Unbounded Knapsack Patterns

Description

Some knapsack problems let you reuse items: coins you can spend as many times as you like, or rod pieces you can cut in any number. The item dimension of 0/1 knapsack existed only to stop reuse, so it can go. One table indexed by amount, or by length, is enough. What stays subtle is what gets counted: combinations, where 1 + 2 and 2 + 1 are the same, or orderings, where they're different. The loop order decides which one you get.

We'll go from simple to more technical:

1. The pattern: one table by amount, swept upward so items can repeat, with coins in the outer loop for combinations.
2. A second flavor: amount in the outer loop to count orderings.
3. Where unbounded knapsack shows up (making change, cutting stock).
4. What breaks it: loop order, sweep direction, greedy ratios, big counts.

The approach

// Coin Change II: number of combinations (multisets) of coins summing to amount
int change(int amount, int[] coins) {
    int[] ways = new int[amount + 1];
    ways[0] = 1;                                   // one way to make 0: use nothing
    for (int coin : coins) {                       // coins OUTER: each multiset counted once
        for (int s = coin; s <= amount; s++) {     // upward: ways[s - coin] may already use this coin - reuse is allowed
            ways[s] += ways[s - coin];
        }
    }
    return ways[amount];
}

// Rod Cutting: best total price, any number of pieces of each length
int rodCutting(int n, int[] price) {
    int[] best = new int[n + 1];
    for (int len = 1; len <= n; len++)
        for (int piece = 1; piece <= len; piece++)
            best[len] = Math.max(best[len], price[piece - 1] + best[len - piece]);   // best[len - piece] may reuse piece
    return best[n];
}

# Coin Change II: number of combinations (multisets) of coins summing to amount
def change(amount: int, coins: list[int]) -> int:
    ways = [0] * (amount + 1)
    ways[0] = 1                                    # one way to make 0: use nothing
    for coin in coins:                             # coins OUTER: each multiset counted once
        for s in range(coin, amount + 1):          # upward: ways[s - coin] may already use this coin - reuse is allowed
            ways[s] += ways[s - coin]
    return ways[amount]


# Rod Cutting: best total price, any number of pieces of each length
def rod_cutting(n: int, price: list[int]) -> int:
    best = [0] * (n + 1)
    for length in range(1, n + 1):
        for piece in range(1, length + 1):
            best[length] = max(best[length], price[piece - 1] + best[length - piece])   # best[length - piece] may reuse piece
    return best[n]

Sweeping amounts upward is exactly what 0/1 knapsack forbids and unbounded knapsack wants: ways[s - coin] may already include this coin, so the coin can be used again. Coins in the outer loop fix the order in which coins are considered, so every combination is built in one canonical order (all 1s, then all 2s, ...) and counted once. Coin Change I (fewest coins) is the same table with min in place of +.

A second flavor: counting orderings

Swap the loops - amount outside, coins inside - and at each amount every coin may be the last one added. Now 1+2 and 2+1 are different sequences:

int[] ways = new int[target + 1];
ways[0] = 1;
for (int s = 1; s <= target; s++)                  // amount OUTER
    for (int x : nums)
        if (x <= s) ways[s] += ways[s - x];        // ending with x

ways = [0] * (target + 1)
ways[0] = 1
for s in range(1, target + 1):                     # amount OUTER
    for x in nums:
        if x <= s:
            ways[s] += ways[s - x]                 # ending with x

Coins [1, 2] and amount 3: coins-outer counts {1,1,1} and {1,2} - 2; amount-outer counts 1+1+1, 1+2 and 2+1 - 3. Neither is wrong; they answer different questions ("how many ways to pay" versus "how many ways to climb with steps of these sizes"), and the loop order decides which one you get.

Where you'll see it

Cutting stock (how to cut standard-length rolls, boards or pipes into ordered pieces with the least waste), making change and dispensing ATM notes, and packing repeated standard units (servers, containers, ad slots of a few fixed lengths) are unbounded knapsack. Counting orderings shows up in combinatorics of schedules and step sequences.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Coins [1, 2], amount 3. What do coins-outer and amount-outer loops count?

2. Why does the unbounded version sweep amounts upward while 0/1 knapsack sweeps downward?

3. Why is ways[0] = 1?

Key takeaways

• Unbounded knapsack uses one table swept upward, so items can be reused.
• Coins outer counts combinations; amount outer counts orderings.
• ways[0] = 1 (the empty choice) seeds every count.
• Fewest coins and rod cutting are the same table with min or max instead of +.
• Greedy by ratio fails; the DP is O(items * amount), pseudo-polynomial.