Greedy Algorithms8 sections · 316 units
Open in Course

When Greedy Fails

The warning signs

Greedy fails when a locally optimal choice blocks a globally optimal solution. Warning signs:

1.1. The current choice affects what choices are available later.

2.2. You need to "undo" a previous choice to find the optimum.

3.3. The problem involves discrete items that cannot be split.

4.4. Small examples show greedy gives the wrong answer. The classic example is 00/11 knapsack. Greedy by value-to-weight ratio fails because you cannot take fractions of items.