Chapter 9 · Greedy Technique
When Greedy Works (and When It Doesn't)
A greedy algorithm makes the choice that looks best right now — feasible, locally optimal, irrevocable — and never looks back. Sometimes that is provably optimal. Sometimes it is quietly wrong. Put three classic problems side by side and find out which is which.
predictions: 0 / 0
🤔 Predict:
Details
How to read this
- Change-making: the top lane is the greedy cashier (largest coin that fits, again and again). The bottom lane is the DP optimum. Same length = greedy was optimal for this amount.
- Activity selection: each bar is an activity on a timeline, listed in the order the greedy rule considers them. Green = picked, grey = skipped because it overlaps something already picked (outlined in red). The dashed line marks when the last picked activity ends.
- Knapsack: the long bar is the knapsack's capacity. Items pour in best value-per-weight first; the last one may be cut into a fraction. The summary compares that with the 0/1 version, where items cannot be cut.
- Every run ends with a proof-by-comparison: the greedy answer next to a brute-force or DP optimum.
Try this
- US coins 25, 10, 5, 1 and 48¢: greedy gives 25 + 10 + 10 + 1 + 1 + 1 (6 coins), which is optimal. Press “Find a counterexample” — none exists for this canonical set.
- Coins 1, 3, 4 and amount 6: greedy takes 4 + 1 + 1 (3 coins) but 3 + 3 needs only 2. Try coins 1, 5, 10, 20, 25 and amount 40 too.
- Activity selection with the classic interview data (start 1, 3, 0, 5, 8, 5 / end 2, 4, 6, 7, 9, 9): earliest finish picks indices 0, 1, 3, 4 — four activities, the maximum.
- Switch the activity rule to “earliest start” or “shortest duration” and load the matching trap preset. The greedy count drops below the brute-force optimum.
- Knapsack “0/1 greedy fails” preset (W = 50): fractional greedy earns 240, which is optimal when cutting is allowed. Without cutting, greedy by ratio gets 160 but the best 0/1 choice is 220.