Greedy Algorithm

Greedy approach gives a feasible solution to a problem where multiple solutions are possible. Greedy approach doesn’t give you the optimal solution, but if the feasible solution is optimal, then we can accept that solution.

Let’s consider the coin changing problem, which could be solved using greedy algorithm. Assume that, we are given a set of coins, and a sum to be changed. Then we can do so,

import math

def greedy(coins, target):
 remaining = 0
 count = 0
 i = 0
 times = 0
 while(True):
      if(target is 0):
           break
      else:
           times = math.floor(target/coins[i])
           remaining = target - (coins[i]*times)
           target = remaining
           print(coins[i]," needs: ", times," times.")
           i += 1
           count += times
 return count
coins = [10,5,2,1]
print("\ntotal coins needed: ", greedy(coins, 31))
10  needs:  3  times.
5  needs:  0  times.
2  needs:  0  times.
1  needs:  1  times.

total coins needed:  4

As we can see that, we need total 4 coins to make 31 from the list of [10,5,2,1] coins. In this case it is an optimal solution, but if we are given [4,3,1] for 6 then the total number of coins we need would be 3 using the greedy algorithm. Unfortunately, the optimal solution would be 2. So we see that greedy algorithm has some drawbacks, but it could be optimized using the dynamic programming.

Author: ashiquechowdhury

A software developer, and a data science enthusiast

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s