Bounded Knapsack, in depth

Definition and a worked example

Given n item types and a capacity W, choose counts t_i with 0 ≤ t_i ≤ k_i so that the total weight Σ t_iw_i is at most W and the total value Σ t_iv_i is as large as possible. Weights and W are non-negative integers, which is what makes a table indexed by capacity possible.

Two neighbouring questions use the same machinery. Feasibility asks which totals can be hit exactly, for example which amounts a purse holding k_i coins of each denomination can pay. Counting asks how many count vectors hit a total exactly. Each gets its own fast method below.

The worked example used throughout has three item types and W = 10:

Unlimited C would give 15 from five copies. The stock of four rules that out, and the bounded optimum is 14, reached either by two A and two C (weight 10) or by one B and three C (weight 10). Exactly four count vectors fill the knapsack to 10: (2,0,2), (0,1,3), (0,2,1) and (2,1,0). Each method below must reproduce these numbers.

The direct recurrence and its cost

Let dp_i[c] be the best value using the first i items within capacity c. Then dp_i[c] = max over t from 0 to min(k_i, c / w_i) of dp_i-1[c - t·w_i] + t·v_i. With a single array swept from high capacity to low, every read of a smaller index still holds the previous item's row, so no copy is needed:

NEG = float("-inf")

def bounded_naive(items, W):            # items: list of (w, v, k)
    dp = [0] + [NEG] * W                 # dp[c]: best value with weight exactly c
    for w, v, k in items:
        for c in range(W, -1, -1):       # high to low: dp[c - t*w] is still last row
            for t in range(1, k + 1):
                if t * w > c:
                    break
                dp[c] = max(dp[c], dp[c - t * w] + t * v)
    return max(dp)

The array holds the best value for weight exactly c, with unreachable totals at minus infinity, which reconstruction needs later. Initialising every cell to 0 instead gives weight at most c, also correct for the maximum.

The cost is O(W · Σ k_i). With 100 item types, stocks around 1,000 and W = 100,000 that is ten billion inner steps. Copying item i into k_i separate 0/1 items costs exactly the same.

Binary splitting, and why it covers every count

The standard improvement, also in the site's general knapsack article, replaces k copies with bundles of sizes 1, 2, 4, … plus a remainder (for k = 13: 1, 2, 4, 6), each a single 0/1 item with weight m·w and value m·v.

Why it is correct: bundles 1, 2, …, 2^p-1 reach every count from 0 to 2^p - 1 (binary notation). The remainder r = k - (2^p - 1) is at most 2^p, so adding it extends the range to every count from 0 to k with no gaps, and no subset exceeds k.

def bundles(k):
    out, p = [], 1
    while k > 0:
        take = min(p, k)                 # last bundle is the remainder
        out.append(take)
        k -= take
        p *= 2
    return out                           # bundles(13) == [1, 2, 4, 6]

The cost drops to O(W · Σ log k_i), usually enough in practice, and it reuses a plain 0/1 loop. It only works for max or min objectives: different bundle subsets can produce the same count, so using it to count combinations double-counts.

O(nW) with a monotone queue

In the naive recurrence for an item of weight w, capacity c only reads cells c - w, c - 2w, …, all in the same residue class modulo w. Write c = r + j·w. Taking j - s copies reads old cell s, so new[r + j w] = max over s in [j - k, j] of old[r + s w] + (j - s) v. Pulling j·v outside gives the form in the diagram.

The quantity inside the max depends only on s, and the window [j - k, j] slides right by one as j grows. That is a sliding-window maximum, which a monotone deque answers in amortised O(1) per step: keep indices with decreasing keys, drop the front when it leaves the window, and pop from the back any index no better than the newcomer. Each capacity is visited once per item, so the algorithm is O(nW) whatever the stocks.

from collections import deque

def bounded_monotone(items, W):
    dp = [0] + [NEG] * W
    for w, v, k in items:
        old = dp[:]                          # the window must read the previous row
        for r in range(min(w, W + 1)):
            q = deque()                      # indices s, keys old[r+s*w] - s*v decreasing
            j = 0
            while r + j * w <= W:
                key = old[r + j * w] - j * v
                while q and q[0] < j - k:    # left the window
                    q.popleft()
                while q and old[r + q[-1] * w] - q[-1] * v <= key:
                    q.pop()                  # dominated by the newcomer
                q.append(j)
                s = q[0]
                dp[r + j * w] = old[r + s * w] - s * v + j * v
                j += 1
    return max(dp)

The most common bug is computing keys from dp instead of a copy of the previous row. The code writes cell r + j w and later reads it again as an older window member; if that read sees the new value, the item is reused beyond its stock. Keeping old costs one O(W) copy per item. Minus infinity is a safe key: an unreachable cell never wins while a reachable one is in the window.

Tracing item A (w = 3, k = 2) from the empty start, class r = 0: the new values at c = 0, 3, 6, 9 are 0, 4, 8 and -∞, because reaching 9 needs three copies and the window for j = 3 no longer contains j = 0. That is exactly where an unbounded loop would wrongly write 12.

Feasibility only: the used-count trick

When only reachability matters, there is a simpler O(nW) method with no deque. Process one item at a time, sweeping capacities upward as in unbounded knapsack, but record for each newly reached cell how many copies of the current item it took to get there. A cell may be extended by one more copy only if that count is below the stock:

def reachable_totals(items, W):
    ok = [True] + [False] * W
    for w, _, k in items:
        used = [0] * (W + 1)                 # copies of THIS item used to reach c
        for c in range(w, W + 1):
            if not ok[c] and ok[c - w] and used[c - w] < k:
                ok[c] = True
                used[c] = used[c - w] + 1
    return ok

This is safe because a cell already reachable before this item keeps used[c] = 0, and a newly reached cell gets the fewest copies possible, since the upward sweep reaches it from the smallest count. The guard not ok[c] is essential: without it a cell reachable anyway would be overwritten with a larger count and block valid extensions. This is the standard solution to the bounded coin problem.

Counting combinations with a window sum

Counting count vectors is a different algebra. Max becomes plus, and the window maximum becomes a window sum, which needs no deque at all: within each residue class keep a running sum of the last k + 1 old cells. The recurrence is ways_new[r + j w] = Σ over s from j - k to j of ways_old[r + s w].

def count_ways(items, W, mod=10**9 + 7):
    ways = [1] + [0] * W                     # one way to make 0: take nothing
    for w, _, k in items:
        new = [0] * (W + 1)
        for r in range(min(w, W + 1)):
            window, j = 0, 0
            while r + j * w <= W:
                c = r + j * w
                window += ways[c]
                if j > k:                    # drop the cell k+1 steps back
                    window -= ways[c - (k + 1) * w]
                new[c] = window % mod
                j += 1
        ways = new
    return ways[W]

On the worked example this returns 4 for W = 10, matching the four vectors listed earlier. The subtraction reads the old row, so the new array must be separate. In fixed-width languages reduce the window consistently modulo the prime; mixing reduced and unreduced subtractions produces negative counts. The same window-sum idea is the efficient form of the count variants discussed in coin change, two variants and counting subset sums.

Recovering how many of each item

Production callers rarely want only a number; they want to know how many of each item to pick. Reconstruction needs the row for every item, or at least enough to replay decisions. With full rows kept, walk backwards: at item i and capacity c, find a count t with dp_i-1[c - t w] + t v = dp_i[c], record t, and move to c - t w.

def counts_from_rows(items, rows, c):
    # rows[i][c]: best value with exactly weight c using items[:i]
    counts = [0] * len(items)
    for i in range(len(items), 0, -1):
        w, v, k = items[i - 1]
        for t in range(k + 1):
            if t * w <= c and rows[i - 1][c - t * w] + t * v == rows[i][c]:
                counts[i - 1] = t
                c -= t * w
                break
    return counts

Start c at the capacity holding the maximum. On the worked example this returns (2, 0, 2) for value 14, one of the two optima; scan t downwards to prefer more copies. Keeping n + 1 rows costs O(nW) memory; storing only the chosen t per item and capacity in a byte array is smaller. Floating-point values break the equality test, so scale them to integers first.

Choosing a method, and failure modes

All the table methods are pseudo-polynomial: linear in the value W, not in its bit length. With W in the billions you need the general article's techniques or an integer programming solver. If weights share a common factor, divide W and every weight by the gcd first.

Failure modes worth testing for explicitly:

• Reading the current row in the monotone method. Items exceed their stock. Test with one item, k = 1 and W = 2w: the answer must be v, not 2v.
• Using binary splitting for counting. Counts come out too high.
• Zero-weight items. The residue loop range(min(w, W + 1)) is empty for w = 0 and the item is silently dropped. Handle them up front.
• Integer overflow. Σ t v can exceed 32 bits long before W is large; use 64-bit values.
• ‘At most’ versus ‘exactly’. Mixing the two initialisations fails only when W cannot be filled exactly.

What to do next

The brute force is ten lines; the bugs are all in the fast versions. For the broader picture of state design behind these recurrences, see dynamic programming in depth; for the contrast with divisible goods, fractional knapsack shows when greedy is optimal.

1. Implement the naive loop as an oracle and keep it in your test suite.
2. Compare binary splitting and the monotone-queue method against it on thousands of small random instances.
3. Add the edge tests above: k = 0, k = 1 with W = 2w, zero-weight items, and a capacity that cannot be filled exactly.
4. Document whether your function means ‘exactly W’ or ‘at most W’.
5. If you need counts, use the window sum; if you need the item list, store per-item choices and reconstruct.
6. Divide by the gcd of the weights and estimate memory before scaling up.