0/1 Knapsack DP, in depth: state semantics, a computed worked table, reconstruction in linear memory, the value-indexed DP and a brute-force test oracle

The recurrence and what a cell means

Define dp[i][c] as the best value achievable using only the first i items with total weight at most c. Item i is either left out, giving dp[i-1][c], or taken, which is possible only when w_i is at most c and gives dp[i-1][c - w_i] + v_i. The answer is dp[n][W]. The correctness argument is an exchange on the last item: any optimal subset of the first i items either contains item i or not, and in each case the rest of the subset must be optimal for the smaller problem, or swapping in a better rest would improve the whole.

Because row i reads only row i-1, one array suffices if capacities are visited from W down to w_i, so each read still sees the previous row's value. That gives O(nW) time and O(W) memory. The time is pseudo-polynomial: linear in the numeric value of W, which is exponential in the number of bits needed to write W down. That single fact decides which of the techniques below you need.

def knapsack_value(items, W):
    # items: list of (weight, value) with non-negative ints
    dp = [0] * (W + 1)                  # dp[c] = best value, weight <= c
    for w, v in items:
        if w > W:
            continue                    # can never be taken; skip the loop entirely
        for c in range(W, w - 1, -1):   # downward: each item used at most once
            cand = dp[c - w] + v
            if cand > dp[c]:
                dp[c] = cand
    return dp[W]

Worked example

Use four items, P (weight 2, value 3), Q (3, 4), R (4, 6) and S (5, 8), and capacity 9. The figure shows the array after each item. Follow column 9: after P it is 3; Q lifts it to 7 (P and Q weigh 5); R lifts it to 13 because dp[5] was 7 before R arrived, so P, Q and R together weigh exactly 9 for value 13; S finally reads the old dp[4] = 6 (that is R alone) and makes 14 with R and S.

Two observations from the table generalise. First, a cell's value never decreases from one row to the next, because skipping the new item is always allowed. Second, the final row tells you the best value for every capacity from 0 to 9 at once, which is useful when the capacity is itself a decision, for example choosing a memory budget for a cache and wanting the value curve rather than one point.

Exactly W or at most W

The initialisation decides what the cells mean, and mixing the two meanings is the most common knapsack bug in production code.

In the example, every capacity except 1 is reachable exactly, so the two tables agree everywhere but c = 1, where the at-most table holds 0 and the exact table holds minus infinity. In real data the difference is far larger. If you use exact initialisation and then answer an at-most question, take the maximum over all of dp[0..W], not dp[W]. If you use at-most initialisation for an exact question, you will report a value for a capacity nothing can fill. The feasibility version is the subset-sum problem, where a bitset turns the inner loop into word-wide shifts; see subset sum and partition equal subset sum for that.

Getting the items back

The one-row array gives the optimal value but forgets which items produced it. There are three ways to get the items back, with very different memory costs.

Full table. Keep all n + 1 rows and walk back from dp[n][W]: if dp[i][c] differs from dp[i-1][c], item i was taken and c drops by w_i. Simple, but n = 2,000 and W = 1,000,000 is two billion cells, 8 GB as 32-bit integers.

Take bits. Keep the one-row array for values, and record one bit per item and capacity saying whether the take branch won. That is n x (W + 1) bits, 32 times smaller than the table, about 250 MB for the example above. Walking back is the same: at item i and capacity c, if the bit is set, take it and subtract its weight.

def knapsack_items_bits(items, W):
    n = len(items)
    dp = [0] * (W + 1)
    take = [bytearray((W + 8) // 8) for _ in range(n)]   # packed bits
    for i, (w, v) in enumerate(items):
        row = take[i]
        for c in range(W, w - 1, -1):
            cand = dp[c - w] + v
            if cand > dp[c]:
                dp[c] = cand
                row[c >> 3] |= 1 << (c & 7)
    chosen, c = [], W
    for i in range(n - 1, -1, -1):
        if take[i][c >> 3] >> (c & 7) & 1:
            chosen.append(i)
            c -= items[i][0]
    return dp[W], chosen[::-1]

Divide and conquer. When even the bits are too many, split the items into halves A and B. Run the one-row DP on each half separately to get best_A[c] and best_B[c] for every c. The optimum splits the capacity somehow between the halves, so it equals the maximum over c of best_A[c] + best_B[W - c]. Record the best split c, then solve A with capacity c and B with capacity W - c recursively. A single item is the base case.

def best_row(items, W):
    dp = [0] * (W + 1)
    for w, v in items:
        for c in range(W, w - 1, -1):
            if dp[c - w] + v > dp[c]:
                dp[c] = dp[c - w] + v
    return dp

def knapsack_items_dc(items, W, offset=0, out=None):
    out = [] if out is None else out
    if not items:
        return out
    if len(items) == 1:
        w, v = items[0]
        if w <= W and v > 0:
            out.append(offset)
        return out
    mid = len(items) // 2
    a, b = best_row(items[:mid], W), best_row(items[mid:], W)
    split = max(range(W + 1), key=lambda c: a[c] + b[W - c])
    del a, b                            # keep extra memory O(W), not O(W log n)
    knapsack_items_dc(items[:mid], split, offset, out)
    knapsack_items_dc(items[mid:], W - split, offset + mid, out)
    return out

The cost is better than it looks. The top level runs best_row over all n items with capacity W: n x W work. The next level has two calls with capacities split and W - split, which add to W, and each runs best_row over its n/2 items, so together they cost (n/2)(split) + (n/2)(W - split) = nW/2. Each level costs half the one above, so the whole recursion costs at most 2nW: the same order as the plain DP, with O(W) extra memory plus the recursion stack. It is the knapsack analogue of Hirschberg's trick for sequence alignment.

When W is huge: index by value

When W is huge but values are small, swap the roles (the overview sketches this; here it is in the form the test harness below checks). Let minw[x] be the minimum weight of a subset whose values add up to exactly x. The recurrence is the same shape, minimising instead of maximising, over values from the total value V down to v_i. The answer is the largest x with minw[x] at most W. Time is O(nV), independent of W.

def knapsack_by_value(items, W):
    V = sum(v for _, v in items)
    INF = float("inf")
    minw = [0] + [INF] * V              # exact-value semantics: start from 0 only
    for w, v in items:
        for x in range(V, v - 1, -1):
            if minw[x - v] + w < minw[x]:
                minw[x] = minw[x - v] + w
    return max(x for x in range(V + 1) if minw[x] <= W)

On the example, V = 21 and minw[14] = 9, so the answer is again 14, while minw[15] = 10 is too heavy. With n = 100 items, values below 1,000 and W around 10^9, the weight DP is hopeless and the value DP runs in about 100 x 100,000 = 10^7 steps. If both weights and values are large, you need the exact search methods or the approximation scheme from the overview article; scaling values down is precisely how that approximation works.

Testing against a brute-force oracle

Knapsack code fails quietly: a wrong loop direction lets an item be used twice, an initialisation mix-up returns plausible numbers, and reconstruction can return a subset that does not achieve the reported value. The cure is a brute-force oracle over random small instances, comparing every implementation against exhaustive search and checking the returned subset, not just the value.

import itertools, random

def brute(items, W):
    best = 0
    for r in range(len(items) + 1):
        for combo in itertools.combinations(items, r):
            if sum(w for w, _ in combo) <= W:
                best = max(best, sum(v for _, v in combo))
    return best

for trial in range(5000):
    n = random.randint(0, 10)
    items = [(random.randint(1, 12), random.randint(0, 20)) for _ in range(n)]
    W = random.randint(0, 40)
    want = brute(items, W)
    got, chosen = knapsack_items_bits(items, W)
    assert got == want == knapsack_value(items, W)
    assert len(set(chosen)) == len(chosen)                     # each item once
    assert sum(items[i][0] for i in chosen) <= W               # feasible
    assert sum(items[i][1] for i in chosen) == want            # achieves value
    dc = knapsack_items_dc(items, W)
    assert sum(items[i][1] for i in dc) == want and sum(items[i][0] for i in dc) <= W
    if items:
        assert knapsack_by_value(items, W) == want

Include zero-value items, items heavier than W, W = 0 and the empty list: those edge cases are where most real bugs live.

Failure modes

Two cheap preprocessing steps help often: drop items heavier than W, and divide all weights and W by their greatest common divisor, which can shrink the table dramatically when weights come in round units such as megabytes or minutes.

What to do next

1. Decide whether your question is at most W or exactly W, and write the initialisation to match before writing the loop.
2. Implement the one-row value DP and the brute-force oracle together, and keep the oracle in your test suite.
3. If you need the chosen items, start with take bits; switch to divide and conquer only when n x W bits does not fit.
4. Estimate n x W and n x V before choosing between the weight DP and the value DP.
5. Read the bounded knapsack article when items come with counts, and the dynamic programming overview to apply the same state-design questions to other problems.
6. Re-solve the worked example by hand, then change W to 8 and predict the new answer before running the code.