← What the Snack Machine Knows · Lesson 2 of 3
Largest coin first
When a machine owes you 41¢ it gives a quarter, a dime, a nickel and a penny: the largest coin that fits, then the largest that fits in what is left. For US coins that greedy rule always gives the fewest coins. Mathematicians call such a coin system canonical.
Not every token set is canonical. A machine paying in tokens worth 1, 3 and 4 that owes 6 gives 4 + 1 + 1 by the greedy rule, three tokens, when 3 + 3 is two. The rule that never loses works backwards: the fewest for an amount is one more than the fewest for the amount minus some token, whichever token makes that smallest.
Children on CodeRealm compare the two rules on a table of amounts and find exactly where greed goes wrong.
A machine pays change in tokens worth 1, 4 and 5 and owes you 8. What is the fewest tokens it can give?