Greedy Algorithms
The best choice right now.
A greedy algorithm makes the choice that looks best right now, and never looks back. It's simple and fast. Sometimes it gives the perfect answer. Sometimes it walks straight into a trap. The skill is knowing which.

- The best choice right now
- Never look back
- Perfect, or a trap
Making change, greedily
To give change with the fewest coins, a cashier grabs the biggest coin that fits, again and again. With normal coins, fifty, twenty, ten, five, two, and one, that always works. Run it. Eighty eight pence is fifty, twenty, ten, five, two, and one. Six coins, and that's the best possible.
def greedy_change(amount, coins):
used = []
for c in sorted(coins, reverse=True):
while amount >= c:
amount -= c
used.append(c)
return used
print(greedy_change(88, [1, 2, 5, 10, 20, 50]))[50, 20, 10, 5, 2, 1]
When greedy fails
Now imagine strange coins, one, three, and four, and we need six. Greedy grabs a four, then a one, and another one. Three coins. But three plus three is only two coins. Run it. Greedy took the best step each time, and still missed the best answer. A technique coming soon, dynamic programming, fixes this.
from greedy import greedy_change
print("greedy:", greedy_change(6, [1, 3, 4]))
print("best: [3, 3]")greedy: [4, 1, 1] best: [3, 3]
Also uses greedy.py
def greedy_change(amount, coins):
used = []
for c in sorted(coins, reverse=True):
while amount >= c:
amount -= c
used.append(c)
return usedSummary
Greedy algorithms take the best step now. They're fast, and sometimes perfect, but not always. Next, a greedy problem where it does work perfectly.
Key takeaways- Best choice now
- Fast and simple
- Not always optimal