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