When Greedy Fails
You'll learn: How to recognize situations where the greedy approach produces incorrect or suboptimal solutions.
The Illusion of Greedy Perfection
While greedy algorithms are elegant and efficient, they don't work for every optimization problem. A greedy algorithm makes the locally optimal choice at each step, hoping this leads to a global optimum—but sometimes that hope is misplaced.
Classic Example: Coin Change
Imagine you need to make change for 6 cents using the minimum number of coins. If your coin denominations are {1, 3, 4}, a greedy approach would:
- Pick the largest coin ≤ 6 → take a 4-cent coin (remaining: 2)
- Pick the largest coin ≤ 2 → take a 1-cent coin (remaining: 1)
- Pick the largest coin ≤ 1 → take a 1-cent coin (remaining: 0)
Greedy result: 3 coins (4 + 1 + 1)
Optimal result: 2 coins (3 + 3)
The greedy choice of taking the largest coin first led us astray! By being "greedy" for the 4-cent coin, we blocked ourselves from the better solution.
Why It Fails
Greedy fails when:
- The greedy choice property doesn't hold—the locally optimal choice doesn't lead to a globally optimal solution
- Future consequences of current choices aren't properly accounted for
- The problem requires "undoing" earlier decisions based on later information
With standard coin systems (like US coins: 1, 5, 10, 25), greedy does work. But with arbitrary denominations, you need dynamic programming to guarantee the optimal answer.
Key Takeaway: Not all optimization problems have the greedy choice property—always verify that greedy choices lead to global optimality before trusting the approach, especially with arbitrary constraints.