Coin Change & Unbounded Knapsack

The previous lesson solved 0/1 knapsack, where each item is taken whole or left behind, at most once. The 0/1 in the name was the include/exclude bit on every item, and it forced a two-dimensional table $K(i,w)$: we had to remember which prefix of items was still on the table, because once item $i$ was used it could not be used again. Now relax exactly that constraint. Let every item be available in unlimited supply, so the thief may pack as many copies of item $i$ as fit. This is the unbounded knapsack problem, and the single change of infinite copies does something surprising to the dynamic program: it erases one whole dimension of the table.

In 0/1 knapsack the second index $i$ existed to stop us from reusing an item; have I already taken item $i$? was genuine state. When items may be reused without limit, that question is meaningless (the set of available items never shrinks), so the only thing a subproblem needs to remember is how much capacity is left. One number, one dimension.

Unbounded knapsack: one dimension instead of two

Define the subproblem on capacity alone:

The answer is $K[W]$ (or ${\max }_{w\le W}K[w]$ if we want at most $W$; padding with a zero-value, weight-one item makes them equal). To fill $K[w]$, consider the last item placed into the knapsack. It is some type $i$ with $w_i\le w$; after placing it we have value $v_i$ plus the best we can do with the remaining budget $w-w_i$, and crucially that remaining budget may use type $i$ again:

Stare at the right-hand side and compare it to 0/1 knapsack's $\max (K(i-1,w),v_i+K(i-1,w-w_i))$. There the include branch read $K(i-1,\cdot )$, the previous row, item $i$ removed from the pool. Here the include branch reads $K[w-w_i]$, the same $K$, item $i$ still in the pool. That one difference is the whole distinction between use once and use any number of times.

Because the available-item set never changes, the item loop and the weight loop may be nested in either order; there is no previous row to respect, only the ascending-weight rule. We fill $W+1$ cells, each scanning up to $n$ items:

time, the same as 0/1 knapsack, but in $\Theta (W)$ space: one array, no second dimension to collapse.

Coin change — minimum coins

The cleanest instance of unbounded knapsack strips the values away, just as subset-sum stripped them from 0/1 knapsack. Fix a set of coin denominations $c_1,\dots ,c_n$, available in unlimited supply, and an amount $A$. Ask: what is the fewest coins that sum to exactly $A$?

This is unbounded knapsack with every item's value set to $1$ (one coin) and the objective flipped to minimize: we want the smallest count, not the largest value. Let $C[a]$ be the minimum number of coins summing to amount $a$:

The $1+(\cdots )$ pays for the coin we just placed; the $\min$ over denominations $c\le a$ picks the best amount to reach the shortfall $a-c$. An amount that no combination of coins can hit keeps the sentinel value $+\infty$, which propagates: if every $C[a-c]$ is $\infty$ then so is $C[a]$. The figure below shows the 1-D table filling left to right, each cell reaching back $c$ positions for each denomination.

With coins $\{1,3,4\}$ the table reads $C=[0,1,2,1,1,2,2]$ for amounts $\mathrm{0..6}$: $C[6]=1+\min (C[5],C[3],C[2])=1+\min (2,1,2)=2$, achieved by $3+3$ (the highlighted transition): two coins, not the three a careless greedy pick would take.

The outer loop runs over $A$ amounts and the inner over $n$ coins, so the running time is $\Theta (nA)$ in $\Theta (A)$ space, pseudo-polynomial in exactly the sense of the previous lesson: polynomial in the numeric value $A$ but exponential in its bit length.¹

Reconstruction. The value $C[A]$ is the coin count; the coins themselves come from the $prev$ array. Starting at $a=A$, the denomination $prev[a]$ is the last coin used, so emit it and jump to $a-prev[a]$; repeat until $a=0$.

Coin change — counting combinations

A different question on the same coins: not how few coins, but how many distinct ways to make amount $A$. This is Coin Change II, and it counts multisets of coins. $\{1,1,1,1\}$ and $\{1,3\}$ are two ways to make $4$, but $\{1,3\}$ and $\{3,1\}$ are the same way, because a multiset has no order. Let $N[a]$ be the number of such combinations summing to $a$, with $N[0]=1$ (the empty multiset is the one way to make $0$).

The naive recurrence "$N[a]={\sum }_{c\le a}N[a-c]$" is wrong for combinations; it counts $1+3$ and $3+1$ separately. The fix is structural and is the most famous loop-order subtlety in dynamic programming.

Why does coins-outer kill the double-count? Because each denomination is introduced exactly once and never revisited, every multiset is built in a fixed canonical order of denominations (coin $c_1$ first, then $c_2$, and so on), so each multiset is reached by exactly one path through the loops. The amount-outer loop, by contrast, re-asks which coin is last? at every amount, so the same multiset is counted once for each ordering of its coins.

Because coin $2$ is introduced only after coin $1$ is fully folded in, each multiset is built in the fixed order ones first, then twos, so $N[3]=2$ counts $\{1,1,1\}$ and $\{1,2\}$ once apiece and never sees a $2+1$.

Swapping the two loops (for a outside, for i inside) computes $N[a]={\sum }_{i:c_i\le a}N[a-c_i]$ instead, the ordered count (Combination Sum IV), where $1+3$ and $3+1$ are distinct. Same body, same $\Theta (nA)$ time; the nesting alone flips the meaning.

A worked count: combinations vs sequences

Take coins $\{1,2\}$ and amount $A=3$. As an unordered count the answers are $\{1,1,1\}$ and $\{1,2\}$: two combinations. As an ordered count we also distinguish the arrangements of $\{1,2\}$, giving $1+1+1$, $1+2$, and $2+1$, for three sequences. The figure traces both, and ties each to its loop order.

The blue link makes the discrepancy concrete: the single combination $\{1,2\}$ on the left explodes into the two ordered sequences $1+2$ and $2+1$ on the right. Counting the left column is the coins-outer loop; counting the right is amount-outer. Picking the wrong nesting silently answers the wrong question: no crash, just a wrong number, which is what makes it the classic bug.

Why greedy fails — and when it works

Coin change has a seductive greedy heuristic: repeatedly take the largest coin that fits. For the U.S. currency system it always gives the minimum, which is why cashiers can make change without dynamic programming. But it is not correct in general. Take coins $\{1,3,4\}$ and amount $6$. Greedy grabs the $4$, then must finish with $1+1$, for three coins, yet $3+3$ makes $6$ in two. The largest-coin-first choice walked into a remainder ($2$) that the denominations cover badly, while a less greedy first step ($3$) left a remainder the coins cover perfectly.

A coin system is called canonical when the greedy algorithm is optimal for every amount; standard currencies (like $\{1,5,10,25\}$) are deliberately designed to be canonical so that greedy change-making works. Whether an arbitrary system is canonical is itself a nontrivial question (it can be decided by checking greedy against the DP optimum over a bounded range of amounts), but the safe default for an unknown denomination set is the $C[a]=1+{\min }_{c}C[a-c]$ dynamic program, which is correct for any coins.³

The same shape elsewhere: Perfect Squares and Word Break

Once you see coin change as unbounded knapsack, two famous problems reveal themselves as the identical recurrence with the coins renamed.

Perfect Squares asks for the fewest perfect squares ($1,4,9,16,\dots$) summing to $n$. That is exactly $\text{Min-Coins}$ with the coins being the squares $\le n$:

The squares are reusable (you may use $1$ four times to make $4$), so it is the ascending-weight minimization we already wrote; only the denomination set changes.

Word Break asks whether a string $s$ can be segmented into dictionary words. The coins are now words, the amount is a string prefix, and the table is indexed by prefix length. Let $B[k]$ be true if the first $k$ characters of $s$ split into dictionary words:

It is the boolean ($\vee$) flavor, like subset-sum was to knapsack, where a word $w$ ending at position $k$ plays the role of a coin of value $|w|$ landing the prefix on the earlier boundary $k-|w|$. The empty prefix $B[0]$ is the always-reachable base, exactly like $C[0]=0$.

Takeaways

• Unbounded knapsack lets each item be used any number of times. That single change deletes the item dimension: the subproblem $K[w]$ depends only on remaining capacity, giving the 1-D recurrence $K[w]={\max }_{w_i\le w}(v_i+K[w-w_i])$ in $\Theta (nW)$ time and $\Theta (W)$ space, versus 0/1 knapsack's 2-D $K(i,w)$.
• The include branch reads $K[w-w_i]$ at the same item-availability (not the previous row), so we sweep weight ascending to permit reuse, the exact opposite of 0/1's descending sweep, which forbids it.
• Coin change (min coins) is unbounded knapsack with unit values and a $\min$ objective: $C[a]=1+{\min }_{c\le a}C[a-c]$, $C[0]=0$, $\infty$ if unreachable; a $prev$ array reconstructs the coins.
• Counting ways is governed by loop order: coins outer, amount inner counts unordered combinations (Coin Change II); amount outer, coins inner counts ordered sequences (Combination Sum IV). Same code, different question: the classic bug.
• Greedy (largest coin first) fails in general ($\{1,3,4\}$, amount $6$: greedy $4+1+1$, optimal $3+3$) but is correct for canonical systems like standard currency; the DP is correct for any denominations.
• Perfect Squares (squares as coins) and Word Break (dictionary words as coins over string prefixes) are the same unbounded-DP shape.