Course contentsShow
← Computer Science
Lesson 885 of 2,87221. Greedy AlgorithmsFree lesson

When Greedy Fails

Recognize problems where greedy produces suboptimal results, like coin change with arbitrary denominations.

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:

  1. Pick the largest coin ≤ 6 → take a 4-cent coin (remaining: 2)
  2. Pick the largest coin ≤ 2 → take a 1-cent coin (remaining: 1)
  3. 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.