A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution.
Limitations of Greedy Algorithms
Sometimes greedy algorithm fails to find the optimal solution because it does not consider all available data and make choices which seems best at that moment.
A famous example for this limitation is searching the largest path in a tree.
The greedy algorithm fails to solve this problem because it makes decisions purely based on what the best answer at the time is: at each step it did choose the largest number and solve the problem as 7 -> 12 -> 6 -> 9. Total is: 34.
But obviously, this is not the optimal solution. Correct solution to this problem is, 7 -> 3 -> 1 -> 99. Total is: 110.
Minimum Coin Change Problem
A good example to understand Greedy Algorithms better is; the minimum coin change problem.
In this problem, the aim is to find the minimum number of coins with particular value which add up to a given amount of money. These types of optimization problems is often solved by Dynamic Programming or Greedy Algorithms.
For reference, this is the denomination of each coin in Turkey:
[1 kr, 5 kr, 10 kr, 25 kr, 50 kr, ₺1 (100 kr)]
For returning 2 lira (₺) and 67 kuruş (kr), you’d take the highest-value coin you could. A lira, another lira, then a 50 kr, a 10 kr, a 5 kr and finally two 1 kr. That’s a greedy algorithm, because you’re always greedily choosing the coin that covers the biggest portion of the remaining amount.
denominations = [1, 5, 10, 25, 50, 100] # 100kr is ₺1 def return_change(change, denominations): to_give_back =  * len(denominations) # starting with the largest coin, goes through denominations list # and also keeps track of the counter, pos. for pos, coin in enumerate(reversed(denominations)): # while we can still use coin, use it until we can't while coin <= change: change = change - coin to_give_back[pos] += 1 return to_give_back print(return_change(267, denominations)) # returns [2, 1, 0, 1, 1, 2] # 2x ₺1 (100 kr), 1x 50kr, 0x 25kr, 1x 10kr, 1x 5kr, 2x 1kr = 267kr = ₺2.67
The runtime of this algorithm is dominated by the 2 loops, thus it is O(n2).
- Wikipedia, Coins of Turkey