When the Greedy Choice Fails

A greedy algorithm makes the best-looking move right now. Sometimes that is exactly right. Other times it walks confidently into a worse answer.

Coin example

If the coins are 25, 10, 5, and 1 cents, choosing the largest coin at each step works for many amounts. But with coin values 10, 6, and 1, the amount 12 exposes the problem.

Greedy chooses 10 + 1 + 1. The better answer is 6 + 6.

Discussion prompt

Ask students: what would have to be true for the greedy method to be safe?

The point is not that greedy algorithms are bad. The point is that a method that feels reasonable still needs a reason.

← Back to All Resources