The coin change problem
In short: The coin change problem asks for the fewest coins that make a given amount; a dynamic programming table solves it in O(amount × coins), names the coins and counts the ways.
Problem
The machine's change
The parking machine returns change. It has one tube for each of the eight euro coins: 1, 2, 5, 10, 20 and 50 cents, 1 € and 2 €. The fewer coins it returns, the less often someone has to refill the tubes. So the change has to use the fewest coins.
The developer does not want to guess and writes a recursion that tries everything: for every coin that fits into the change, "this coin plus the best for the rest", and takes the smallest. The amounts are in cents, and the counter counts the coins tried:
tries = 0
def fewest(coins, amount): global tries if amount == 0: return 0 best = amount + 1 for coin in coins: if coin > amount: break tries += 1 count = fewest(coins, amount - coin) + 1 best = min(best, count) return best
coins = [1, 2, 5, 10, 20, 50, 100, 200]for amount in [10, 20, 30]: tries = 0 count = fewest(coins, amount) print(f"{amount} cents: {count} coins, {tries} tries")10 cents: 1 coins, 309 tries20 cents: 1 coins, 66281 tries30 cents: 2 coins, 14158888 triesThe answers are right. But for 30 cents the recursion tries 14,158,888 coins, and for 40 cents 3,024,560,419. Change of 63 cents takes 689,951,222,249,236 tries: at a billion a second that is eight days, while the driver waits at the barrier.
The idea
The table
The recursion asks the same thing again and again: the best for 13 cents, for 8 cents, for 3 cents. These are the overlapping subproblems from the previous lesson. Only here up to eight branches leave every amount, one for each coin, and the tree grows even faster.
So we build a table bottom up. A dynamic programming table is described by four things:
- What the cell means. best[a] is the fewest coins for exactly a cents.
- Where it comes from. The last coin is one of those that fit. So best[a] is 1 + best[a − coin] for the best coin.
- In which order it is filled. a − coin is less than a. From left to right everything the cell reads is already done.
- Where the answer is. In the last cell, best[change]. The start is best[0] = 0: zero cents need no coins.
This is a DP table: a cell for every subproblem, filled in an order where each cell finds ready the ones it depends on. As in the previous lesson, only the choice in the cell is between more options.
See it
Cell by cell
The table for 9 cents. Watch the arrows: each comes from cell a − coin, and cell a keeps the smallest it has seen:
def change(coins, amount): best = [0] * (amount + 1) last = [0] * (amount + 1) for a in range(1, amount + 1): best[a] = amount + 1 for coin in coins: if coin > a: break count = best[a - coin] + 1 if count < best[a]: best[a] = count last[a] = coin used = [] a = amount while a > 0: used.append(last[a]) a -= last[a] return usedStep by step, in words
- change(coins, 9): best[a] is the fewest coins for a cents, last[a] the coin that gets there. best[0] = 0: zero cents need no coins.
- For each a from left to right, try every coin up to a: one coin plus the best for what is left, best[a − coin] + 1. The arrow comes from that cell.
- a = 5: the coin 1 gives best[4] + 1 = 3, the coin 2 gives best[3] + 1 = 3, the coin 5 gives best[0] + 1 = 1. The cell keeps the smallest, and last remembers the coin.
- The coins are ordered small to large, and 10 is already more than 9: the loop stops there. Every cell reads only cells to its left, which are already final.
- Back along last: 9 → 7 → 5 → 0. The coins are 2 + 2 + 5. 22 tries for 9 cents, each cell solved once.
coins = [1, 2, 5, 10, 20, 50, 100, 200]print(change(coins, 9))[2, 2, 5]amount + 1 means "nothing yet": you can never need more coins than cents, because even one-cent coins make exactly amount. So the first coin tried is always better.The idea
Which coins
The count is not enough: the machine also has to know which coins to drop. So next to best[a] the table also keeps last[a], the coin that leads to the best for a. At the end you start from the change: drop last[a], subtract it, and repeat until you reach 0.
tries = 0
def change(coins, amount): global tries best = [0] * (amount + 1) last = [0] * (amount + 1) for a in range(1, amount + 1): best[a] = amount + 1 for coin in coins: if coin > a: break tries += 1 count = best[a - coin] + 1 if count < best[a]: best[a] = count last[a] = coin used = [] a = amount while a > 0: used.append(last[a]) a -= last[a] return used
coins = [1, 2, 5, 10, 20, 50, 100, 200]for amount in [63, 480]: tries = 0 used = change(coins, amount) text = " + ".join(map(str, used)) print(f"{amount} cents: {text}, {tries} tries")63 cents: 1 + 2 + 10 + 50, 296 tries480 cents: 10 + 20 + 50 + 200 + 200, 3460 tries296 tries for 63 cents instead of 689,951,222,249,236. The table has one cell per cent, and each cell tries at most the eight coins. The work is O(n · k): n cents times k kinds of coin. With k = 8 that is linear in the change.
Try it
Fill in
One coin plus the best for the rest. Which cell does the try read?
def change(coins, amount):
best = [0] * (amount + 1)
last = [0] * (amount + 1)
for a in range(1, amount + 1):
best[a] = amount + 1
for coin in coins:
if coin > a:
break
count = best[] + 1
if count < best[a]:
best[a] = count
last[a] = coin
used = []
a = amount
while a > 0:
used.append(last[a])
a -= last[a]
return usedThe rest after the coin is a - coin cents, and the best for it is already in the table, because it is to the left. One more coin is + 1.
The idea
Why not the biggest coin first?
A cashier does something else: gives the biggest coin that fits, and repeats. For 63 cents that is 50, 10, 2, 1: four coins again. With euro coins this rule always gives the fewest coins. The coins are chosen that way.
But the rule depends on the coin system. With other coins, or when a tube in the machine runs out, "biggest first" can give more coins than needed. When it works and when it fails is the lesson "When greedy fails". The table does not rely on that: it tries every coin for every amount and finds the fewest for any coins.
The idea
In how many ways
Another problem with the same table. The cash machine pays out amounts in notes of 5, 10, 20 and 50 €. The testers want to check every possible bundle for 100 € and ask: how many are there?
Now the cell is count[a]: in how many ways exactly a euros can be made. count[0] = 1, the empty bundle. The outer loop goes over the notes, the inner one over the amounts:
def ways(notes, amount): count = [0] * (amount + 1) count[0] = 1 for note in notes: for a in range(note, amount + 1): count[a] += count[a - note] return count[amount]notes = [5, 10, 20, 50]print(ways(notes, 100), "ways")49 waysThe order of the loops matters. When the fives come entirely before the tens, every bundle is built in one order: first the fives, then the tens. So 5 + 10 and 10 + 5 are the same bundle and are counted once. And here nobody looks for a minimum: the cell adds up the number of ways from the cells to its left.
Try it
Predict the output
How many bundles are there for 20 € with notes of 5, 10 and 20?
def ways(notes, amount): count = [0] * (amount + 1) count[0] = 1 for note in notes: for a in range(note, amount + 1): count[a] += count[a - note] return count[amount]
notes = [5, 10, 20]print(ways(notes, 20), "ways")One twenty; two tens; one ten and two fives; four fives. Four bundles. 6 is the number of sequences: 10 + 5 + 5, 5 + 10 + 5 and 5 + 5 + 10 are three of them, but the bundle is one.
Try it
Find the bug
A colleague wrote the same counting, but for 100 € it comes out much bigger:
notes = [5, 10, 20, 50]print(ways(notes, 100), "ways")48007 waysWhich line has the bug?
Pick the line with the bug.
The outer loop goes over the amounts, and the inner one over the notes. So for every amount every note is tried as the last one, regardless of the previous ones, and every arrangement of a bundle is counted separately: 5 + 10 and 10 + 5 are two ways. That is the number of sequences, 48,007, while the bundles are 49. When the notes are the outer loop, every bundle is built in one order and counted once.
See it
Measure it: recursion against the table
We count the coins tried: in every recursive call and in every cell. The recursion is not run above 30 cents: at 40 cents it is over 3 billion tries.
- Recursion without memory
O(2ⁿ) - Table
O(n)
| Algorithm | n = 10 | n = 20 | n = 30 |
|---|---|---|---|
| Recursion without memory | 309 | 66,281 | 14,158,888 |
| Table | 26 | 67 | 117 |
def change(coins, amount): best = [0] * (amount + 1) last = [0] * (amount + 1) for a in range(1, amount + 1): best[a] = amount + 1 for coin in coins: if coin > a: break count = best[a - coin] + 1 if count < best[a]: best[a] = count last[a] = coin used = [] a = amount while a > 0: used.append(last[a]) a -= last[a] return usedEvery 10 cents multiply the recursion by about 200, while the table grows by 40–50 tries. The recursion curve is labelled O(2ⁿ): it is exponential, with a base of about 1.7.
More precisely, if you are curious
The same numbers in your language:
tries = 0
def fewest(coins, amount): global tries if amount == 0: return 0 best = amount + 1 for coin in coins: if coin > amount: break tries += 1 count = fewest(coins, amount - coin) + 1 best = min(best, count) return best
def change(coins, amount): global tries best = [0] * (amount + 1) last = [0] * (amount + 1) for a in range(1, amount + 1): best[a] = amount + 1 for coin in coins: if coin > a: break tries += 1 count = best[a - coin] + 1 if count < best[a]: best[a] = count last[a] = coin used = [] a = amount while a > 0: used.append(last[a]) a -= last[a] return used
coins = [1, 2, 5, 10, 20, 50, 100, 200]for amount in [10, 20, 30]: tries = 0 fewest(coins, amount) plain = tries tries = 0 change(coins, amount) print(f"{amount} cents: no memory {plain}, table {tries}")10 cents: no memory 309, table 2620 cents: no memory 66281, table 6730 cents: no memory 14158888, table 117Exercise
The change from the input
Solve it in your editor.
Change. Read the change in cents and print how many coins the machine returns and which. Use change from the lesson.
4805 coins: 10 + 20 + 50 + 200 + 200More tasks
- An empty tube. The 1 and 2 cent tubes are empty. Which amounts under 1 € can the machine not return at all? How do you tell from the table? (Hint: the cell stays
amount + 1.) - Biggest first. Print the coins from the biggest to the smallest.
- How many ways with coins. In how many ways can you pay 1 € with the coins from 1 to 50 cents? And if the 1 € coin is allowed too?
More precisely
Impossible change and very big numbers
Two things the lesson skipped.
More precisely, if you are curious
When the change cannot be returned. If the 1 and 2 cent tubes are empty, 3 cents cannot be returned with anything. Then the cell stays amount + 1, because no try is better. And if last[a] is 0, walking back would spin forever on the spot. So before walking back you check whether best[amount] > amount, and the machine says "No change, please pay the exact amount".
The number of ways grows very fast. In how many ways can you pay 100 € with coins only (10,000 cents, the eight euro coins)?
def ways(notes, amount): count = [0] * (amount + 1) count[0] = 1 for note in notes: for a in range(note, amount + 1): count[a] += count[a - note] return count[amount]
coins = [1, 2, 5, 10, 20, 50, 100, 200]print(ways(coins, 10000))1133873304647601long, and int would overflow without an error.The table in two dimensions. Counting the ways is really a table "the first i notes × the amount": cell (i, a) is in how many ways a can be made with only the first i notes. Row i is built from the row above it (without note i) and from the cell to the left in the same row (with one more note i). The program keeps only one row and overwrites it from left to right. That is why the outer loop goes over the notes: it walks the rows. The same idea, one row instead of the whole table, comes back in the knapsack problem.
Test