virtualgate's picture

Greedy Algorithms

Greedy Algorithm | How to come up with a Greedy Algorithm?

Greedy Algorithm:
A greedy algorithm, as the name suggests, always makes the choice that looks best at that moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. Now the question is how to decide which choice is the best (or optimal), for that a function is required (which is called as the objective function) that needs to be optimized (either maximized or minimized) at the given point. Greedy algorithm makes greedy choices at each step such that the objective function is optimized. The Greedy Algorithm has only one shot to compute the optimal solution as it never goes back and reverses the decision.

How to come up with a Greedy Algorithm?

Let’s take an example. Suppose you are suffering from a lethal disease and you have only T years left to live. Now you want to try all the different things you always wanted to do. You are given an array A of integers denoting the time taken to complete different things in years. You want to know what is the maximum number of different things you can do in the limited time you have.

This is a simple Greedy Problem. In each iteration, one needs to greedily select the things which will take minimum time to complete and also maintain two variables currentTime and numberOfThings. So, simply sort the array A in nondecreasing order. Then, select the things one by one and add the time taken to complete that thing into currentTime and also add one to numberOfThings. Repeat as long as the currentTime is smaller than or equal to T.

Let A=[5,3,4,2,1] and T=6

After sorting, A=[1,2,3,4,5]

After 1st iteration,currentTime=1 and numberOfThings=1
After 2nd iteration, currentTime=1+2=3 and numberOfThings=2
After 3rd iteration, currentTime=3+3=6 and numberOfThings=3
After 4th iteration, currentTime=6+4=10 which is greater than T, answer will be 3.

Contributor's Info

Created: Edited:
0Comment
Kruskal's algorithm Minimum Spanning Tree Graph Algorithm
Content covered: 

Kruskal's algorithm Minimum Spanning Tree Graph Algorithm

More Less
0Comment
Prim's Algorithm Minimum Spanning Tree Graph Algorithm
Content covered: 

Prim's Algorithm Minimum Spanning Tree Graph Algorithm

More Less
1Comment
GATE 2005 Example on Greedy Algorithms

We are given 9 tasks \(T_1, T_2, T_3, .....T_9\).The execution of each task requires one unit of time. We can execute one task at a time. Each task \(T_i\)has a profit \(P_i\) and a deadline \(d_i\). Profit \(P_i\) is earned if the task is completed before the end of the \(d_i^{th}\) unit of time.

 

Task \(T_1\) \(T_2\) \(T_3\) \(T_4\) \(T_5\) \(T_6\) \(T_7\) \(T_8\) \(T_9\)
Profit 15 20 30 18 18 10 23 16 25
Deadline 7 2 5 3 4 5 2 7 3

 

(1) Are all tasks completed in the schedule that gives maximum profit ?

      A) All tasks are completed

      B) \(T_1 \ \ and \ \ T_2\) are left out

      C) \(T_1 \ \ and \ \ T_8\) are left out.

      D) \(T_4 \ \ and \ \ T_6\) are left out.

(2) What is the maximum profit earned ?

     A) 147

     B) 165

     C) 167

     D) 175

 

(1)

\(\underline{\text{Step - I}}\):  Arrange the the task in increasing order of Deadline and then Profit:

Task \(T_7\) \(T_2\) \(T_9\) \(T_4\) \(T_5\) \(T_3\) \(T_6\) \(T_8\) \(T_1\)
Deadline 2 2 3 3 4 5 5 7 7

 

\(\underline{\text{Step - II}}\) : Now, pick task one by  one and execute it (NOTE: Each task takes 1 unit of time )

Task \(T_7\) \(T_2\) \(T_9\) \(T_5\) \(T_3\) \(T_8\) \(T_1\)    
Time Period of Execution 0 to 1 1 to 2 2 to 3 3 to 4 4 to 5 5 to 6 6 to 7    

 

Hence, Except  \(T_4 \ \ and \ \ T_6 \)  , all other task are completed. Ans (D)

(2)

Maximum Profit = \(P_7 + P_2+ P_9 + P_5 + P_3 + P_8 + P_1\)

\(\hspace{30mm} = 23 + 20 +25+18+ 30 + 16+15\)

\(\hspace{30mm} = 147\)

Hence, Ans (A)

0Comment

  • This quiz contains 10 questions on the topic Greedy Algorithms
  • Learn well before you attempt the quiz
  • You can attempt the quiz unlimited number of times.

Difficulty Level:  intermediate