Trusting a Greedy Rule Without a Proof

A greedy rule that gives the right answer on every example you try can still be wrong, because a greedy rule is only correct when it is proved correct. This card shows two plausible rules failing and the cheapest way to find out: one small counterexample.

The symptom is an answer that looks reasonable and is not the best. Nothing crashes and nothing warns, so the mistake surfaces only when someone compares the output with a better one. The trigger is a rule that worked on the familiar case and was trusted on a new one: largest coin first, which works for 25, 10, 5 and 1, used for a different set of coins, or shortest meeting first, which sounds as if it should leave the most room.

A run tried both rules and compared each with a brute-force search that tries every possibility.

The mechanism is a missing greedy choice property. With coins 1, 5, 6 and 9, no best answer for 11 starts with a 9, so taking it first shuts out the two-coin answer for good, and a greedy algorithm never goes back. The shortest meeting, 4 to 7, overlaps both of the others, so choosing it loses two meetings to gain one. The run went further for the coins: across every amount from 1 to 99, largest first was beaten on 40 amounts with 1, 5, 6 and 9, starting at 11, and on none with 1, 5, 10 and 25.

The cost is a wrong answer that passes every test built from the case the rule was designed on. A till that gives one extra coin, or a calendar that schedules one meeting fewer, is a bug nobody reports.

The remedy is to try to break a greedy rule before trusting it. Search small inputs, three or four items, for one where the rule's first choice is not part of any best answer, either by hand or by running a brute-force search beside the greedy one, as the run above did. One counterexample is a complete disproof. If none turns up, prove the rule with an exchange argument, as Proving a Greedy Choice With an Exchange Argument does for meetings. If the rule breaks and no other measure works, the problem needs dynamic programming, which keeps every choice that could still lead to the best answer: Dynamic Programming, a later topic, solves fewest coins for any coin set.