Greedy Algorithms: Take the Best Choice Now and Never Revisit It

A greedy algorithm builds a solution one step at a time, and at each step takes whichever choice looks best right now, without looking ahead and without ever undoing it. This card covers the method, the two properties a problem needs for it to give the best answer, and how to tell a problem that has them.

Suppose a till has to give 68 cents in change with coins of 25, 10, 5 and 1 cents, using as few coins as it can. A cashier does not list every combination. They take the largest coin that fits, subtract it, and repeat. A run of that rule printed each step:

Seven coins, and a brute-force search over every combination found no way to do it in fewer. Each row makes one choice and never looks at it again: the first 25 stays in the hand whatever happens later.

In general, a greedy algorithm sorts or scans the options by some measure of how good they look, takes the best one that keeps the solution valid, and moves on to what is left. Backtracking, an earlier topic, tries every choice and undoes each one; a greedy algorithm tries one and keeps it, so it usually runs in the time of a sort, O(n log n), or less.

The price is that it is right only when the problem has two properties. The greedy choice property says some best solution begins with the choice the rule picks, so taking it never shuts out the best answer. Optimal substructure says that once the choice is made, what is left is a smaller problem of the same kind, and the best answer to it, added to the choice, is the best answer to the whole. Change for 68 with these coins has both: some fewest-coin answer always starts with the largest coin that fits, and what remains is change for a smaller amount.

Think of climbing a hill in fog by always stepping uphill. Every step is the best one you can see, and you stop when no step goes up. The analogy breaks at the end: the walker reaches a top, not necessarily the highest one, while a greedy rule that has been proved correct always reaches the best answer. The proof is what makes the difference, and Proving a Greedy Choice With an Exchange Argument gives one.

A problem without the greedy choice property is not one to solve this way. Change with coins of 1, 5, 6 and 9 is the example on Trusting a Greedy Rule Without a Proof: the largest coin first takes three coins for 11 where two will do.

Reach for a greedy algorithm when each step has an obvious best local choice and you can argue that taking it never costs the best answer: scheduling, choosing edges for a cheapest network, building a compression code. When you cannot make that argument, the problem needs backtracking or dynamic programming, which keep more than one choice alive.