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.