Replacing a Failing Greedy Rule With a Table Over Amounts

When largest coin first gives the wrong count, try every coin as the last one for every amount.

A greedy rule that fails can be replaced by dynamic programming over the same choices: instead of committing to one choice, try every choice for every subproblem and keep the best. This example makes that move on making change, where the greedy rule is largest coin first and the table tries every coin as the last one.

With coins of 1, 5, 6 and 9, the fewest coins that make 11 is 2, as 5 + 6. Largest first takes the 9, then needs 2 more and can only pay it with two 1s, 3 coins in all; once the 9 is taken it is never reconsidered. The greedy rule chose among the right options, the coins, but tried only one of them.

The table keeps the choices and drops the commitment. Let best[a] be the fewest coins that make amount a. The last coin paid is one of the four, and whichever it is, the rest is a smaller amount paid as cheaply as possible. So best[a] is 1 plus the smallest best[a − c] over every coin c no larger than a, with best[0] = 0. The amounts are filled from 0 upwards, so every smaller amount is ready when it is needed.

best[a], the fewest coins from 1, 5, 6 and 9 that make each amount a from 0 to 11

InputCoins 1, 5, 6 and 9; amounts 0 to 11

amount 0
1. 0a
2. -
3. -
4. -
5. -
6. -
7. -
8. -
9. -
10. -
11. -
12. -
Amount 0 needs no coins, so best[0] is 0. Every other entry is still unknown.
amount 1
1. 0
2. 1a
3. -
4. -
5. -
6. -
7. -
8. -
9. -
10. -
11. -
12. -
Only the 1 fits, so amount 1 needs best[0] + 1 = 1 coin.
amount 2
1. 0
2. 1
3. 2a
4. -
5. -
6. -
7. -
8. -
9. -
10. -
11. -
12. -
Only the 1 fits again: best[1] + 1 = 2.
amount 3
1. 0
2. 1
3. 2
4. 3a
5. -
6. -
7. -
8. -
9. -
10. -
11. -
12. -
Still only the 1: three coins.
amount 4
1. 0
2. 1
3. 2
4. 3
5. 4a
6. -
7. -
8. -
9. -
10. -
11. -
12. -
Four coins; the 5 is still too large.
amount 5
1. 0
2. 1
3. 2
4. 3
5. 4
6. 1a
7. -
8. -
9. -
10. -
11. -
12. -
The 5 fits, and best[0] + 1 = 1 beats best[4] + 1 = 5 with a 1 as the last coin.
amount 6
1. 0
2. 1
3. 2
4. 3
5. 4
6. 1
7. 1a
8. -
9. -
10. -
11. -
12. -
The 6 fits: best[0] + 1 = 1.
amount 7
1. 0
2. 1
3. 2
4. 3
5. 4
6. 1
7. 1
8. 2a
9. -
10. -
11. -
12. -
A last 1 gives best[6] + 1 = 2, a last 5 gives best[2] + 1 = 3 and a last 6 gives best[1] + 1 = 2, so 2.
amount 8
1. 0
2. 1
3. 2
4. 3
5. 4
6. 1
7. 1
8. 2
9. 3a
10. -
11. -
12. -
A last 1 or a last 6 gives 3, and a last 5 gives best[3] + 1 = 4, so 3.
amount 9
1. 0
2. 1
3. 2
4. 3
5. 4
6. 1
7. 1
8. 2
9. 3
10. 1a
11. -
12. -
The 9 fits: best[0] + 1 = 1.
amount 10
1. 0
2. 1
3. 2
4. 3
5. 4
6. 1
7. 1
8. 2
9. 3
10. 1
11. 2a
12. -
A last 1 gives best[9] + 1 = 2, as does a last 5 with best[5] + 1, so 2.
amount 11
1. 0
2. 1
3. 2
4. 3
5. 4
6. 1
7. 1
8. 2
9. 3
10. 1
11. 2
12. 2a
A last 5 gives best[6] + 1 = 2, and so does a last 6 with best[5] + 1: 5 + 6. Largest first takes the 9 and then two 1s, 3 coins.

Result2 coins for 11, 5 + 6, where largest first uses 3

The last frame holds the answer, 2, and the run read the coins back by storing the last coin chosen at each amount: 5 at 11, leaving 6, which a single 6 pays. The greedy answer is in the same table: the 9 leaves amount 2, which costs best[2] = 2 more coins, where the 5 leaves amount 6, which costs 1.

The table costs O(amount × coins), one step for each coin at each amount, against the greedy rule's single pass, and it is right for every set of coins. The general move is the same whatever the problem: keep the greedy rule's choices as the options, make the subproblem what is left after a choice, and let the table try them all. Greedy Algorithms' van loaded by value per kilo is the same move in another surface: when the cargo cannot be split, the 0/1 knapsack table replaces the rule.

← → move through sections and cards