6.19

Making Change With at Most k Coins

Pattern · Knapsack + extra dimension 3-D Boolean table O(nvk) 7difficulty
Question — exam style

Here is a variation on the change-making problem. Given an unlimited supply of coins of denominations x[1], x[2], …, x[n], we wish to make change for a value v using at most k coins. For instance, if the denominations are 5 and 10 and k = 6, then we can make change for 55 but not for 65. Give an efficient dynamic-programming algorithm.

Input:Denominations x[1], …, x[n]; integers k and v.
Output:A Boolean: can we make change for v using at most k coins?

Model answer

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

A new constraint ("at most k") ⇒ add a dimension counting coins used. This is the standard move: a bound on a resource becomes a table axis.

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

Same take/skip structure as 6.17, but taking a coin of denomination i also spends one from the coin budget: c → c−1. Base case T(i,b,0)=false for b>0 enforces the "no coins left" wall.

cImplementation analysis
(1) # of subproblems
O(nvk)
(2) Time to fill table
O(nvk) — O(1) per entry
(3) Where answer is extracted
T(n, v, k)
(4) Time to extract
O(1)
Generalizable move — worth its own reflex

Whenever a problem adds "at most / exactly k of something," add a k-sized axis and decrement it on the relevant branch. This is how most exam variants are built: take a canonical recurrence and bolt on one dimension. Recognizing that turns a "novel" problem into a solved one.

Leaner alternative graders often prefer — O(nv), drop the k axis

Instead of a Boolean 3-D table, store the minimum number of coins and compare to k only at the end. k never needs to be a dimension.

C(i, b) = minimum # of coins from denominations x[1..i] summing to exactly b (∞ if impossible) C(i, 0) = 0 for 0 ≤ i ≤ n C(0, b) = ∞ for 1 ≤ b ≤ v If x[i] > b: C(i, b) = C(i-1, b) Else: C(i, b) = min{ C(i-1, b), 1 + C(i, b - x[i]) } for 1 ≤ i ≤ n, 1 ≤ b ≤ v

Extraction: answer is yes iff C(n, v) ≤ k. Subproblems O(nv), fill O(nv), extract O(1). This is strictly tighter (no factor of k) and uses ∞, a legal numeric primitive. Both this and the 3-D Boolean version above earn full credit; lead with this if efficiency is rewarded.

Optional pseudocode not required by Ed #9

A mechanical translation of the leaner 2-D min-coins form (version B).

function ChangeAtMostK(x[1..n], v, k):
    for i = 0 to n: C[i][0] = 0
    for b = 1 to v: C[0][b] = ∞
    for i = 1 to n:
        for b = 1 to v:
            if x[i] > b:
                C[i][b] = C[i-1][b]
            else:
                C[i][b] = min(C[i-1][b], 1 + C[i][b - x[i]])
    return C[n][v] <= k         # true = makeable with ≤ k coins
✎

Try it yourself

worked example + self-test

Min-coins form: C(b)=minc(1+C(b−c)). Answer yes iff C(v) ≤ k.

Worked min-coins table

denominations x = [5, 10] v = 55 k = 6

b │ 0 │ 5 │10 │15 │20 │25 │30 │35 │40 │45 │50 │55 C(b) │ 0 │ 1 │ 1 │ 2 │ 2 │ 3 │ 3 │ 4 │ 4 │ 5 │ 5 │ 6 (non-multiples of 5 are ∞ — unreachable) C(55) = 6. Compare to k = 6.
Answer: C(55) = 6 ≤ 6 → YES. Coin set: one 5 + five 10s (6 coins).  DPV check: 65 needs 7 coins → NOT makeable with k=6.
Self-test fill C(b), compare to k, reveal

denominations x = [1, 5, 10] v = 27 k = 5

Reveal answer
YES — min coins = 5 (two 1s + one 5 + two 10s = 27), and 5 ≤ 5.