A greedy algorithm builds a solution step by step, making the locally best choice at each turn without ever reconsidering. While simple and fast, a series of local optimizations does not always yield a globally optimal result.
| Approach | Behavior | Risk / Benefit |
|---|---|---|
| Greedy | Grabs immediate best step | Fast, but can fail globally |
| Optimal | Maximizes overall result | Guaranteed best, often slower |
Some problems allow greedy solutions. Making change with standard coins, minimizing lateness, and building minimum spanning trees are proven optimal via exchange arguments or matroids.
When Greedy Fails
Greedy often fails, and the definitive proof is a counterexample. Consider making change for 30 using coins of sizes .
The greedy choice picks 20 first, leaving 10, and takes ten 1sts for a total of 11 coins. The optimal solution uses two 15s, totaling just 2 coins.
Common pitfall: Assuming a locally optimal choice guarantees a global optimum. Never assume correctness; you must mathematically prove it, or a single counterexample will demolish your algorithm.