6.17

Making Change (Unlimited Coins)

Pattern · Knapsack with repetition 2-D Boolean table O(nv) 3difficulty
Question — exam style

Given an unlimited supply of coins of denominations x[1], x[2], …, x[n], we wish to make change for a value v; that is, we wish to find a set of coins whose total value is v. This might not be possible: for instance, if the denominations are 5 and 10 then we can make change for 15 but not for 12. Give an O(nv) dynamic-programming algorithm for the following problem.

Input:Denominations x[1], …, x[n]; a value v.
Output:A Boolean: is it possible to make change for v using these denominations (each usable unlimited times)?

Model answer

4-part format
aSubproblem in words
T(i, b) = true iff some multiset of coins drawn from denominations x[1..i] sums to exactly b, for 0 ≤ i ≤ n and 0 ≤ b ≤ v.

"Unlimited supply" ⇒ Knapsack with repetition. The key structural difference: when you take coin i, you may take it again, so you stay on row i, not i−1.

bRecurrence math only, with base cases + bounds
T(i, 0) = true for 0 ≤ i ≤ n T(0, b) = false for 1 ≤ b ≤ v If x[i] > b: T(i, b) = T(i-1, b) Else: T(i, b) = T(i-1, b) OR T(i, b - x[i]) for 1 ≤ i ≤ n, 1 ≤ b ≤ v

Either don't use denomination i at all (T(i−1,b)), or use one coin of it and keep denomination i available for the remainder (T(i, b−x[i]) — note the i, not i−1).

Understanding this recurrence, step by step read if it isn't clicking

1 What one table entry actually asks

T(i, b) is a yes/no question:

"Using only coin types x[1], …, x[i] — each usable as many times as I want — can I make exactly the amount b?"

Two knobs. i = how many coin types are on the table right now. b = the amount you're currently trying to hit. Every cell of the table holds one Boolean, true or false.

2 The two base cases (where it bottoms out)

  • T(i, 0) = true — the target 0 is always makeable: use no coins at all. The empty pile sums to 0. True for every i.
  • T(0, b) = false for b ≥ 1 — with zero coin types available, you can't make any positive amount.

3 The recurrence is one decision: use coin type i, or don't

Standing at T(i, b), ask a single question about the newest coin type, x[i]. There are exactly two ways the answer could be "yes," and you're happy if either works — that's why the two options are joined by OR.

Option A — skip coin type i entirely

Then you must make b using only the earlier types 1..i−1. That is exactly T(i−1, b). Notice i drops to i−1 — you've put that coin away for good.

Option B — use at least one coin of type i

Lay down one x[i] coin. You've covered x[i] of the amount, so you still need to make b − x[i]. Crucially, coin type i is still available for that remainder — so the subproblem is T(i, b − x[i]), with i unchanged.

The guard if x[i] > b just kills Option B when the coin is bigger than the amount left — you can't place a coin worth more than the target — leaving only Option A.

4 The heart of it: why T(i, b−x[i]) and not T(i−1, b−x[i])?

This single index is the whole problem. It's the difference between "unlimited supply" and "each coin once."

✓ T(i, b−x[i]) — index stays i

Coin type i is still on the table for the rest of the amount → you may use it again → unlimited supply. This is what 6.17 asks for.

✗ T(i−1, b−x[i]) — index drops to i−1

After using coin i once, it's gone → each coin used at most once. That's the 0/1 problem — a different question.

Concretely, with one coin type x = [3] and target 6, the "yes" path is: use coin 3 → need T(1, 3) → use coin 3 again → need T(1, 0) = true. It used coin type 1 twice, and it could only do that because the index stayed 1 both times. Had it dropped to T(0, 3) after the first use, that's false, and you'd wrongly conclude 6 is unmakeable.

5 The whole thing, filled out — x = [3, 5], v = 11

Bottom-up: fill row by row, and within each row go left to right (increasing b), because Option B reads T(i, b−x[i]) — a smaller b in the same row — which must already be filled.

b=0 b=1 b=2 b=3 b=4 b=5 b=6 b=7 b=8 b=9 b=10 b=11 i=0 T F F F F F F F F F F F ← no coins: only 0 works i=1 T F F T F F T F F T F F ← coin 3 only → multiples of 3 i=2 T F F T F T T F T T T T ← add coin 5 Answer = T(2, 11) = TRUE (11 = 3 + 3 + 5)

A few cells traced so you can see both options firing:

Row i=1 (coin 3 only): T(1,3) = T(0,3) OR T(1,0) = F OR T = T one 3 T(1,6) = T(0,6) OR T(1,3) = F OR T = T 3+3 (reuses coin 3: reads T(1,3), same row) T(1,9) = T(0,9) OR T(1,6) = F OR T = T 3+3+3 → row 1 is true exactly at the multiples of 3: {0,3,6,9}. Correct. Row i=2 (coins 3 and 5): T(2,5) = T(1,5) OR T(2,0) = F OR T = T one 5 T(2,6) = T(1,6) OR T(2,1) = T OR F = T inherited 3+3 (Option A) T(2,8) = T(1,8) OR T(2,3) = F OR T = T 5 + 3 T(2,11) = T(1,11) OR T(2,6) = F OR T = T 5 + (3+3) → makeable amounts: {0,3,5,6,8,9,10,11}. (1,2,4,7 are impossible from 3s and 5s.)
The one-sentence summary: to make b from coin types 1..i — either make it without type i (T(i−1, b)), or spend one type-i coin and make the rest while still allowed to use type i (T(i, b−x[i])). That "still allowed" is the entire trick.
cImplementation analysis
(1) # of subproblems
O(nv)
(2) Time to fill table
O(nv) — O(1) per entry
(3) Where answer is extracted
T(n, v)
(4) Time to extract
O(1)
The one thing that separates the two Knapsacks

With repetition: the "take" branch stays on the same item index — T(i, b−x[i]). Without repetition (0/1): the "take" branch moves to T(i−1, b−x[i]). Memorize this single-character difference; it's the most common re-skin on this exam.

Optional pseudocode not required by Ed #9

A mechanical translation of the 1-D with-repetition form.

function MakeChange(x[1..n], v):
    T[0] = true
    for b = 1 to v:
        T[b] = false
        for i = 1 to n:
            if x[i] <= b and T[b - x[i]]:
                T[b] = true; break
    return T[v]
✎

Try it yourself

worked example + self-test

1-D form: T(0)=true; T(b)=ORcoins c(c≤b AND T(b−c)). Answer T(v).

Worked 1-D boolean table

denominations x = [3, 5, 7] target v = 13

b │ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 T(b) │ T F F T F T T T T T T T T T coin used│ – – – 3 – 5 3 7 3 3 3 3 3 3 T(6)=T because coin 3 works and T(6−3)=T(3)=T T(4)=F: every coin lands on a false cell or overshoots
Answer: T(13) = true. One coin set: {3, 3, 7} (=13).  Edge: x=[5,10], v=12 → false (only multiples of 5 reachable).
Self-test fill T(b), then reveal

denominations x = [4, 6, 9] target v = 17

Reveal answer
T(17) = true.  One coin set: {4, 4, 9} (= 17).