Why greedy fails
Overview
Greedy algorithms fail when a locally optimal choice prevents finding the globally optimal solution. For example, making change for `6` with coins `{1, 3, 4}`. A greedy approach takes `4 + 1 + 1` (3 coins), but the optimal is `3 + 3` (2 coins). Taking the biggest coin blocks the better combination.
Identifying when greedy fails is crucial because it tells you when to switch to more exhaustive strategies like dynamic programming.
Where used: Coin change problems with arbitrary denominations, 0/1 Knapsack, Complex resource allocation
Why learn this
- You will save hours of debugging by quickly identifying problems that cannot be solved greedily.
- It forms the diagnostic rule for knowing when to reach for dynamic programming.
- Interviewers frequently present problems that look greedy but are actually dynamic programming traps.
Common mistakes
- Trying to 'fix' a failing greedy algorithm with more heuristics: If the problem lacks the greedy-choice property, adding complex conditions or sorting rules usually just creates a fragile algorithm that fails on different edge cases.
- Assuming 0/1 Knapsack works like Fractional Knapsack: In Fractional Knapsack, you can split items, so taking the best value-to-weight ratio works. In 0/1 Knapsack, items are indivisible, so taking a high-ratio item might leave awkward empty space.
Recall questions
- Why does a greedy approach fail for making change for `6` using coin denominations of `{1, 3, 4}`?
- What is the diagnostic rule for when a greedy algorithm fails?
- If a greedy algorithm fails, what technique should you usually reach for next?
Understanding checks
Why does the greedy strategy fail for 0/1 Knapsack?
Because items are indivisible. Taking an item with a high value-to-weight ratio might consume capacity that could otherwise hold multiple slightly less efficient items that together yield a higher total value.
The inability to fractionalize items means the greedy choice can leave wasted, unusable capacity.
Given coins `{1, 15, 25}` and a target of `30`, what does the greedy algorithm output, and what is the optimal output?
Greedy outputs 6 coins (`25 + 1 + 1 + 1 + 1 + 1`). The optimal output is 2 coins (`15 + 15`).
Greedy blindly takes the largest coin (`25`), ignoring that it leaves a remainder (`5`) that requires many small coins.
Practice tasks
Spot the failure
Create a counter-example for a greedy pathfinding algorithm that always takes the edge with the lowest immediate cost to reach the target.
Continue learning
Previous: Why greedy works
Next: Overlapping subproblems