When greedy lies to you
Greedy is seductive: short code, O(n log n), feels obviously right. But feeling right is not an argument, and the classic trap is coin change with a non-US coin system.
Coins [1, 3, 4], amount 6:
- Greedy: take 4 (biggest that fits), then 1, then 1. Three coins.
- Optimal: 3 + 3. Two coins.
Taking the 4 looked best but poisoned the future: the remaining 2 can only be made with pennies. Greedy fails whenever a locally-best choice can hurt later options and no exchange argument can rescue it.
The professional workflow: propose the greedy rule, then hunt hard for a counterexample. Find one and you need backtracking (unit 6) or dynamic programming (unit 9, which solves exactly this coin problem). Fail to find one and can argue the exchange, greedy it is.
Code exercise · python
Run this. greedy_coins counts coins biggest-first. best_coins tries EVERY first coin recursively (unit 5 style) and keeps the cheapest, so it is slow but honest. Watch them disagree on 6.
Quiz
What is the RIGHT way to establish that a greedy rule is trustworthy for a problem?
Code exercise · python
Your turn, a greedy that works: cookies. appetites[i] is the smallest cookie that satisfies child i, and each child gets at most one cookie. Sort both lists, then walk the cookies smallest-first, satisfying the easiest unsatisfied child whenever the cookie is big enough. Return how many children end up content.
Quiz
Cookies worked greedily, but coin change with [1, 3, 4] did not. What is the structural difference?
Problem
Coins are [1, 3, 4] and the amount is 6. How many coins does the biggest-first greedy use? (The optimum is 2.)