DP VI — Unbounded Knapsack

Review boundary and corrected contracts

Corrected the worked optimum explanation: capacity 8 is worth 130 via weights 3+3+1+1, not 4+4 (120). Amounts and capacities are nonnegative integers; denominations and weights are positive integers. Counting by denomination requires distinct denominations. Weight/value lists must have equal lengths. Item-outer counts unordered combinations; total-outer counts ordered sequences. A reconstruction now returns an actual minimum-coin witness.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own unbounded knapsack — items in unlimited supply — as the exact mirror of 0/1, and see how Coin Change (min and count), Rod Cutting, and Combination Sum IV are all this one shape.

Series: LeetCode — From Basics to Production-Ready · Session 38 / 65 · Phase 2 · Dynamic programming

Prerequisites

L37 (0/1 knapsack) is mandatory — this session is defined as its opposite. If you cannot yet say "0/1 sweeps capacity backwards", stop and finish L37 first. Everything here is the same table with the inner loop reversed.

Watch first (skim before the session)

Optional resources retained from the original lesson; video availability and contents were not rechecked in this review. The worked explanations below are self-contained.

• Coin Change — Dynamic Programming Bottom Up — Leetcode 322 — NeetCode.
• Coin Change 2 — Unbounded Knapsack — Leetcode 518 — NeetCode.
• Dynamic Programming #2 — Coin change, double counting — Errichto Algorithms.
• Cutting Rod dynamic programming — Tushar Roy.

Why this session exists

Unbounded knapsack is 0/1's mirror image, and reviewers test whether you can tell them apart under pressure. The naked version — "items with weight and value, capacity W, each item usable unlimited times, maximise value" — is rare; the disguises are everywhere: Coin Change (fewest coins), Coin Change 2 (how many ways), Rod Cutting (best price to cut a rod), Combination Sum IV (count ordered ways to reach a target).

Two details carry this session. First: the single-character difference from 0/1 — the capacity loop runs forwards so dp[c-w] already includes the current item, making it reusable. Second, and subtler: for the counting variants, the order of the two loops decides whether you count combinations (item loop outside) or permutations (capacity loop outside). That loop-order distinction is a favourite senior-level probe.

A vending machine, not a backpack

Real: In 0/1 you're a thief with one of each item. In unbounded you're at a vending machine: unlimited stock of each product. If a 25-cent coin helps, you can use as many 25-cent coins as you like. 'Unlimited supply' is the whole difference.

# Coin Change: coins available in unlimited quantity
#   amount = 11, coins = [1, 2, 5]
#   fewest coins = 3  ->  5 + 5 + 1
#   each coin reusable  -> unbounded

Blank-file warm-up

Five minutes, empty file, no notes. Write both cores from memory, and note the one flipped line:

unbounded value :  for c from w to W:            # FORWARDS (reusable)
                        dp[c] = max(dp[c], dp[c-w] + v)
 
coin change min :  for c from coin to amount:    # FORWARDS
                        dp[c] = min(dp[c], dp[c-coin] + 1)

If the loop direction wobbles against L37, drill the pair: "one-of-each backwards, unlimited forwards."

From first principles

Question: Why does forward capacity iteration make items reusable, and how is that different from 0/1?

Premise: For the zero-initialised value table below, dp[c] is the best value with total weight at most c; unused capacity is allowed. Coin-change tables instead describe an exact amount c, with impossible positive amounts initially unreachable.

Because: A target-outer optimisation can consider every item at each capacity. In the item-outer combination counter, however, the current item prefix is an implicit state: after processing a coin, dp[c] counts combinations using only coins processed so far.

Premise: For item (w, v): dp[c] = max(dp[c], dp[c-w] + v), iterating c from w up to W.

Because: When we reach c, dp[c-w] has ALREADY been updated for this same item in this pass, so taking the item again is allowed — that's exactly 'reuse'.

Premise: Contrast 0/1: there we iterate c downwards so dp[c-w] reflects the state BEFORE the current item, forbidding reuse.

Because: With items outermost and the same state and initialisation, sweep direction decides whether the take branch reads the previous item row or the current one. This rule does not license swapping arbitrary loops or mixing exact-fill and at-most-capacity base cases.

Premise: For the take-branch in the recursive framing, unbounded STAYS on the same item index after taking; 0/1 MOVES to the next index.

Because: Staying lets you take the same item again; moving on forbids it. This mirrors the loop direction in the iterative version.

Conclusion: Unbounded knapsack = 0/1 with the capacity loop reversed (forwards). The take-branch reuses the current item instead of consuming it.

Unbounded value maximisation (the naked form): zero initial values allow choosing nothing. For example, weights [3], values [5], capacity 4 returns 5 with one unit unused; it does not claim weight 4 is reachable. An exact-fill value variant would instead seed only dp[0] to 0 and all positive capacities to negative infinity.

def unbounded_knapsack(weights: list[int], values: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for c in range(1, W + 1):
        for w, v in zip(weights, values):
            if w <= c:
                dp[c] = max(dp[c], dp[c - w] + v)   # reuse allowed: dp[c-w] may include this item
    return dp[W]
 
assert unbounded_knapsack([1, 3, 4], [15, 50, 60], 8) == 130   # 3+3+1+1 -> 50+50+15+15

Either loop order works for the max-value unbounded problem because both dp[c] and dp[c-w] end up reflecting reuse. But for the counting variant (Coin Change 2), loop order changes the ANSWER — coins-outer counts combinations, amount-outer counts permutations. Never carry the "order doesn't matter" habit from max-value into counting.

Coin Change — the canonical disguise

Fewest coins to make an amount, coins reusable — unbounded knapsack minimising count.

def coin_change(coins: list[int], amount: int) -> int:
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0                                 # 0 coins make amount 0
    for c in range(1, amount + 1):
        for coin in coins:
            if coin <= c:
                dp[c] = min(dp[c], dp[c - coin] + 1)   # forwards: reuse coins
    return dp[amount] if dp[amount] != INF else -1
 
assert coin_change([1, 2, 5], 11) == 3       # 5 + 5 + 1
assert coin_change([2], 3) == -1             # impossible
assert coin_change([1], 0) == 0

• Complexity: O(amount · len(coins)) time, O(amount) space.
• Follow-up: return the actual coins (parent pointers), or count the number of ways (Coin Change 2), which flips it to a counting problem with a loop-order subtlety.

Coin Change 2 — where loop order bites

Count the number of combinations of coins that make the amount. Coins outer, amount inner:

def coin_change_2(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1                                 # one way to make 0: take nothing
    for coin in coins:                        # coins OUTER  -> counts combinations
        for c in range(coin, amount + 1):     # forwards -> reusable
            dp[c] += dp[c - coin]
    return dp[amount]
 
assert coin_change_2(5, [1, 2, 5]) == 4      # {5},{2,2,1},{2,1,1,1},{1x5}
assert coin_change_2(3, [2]) == 0

If you swap the loops (amount outer, coins inner) you count permutations instead — [1,2] and [2,1] become distinct — which is Combination Sum IV, a different problem. This is the senior probe.

Name: 0/1's mirror, with a loop-order twist for counting

Picture: Same grid as 0/1 knapsack, but the sweep runs left-to-right so an item can feed itself. For MAX-VALUE the loop order is free. For COUNTING, put the item loop OUTSIDE to count combinations (order-insensitive), or the capacity loop outside to count permutations (order-sensitive).

• Unlimited supply ⇒ capacity loop FORWARDS.

• Fewest items to hit a target ⇒ dp[c] = min(dp[c], dp[c-w] + 1).

• Count COMBINATIONS ⇒ items outer, capacity inner.

• Count PERMUTATIONS ⇒ capacity outer, items inner (Combination Sum IV).

Trigger: A target/budget with items in unlimited supply — coins, rod lengths, step sizes.

Memory hook

"Unlimited, sweep forwards — coins outside for combos, target outside for orders." The first clause pairs with L37's "one of each, sweep backwards." The second clause encodes the only genuinely tricky bit of this session — the counting loop order. Recite the full pair (L37 + L38) as one sentence and both knapsacks are locked.

Myth: Coin Change and Coin Change 2 are the same problem with a different return value, so the same loop structure works.

Truth: Coin Change (fewest coins) is order-agnostic and loop order is free. Coin Change 2 (count ways) REQUIRES coins-outer to count combinations; capacity-outer counts permutations and can give a larger, wrong answer.

Why: For amount 3, coins [1,2]: combinations = {1+1+1, 1+2} = 2. Permutations = {1+1+1, 1+2, 2+1} = 3. Same DP array, different loop nesting, different count.

Test: Before writing a counting knapsack, ask: 'do [1,2] and [2,1] count as one way or two?' One way ⇒ coins outer. Two ways ⇒ capacity outer.

What reviewers actually ask

• LC322 · Coin Change — Practice selection. Fewest coins for an amount. Probe: recognising unbounded knapsack, the forward loop, and the "impossible ⇒ -1" sentinel. Follow-up: reconstruct the coins, or handle huge amounts.
• LC518 · Coin Change 2 — Practice selection. Count combinations. Probe: the coins-outer loop order and why it counts combinations not permutations. This is the discriminating question.
• LC377 · Combination Sum IV — Practice selection. Despite the name, it counts permutations (ordered), so it's the capacity-outer twin of Coin Change 2. Probe: can you articulate that the loop order flips the meaning?
• LC279 · Perfect Squares — Practice selection. Fewest perfect squares summing to n = Coin Change with coins = {1,4,9,16,...}. Probe: seeing the reduction, and the sqrt bound on the coin set.
• LC983 · Minimum Cost For Tickets — Practice selection. An unbounded-flavoured DP over days with 1/7/30-day passes. Probe: state as cost-to-cover-up-to-day-i with reusable passes.
• LC518 vs LC377 side by side — reviewers sometimes ask both to see if you truly understand loop order versus having memorised one template.

Escalation ladder: fewest items (min) → count combinations → count permutations → reconstruct the multiset. The middle two are the same DP with the loops swapped — the whole point of the session.

Combination Sum IV — the loop-order twin

Plain words. Given distinct positive integers nums and a target, count the number of ordered sequences that sum to the target. The name says "combination"; the examples make clear it means permutations. Read the examples to settle the ordering contract rather than inferring it from the title.

The insight. Everything about the array and the recurrence is identical to Coin Change 2. Only the nesting flips. Ask "how many ordered ways end with this number?" and you get a natural target-outer loop:

def combinationSum4(nums: list[int], target: int) -> int:
    dp = [0] * (target + 1)
    dp[0] = 1                          # one ordered way to reach 0: the empty sequence
    for t in range(1, target + 1):     # TARGET outer -> order matters
        for x in nums:                 # every number gets a chance to be the LAST one
            if x <= t:
                dp[t] += dp[t - x]
    return dp[target]
 
assert combinationSum4([1, 2, 3], 4) == 7   # 1111,112,121,211,13,31,22

Compare it line by line with the combinations version and the only difference is which for is on the outside:

def change(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:                    # COINS outer -> order does not matter
        for t in range(c, amount + 1): # forward -> coin reusable
            dp[t] += dp[t - c]
    return dp[amount]
 
assert change(4, [1, 2, 3]) == 4            # 1111, 112, 22, 13

Seven versus four on the same inputs. That gap is the entire lesson, and being able to produce both numbers on demand is the cleanest way to prove you understand loop order rather than having memorised a template.

The follow-up they escalate to: "what if negative numbers were allowed?" With both +1 and -1, a reachable target has infinitely many sequences: insert arbitrarily many zero-sum pairs. Not every negative-valued set has this property, but increasing total is no longer a valid dependency order. A length cap makes enumeration finite; then use a state such as (length, total), including negative intermediate totals, rather than the positive-only array above.

Goal: Make Coin Change return the actual coins used, not just the count.

Hint: Keep a parallel choice array: when dp[t] improves via coin c, record choice[t] = c. Then walk backwards from the amount, emitting choice[t] and jumping to t - choice[t] until you reach 0.

def coin_change_with_coins(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    choice = [None] * (amount + 1)
    for t in range(1, amount + 1):
        for c in coins:
            if c <= t and dp[t - c] + 1 < dp[t]:
                dp[t] = dp[t - c] + 1
                choice[t] = c
    if dp[amount] == INF:
        return None
    result = []
    while amount:
        coin = choice[amount]
        result.append(coin)
        amount -= coin
    return result

Tradeoff

Decision: When a counting-knapsack problem appears, how do you decide the loop nesting?

Name: Items (coins) outer, capacity inner

Gain: Counts COMBINATIONS — order-insensitive; correct for 'how many sets of coins make X' (Coin Change 2).

Cost: Wrong if the problem actually treats [1,2] and [2,1] as distinct.

Pick: when order does NOT matter (a multiset of items).

Name: Capacity (target) outer, items inner

Gain: Counts PERMUTATIONS — order-sensitive; correct for Combination Sum IV / step-climbing counts.

Cost: Over-counts if the problem wants combinations.

Pick: when order DOES matter (sequences, ordered ways to reach a total).

Verdict: First answer the English question: is [1,2] the same as [2,1]? Same ⇒ items outer. Different ⇒ target outer. Decide this BEFORE writing code; it is the single most tested nuance here.

In practice

Rod Cutting maps piece length to weight and sale price to value: for length 4 and prices [1, 5, 8, 9] for lengths 1–4, two length-2 pieces earn 10, beating the uncut price 9. If all rod material must be sold, use an exact-fill state (unreachable lengths start at negative infinity); the at-most-capacity table is appropriate when waste is allowed. General cutting-stock problems can also impose demands and limited stock, so this reduction covers the single-rod unlimited-piece-type model, not every cutting-stock problem. Ticket passes are reusable choices too, but their state tracks days covered, not just a sum of pass durations.

You are ready to move on when you can

• Write unbounded knapsack from memory with the capacity loop forwards, and say why forwards = reusable.

• State the one-character difference from 0/1 knapsack.

• Write Coin Change (min) and Coin Change 2 (count) and explain the loop order for the counting one.

• Explain why Combination Sum IV counts permutations while Coin Change 2 counts combinations.

• Reduce Perfect Squares to Coin Change with square 'coins'.

Self-check (answer follows each question).

Check yourself

Q: What single change turns 0/1 knapsack into unbounded knapsack?

A: Reverse the inner capacity loop to iterate forwards (low → high), so dp[c-w] already includes the current item and it can be reused.

Q: In Coin Change 2, why must coins be the OUTER loop?

A: Coins-outer fixes an order in which items are considered, so each combination is counted once (order-insensitive). Capacity-outer would count [1,2] and [2,1] separately — permutations.

Q: Combination Sum IV is named 'combination' but counts what?

A: Permutations — ordered ways to reach the target. Its loop nesting is capacity-outer, items-inner: the opposite of Coin Change 2.

Q: Why does max-value unbounded knapsack work with either loop order, but counting doesn't?

A: Positive weights make each take depend on a smaller capacity. Target-outer considers every possible last item; item-outer considers every multiset via its largest processed item. Both cover every feasible selection, and repeated orderings do not change a min/max. Addition does count those repeated orderings, so the counting loops represent different objects.

Q: How does Perfect Squares reduce to unbounded knapsack?

A: Treat the perfect squares 1,4,9,...,≤n as unlimited 'coins' and find the fewest that sum to n — exactly Coin Change (min) on that coin set.

Stretch: The coin set has only O(sqrt(n)) elements, so it runs in O(n·sqrt(n)).

Practice queue

Solve in this order; log each as cold / warm / hint / failed.

1. LC322 Coin Change — unbounded min, the gateway.
2. LC518 Coin Change 2 — count combinations (coins outer).
3. LC377 Combination Sum IV — count permutations (target outer); feel the flip.
4. LC279 Perfect Squares — Coin Change with square coins.
5. LC983 Minimum Cost For Tickets — unbounded-flavoured day DP.
6. LC139 Word Break — unbounded reachability where the "coins" are dictionary words and the capacity axis is string position.
7. LC518 and LC377 back to back, from a blank file — write both in one sitting and confirm you get 4 and 7 on target 4 with {1,2,3}.

Spaced-repeat anchors: LC322 and LC518. LC322 carries the forward-loop minimum; LC518 carries the loop-order nuance that this entire session exists for. Re-solve both at +7d and again at +21d, and on the +21d pass write LC377 immediately afterwards to re-test the flip.

• Unbounded knapsack = 0/1 with the capacity loop FORWARDS; each item reusable.

• Learn it as a matched pair with L37: 'one of each, backwards' vs 'unlimited, forwards'.

• For counting: items outer ⇒ combinations (Coin Change 2); target outer ⇒ permutations (Combination Sum IV).

• Coin Change, Perfect Squares, Rod Cutting are all this one shape in disguise.

Corrective source notes

• Knapsack Problem - Algorithms for Competitive Programming — Zero-one knapsack row compression scans capacity downward so the dependency still refers to the previous item row. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.