Unbounded Knapsack Explained: One Forward Loop, Unlimited Copies

The 0/1 knapsack lets you take each item at most once. Its sibling, the unbounded knapsack, lets you take as many copies as you like. In the one-row version, the only code difference is the direction of one loop, which is why interviewers like it: it separates a memorised template from knowing what each cell means. Rod cutting, coin change and cutting stock are all this problem in different clothes.

The problem it solves

You have a bag of capacity W and item types, each with a weight and a value. Every type is available in unlimited supply. Choose how many of each to take so the total weight fits and the total value is as large as possible.

With weights 3, 4 and 5 worth 30, 50 and 60 and a capacity of 8, the best 0/1 answer takes the 3 and the 5 for 90. The unbounded answer takes the 4 twice for 100. Trying every combination of counts grows exponentially; the table below does it in O(n × W).

The intuition

Let best[c] be the most value that fits in capacity c. Look at a full bag of capacity c and ask a single question: which item went in last? If it was an item of weight w and value v, the rest of the bag is an optimal bag of capacity c - w, so the total is best[c - w] + v. Try every item and keep the maximum:

best[c] = max(best[c], best[c - w] + v) for every item with w no larger than c.

Stock is unlimited, so best[c - w] may already contain this same item, and that is fine. Fill the cells from capacity 1 upwards and every cell reads only cells already finished.

Now compare with 0/1 in its one-row form. There, the outer loop runs over items and the inner loop runs capacity backwards, from W down to w, so when best[c] reads best[c - w], that smaller cell has not been updated for this item yet and each item is counted at most once. Run the same inner loop forwards, and best[c - w] has already been improved by this item, so the item can be added again, and again. That single flip is the whole difference between the two problems, as the 0/1 knapsack article shows from the other side. The patterns cheat sheet groups both variants under knapsack DP.

Watch it run

The animation lays out one cell per capacity. Stock is unlimited, so the only question each cell asks is which item goes in last. Capacities 1 and 2 are smaller than the lightest item, so nothing fits and those cells stay 0. At capacity 3 it puts in the weight-3 item and reuses best[0] = 0, for 30. Capacity 4 takes the weight-4 item on top of best[0] for 50, and capacity 5 takes the weight-5 item for 60. Capacity 6 puts in the weight-3 item and reuses best[3] = 30, so a second copy of the same item is already in play, for 60. Capacity 7 adds the weight-3 item to best[4] = 50, for 80. Capacity 8 adds the weight-4 item to best[4] = 50, for 100. The final frame lands on that 100, two weight-4 items: the cell it read, best[4], already contained one of them, and that is the whole difference from 0/1, which tops out at 90.

The code

The lesson's table for the animation's items. Each cell is the best value for that capacity:

weights = [3, 4, 5]
values = [30, 50, 60]
cap = 8

def unbounded(weights, values, cap):
    best = [0] * (cap + 1)
    for c in range(1, cap + 1):                       # capacities in increasing order
        for w, v in zip(weights, values):
            if w <= c:
                best[c] = max(best[c], best[c - w] + v)   # best[c - w] may already hold this item
    return best

best = unbounded(weights, values, cap)
print(best)                                           # [0, 0, 0, 30, 50, 60, 60, 80, 100]

The one-loop difference, side by side. Both functions loop over items outside and capacity inside; the only change is the direction of the inner loop, and it moves the answer from 90 to 100:

def zero_one(weights, values, cap):
    best = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):               # backwards: best[c - w] is still "without this item"
            best[c] = max(best[c], best[c - w] + v)
    return best[cap]

def item_loop_forwards(weights, values, cap):
    best = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(w, cap + 1):                   # the same loop, only the direction flipped
            best[c] = max(best[c], best[c - w] + v)
    return best[cap]

print(zero_one(weights, values, cap), item_loop_forwards(weights, values, cap))   # 90 100

Reading the answer back: remember the last item for every cell, then walk back from the full capacity. The same function solves rod cutting, where a piece of length k sells for a price and the rod's length is the capacity:

def with_choices(weights, values, cap):
    best, last = [0] * (cap + 1), [None] * (cap + 1)
    for c in range(1, cap + 1):
        for w, v in zip(weights, values):
            if w <= c and best[c - w] + v > best[c]:
                best[c], last[c] = best[c - w] + v, (w, v)   # the item that went in last
    picked, c = [], cap
    while c > 0 and last[c] is not None:
        picked.append(last[c])
        c -= last[c][0]
    return best[cap], picked

print(with_choices(weights, values, cap))             # (100, [(4, 50), (4, 50)])

prices = {1: 2, 2: 5, 3: 7, 4: 8}                      # rod cutting: a piece of length k sells for prices[k]
rod = unbounded(list(prices), list(prices.values()), 7)
print(rod[7], [w for w, _ in with_choices(list(prices), list(prices.values()), 7)[1]])   # 17 [1, 2, 2, 2]

Coin change is the same recurrence with min instead of max and 1 per coin instead of a value. Six from coins 1, 3 and 4 takes two coins; three cannot be made from 5 and 7:

def fewest_coins(coins, amount):
    INF = float("inf")
    fewest = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                fewest[a] = min(fewest[a], fewest[a - coin] + 1)
    return fewest[amount] if fewest[amount] != INF else -1

print(fewest_coins([1, 3, 4], 6), fewest_coins([5, 7], 3))   # 2 -1

Checked on 1,000 seeded random instances against brute force, every count of every item for the unbounded version and every subset for 0/1; the items read back must fit and add up to the reported value:

import random

def brute_unbounded(weights, values, cap):
    """Try every count of every item: a plain search over all multisets that fit."""
    def go(i, room):
        if i == len(weights):
            return 0
        return max(k * values[i] + go(i + 1, room - k * weights[i])
                   for k in range(room // weights[i] + 1))
    return go(0, cap)

def brute_zero_one(weights, values, cap):
    best = 0
    for mask in range(1 << len(weights)):
        chosen = [i for i in range(len(weights)) if mask >> i & 1]
        if sum(weights[i] for i in chosen) <= cap:
            best = max(best, sum(values[i] for i in chosen))
    return best

random.seed(24)
ok = True
for _ in range(1000):
    n = random.randint(1, 5)
    ws = [random.randint(1, 9) for _ in range(n)]
    vs = [random.randint(1, 60) for _ in range(n)]
    cap = random.randint(0, 25)
    want = brute_unbounded(ws, vs, cap)
    got, picked = with_choices(ws, vs, cap)
    ok &= unbounded(ws, vs, cap)[cap] == item_loop_forwards(ws, vs, cap) == got == want
    ok &= sum(w for w, _ in picked) <= cap and sum(v for _, v in picked) == got
    ok &= zero_one(ws, vs, cap) == brute_zero_one(ws, vs, cap)
print(ok)                                             # True

The complexity

• Time: O(n × W) for n item types and capacity W. That is pseudo-polynomial: it grows with the numeric value of W, not with the number of digits needed to write it, so a capacity of a billion is out of reach.
• Space: O(W) for the one row, plus O(W) more to read the chosen items back.
• Loop order: capacity outside and items inside, or items outside and capacity forwards inside, give the same maximum.

Where it goes wrong

• The wrong loop direction. Backwards is 0/1, forwards is unbounded; mixing them up silently changes the problem.
• Counting combinations with the loops swapped. For the maximum it does not matter, but when counting the number of ways, items outside counts combinations and capacity outside counts ordered sequences; see coin change II.
• Initialising with 0 when the bag must be exactly full. Unreachable capacities need minus infinity.
• Greedy by value per weight. Taking the best ratio first fails here too. A weight-5 item worth 11 beats a weight-3 item worth 6 on ratio, but in a bag of 9 the greedy pick of one of each makes 17, while three of the weight-3 item make 18.

When it shows up in interviews

Rarely by name. It arrives as coin change, rod cutting, "minimum number of perfect squares that sum to n", cutting stock, or "maximum value with unlimited supply". The tell is reuse: if an item or a step can be chosen again, it is the forward loop. If each item can be used once, as in partition equal subset sum, it is the backward loop.

How to say it in an interview

"best[c] is the most value that fits in capacity c. For each capacity I ask which item went in last, and take the maximum of best[c - w] + v over the items that fit. Because supply is unlimited, best[c - w] is allowed to contain the same item, so I fill capacities in increasing order, which is the forward loop; the backward loop would be 0/1 knapsack. It is O(n × W) time and O(W) space, and if I need the items themselves I store the last item chosen at each capacity and walk back from W."