The Greedy Choice Property
You'll learn: What characteristic makes a problem solvable by greedy algorithms—when choosing the locally best option actually guarantees the globally best solution.
What Is the Greedy Choice Property?
The greedy choice property is the key trait that tells you a problem can be solved greedily. It means that a problem allows you to make the best decision right now, at each step, without worrying about future consequences—and those locally optimal choices will combine to give you the globally optimal solution.
Not all problems have this property! Many require backtracking or dynamic programming because a locally good choice might paint you into a corner later.
When Does It Hold?
A problem has the greedy choice property when:
- Local optimum equals global optimum: The best choice at the current moment remains correct in hindsight.
- No need to reconsider: You never need to undo or revisit a greedy choice.
- Safe first move: Making the greedy choice always leaves you with a smaller, similar subproblem.
Analogy: The Cashier Problem
Imagine giving change with the fewest coins. If you have denominations like {25¢, 10¢, 5¢, 1¢}, always picking the largest coin that fits works perfectly. Choosing 25¢ first for 37¢ is locally best and leads to the globally best solution (25¢ + 10¢ + 1¢ + 1¢).
But with weird denominations like {25¢, 10¢, 4¢}, greedy fails! For 12¢, greedy picks 10¢ + 1¢ + 1¢ (three coins), but optimal is 4¢ + 4¢ + 4¢ (also three—or actually, 10¢ + 1¢ + 1¢ works here, bad example—better: for 8¢, greedy gives 4¢ + 4¢, which is optimal. For 6¢: 4¢ + 1¢ + 1¢ versus 4¢ + 4¢... Let me use: for 6¢, greedy: 4¢ + 1¢ + 1¢ = 3 coins, but you can't do better. Actually standard {10¢, 5¢, 1¢} for 6¢: greedy = 5¢ + 1¢, optimal too).
Key Takeaway: The greedy choice property means the best local decision at every step guarantees the best global result—this property must be proven for each problem before applying a greedy algorithm.