AI Hints
Home›DSA in Python Tutorial›Greedy Algorithms
DSA in Python · Lesson 88 of 132

Greedy Algorithms

The best choice right now.

⏱ 2 min read▶ Video at 1:45:17🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Greedy Algorithms
From the video: Greedy Algorithms
  • 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.

greedy.pypython
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]))
Output
[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.

greedy_fail.pypython
from greedy import greedy_change

print("greedy:", greedy_change(6, [1, 3, 4]))
print("best:   [3, 3]")
Output
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 used

Summary

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
Next up: Practice: Meeting Rooms — greedy that works