Pseudo-Polynomial Knapsack: Why the Capacity State Is Not Polynomial

The 0/1 knapsack problem takes n items with weights w_i and values v_i and a capacity W, and asks for the maximum total value of a subset whose total weight does not exceed W. The dynamic program fills a table indexed by item and remaining capacity. Its running time is O(nW), which is a product of two numbers read directly off the input. That looks polynomial, and the problem is NP-hard. Both statements are true, and the resolution — that W is a magnitude rather than a length — is the single most consequential fact about this DP.

The recurrence and its table

Let best[i][c] be the maximum value achievable using a subset of the first i items with capacity c remaining. Then

best[0][c] = 0                                   for all c
best[i][c] = best[i-1][c]                        if w_i > c
best[i][c] = max(best[i-1][c], v_i + best[i-1][c - w_i])   otherwise

Each cell depends on two cells in the previous row. The table has (n+1)(W+1) cells and each is computed in constant time, so the total is Θ(nW) arithmetic operations. The answer is best[n][W].

The recurrence embodies the sufficiency argument from the state-design article in its simplest form. Once the first i items have been decided, the only fact about that history that constrains the rest is how much capacity is left. The chosen subset’s identity does not matter, only its total weight, which is why a single integer per cell suffices.

Where the polynomial claim breaks

Complexity is measured against the length of the input encoding. Writing the capacity W in binary takes ⌈log₂(W+1)⌉ bits. A table with W columns therefore has 2^b columns for an input of b bits, which is exponential in the input length. The bound O(nW) is polynomial in the value of W and exponential in its representation, and bounds of that shape are called pseudo-polynomial.

The distinction is not academic. A capacity of 10^9 written as a decimal literal occupies ten characters; the table would need on the order of 10^9 cells per item row, which at four bytes per cell is 4 GB for a single row and cannot be allocated on ordinary hardware. Ten characters of input producing a multi-gigabyte requirement is the practical signature of a pseudo-polynomial algorithm.

The standard hardness result is stronger than “no known polynomial algorithm”. Knapsack is NP-complete in the weak sense: it is NP-complete when the weights are encoded in binary, but if the weights are restricted to be bounded by a polynomial in n, the DP runs in polynomial time in the input length. Problems that remain NP-complete even with such a restriction are strongly NP-complete; 3-partition is the canonical example, and bin packing inherits the property. The gap between weak and strong hardness is precisely the gap between problems that admit pseudo-polynomial DPs and those that do not.

The two-dimensional table collapses to one row

The recurrence reads only the previous row, so the full table is unnecessary for computing the value. Two rows of W+1 cells suffice, and with care one row suffices if it is traversed in the right direction.

def knapsack_01(weights, values, capacity):
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        # Descending order keeps `best[c - w]` from the previous item round.
        for c in range(capacity, w - 1, -1):
            if best[c - w] + v > best[c]:
                best[c] = best[c - w] + v
    return best[capacity]

The descending loop is the whole trick. In the 1D array, best[c - w] must refer to the state before the current item was considered. Iterating c downward guarantees that index c - w has not yet been overwritten in this round. Iterating upward would allow item i to be used repeatedly, which computes the unbounded knapsack instead — a correct answer to a different problem, and a silent one, since no input validation can distinguish the two intentions. The guard range(capacity, w - 1, -1) is the other half of the loop: it stops before the indices below w are visited, where c - w would be negative and index from the end of the list rather than from the start.

This is a general pattern rather than a knapsack peculiarity. Whenever the state graph’s edges go from row i-1 to row i at a lower or equal column index, the row can be reused provided the columns are visited in the order that keeps the source cell untouched. The direction is a property of the transition, not a convention: 0/1 knapsack needs descending, unbounded knapsack needs ascending, and edit distance needs both dimensions retained because its transitions read [i-1][j-1], [i-1][j], and [i][j-1], as described in edit distance and two-dimensional tables.

The space reduction costs reconstruction

A one-row table holds the optimum value and nothing else. The chosen subset is not recoverable from it, because the information about which rows made which decisions was overwritten. Restoring reconstruction requires either the full table, O(nW) cells, or a divide-and-conquer scheme that splits the item list in half, computes forward and backward half-tables at the split point, finds the capacity allocation that maximizes the sum, and recurses on each half. The latter keeps O(W) space and costs O(nW log n) time — the same trade as Hirschberg’s algorithm for sequence alignment.

There is a middle option: store one bit per cell recording whether the item was taken. That is the decision table compressed to n(W+1) bits (8× smaller than one byte per cell, 32× smaller than four bytes per cell) and keeps the same W+1 columns as the value table; the state, not the decision bit, is what the one-row reduction discards. The saving costs bit-manipulation overhead in the inner loop. For n = 1000 and W = 10^5 that is 12.5 MB rather than the 400 MB the same number of 4-byte cells would occupy, and the difference decides what fits in memory.

Fractional relaxation bounds the integral optimum

The LP relaxation of knapsack allows taking a fraction of an item and is solved by sorting by value density v_i / w_i and filling greedily. Its optimum OPT_LP is an upper bound on the integral optimum, and the integral optimum is at least OPT_LP − v_max: the greedy solution takes everything except possibly one split item, so dropping the fractional part loses at most the value of the single heaviest-value item. Since OPT ≥ max(v_max, OPT_LP − v_max), at least one of the two terms is at least OPT_LP / 2, so OPT_LP ≤ 2·OPT and the better of the two candidates is a 2-approximation.

The bound is the hook for the scaling scheme. If values are rounded down to multiples of some K, the DP runs on scaled values that are at most V/K per item and at most nV/K in total, so the table over “value achieved” has O(n · nV/K) cells and the running time becomes O(n²V/K). Rounding each value down by at most K loses at most nK in total value, so choosing K = ε·v_max/n costs at most ε·v_max and gives a (1 − ε) approximation in O(n³/ε) time relative to v_max. That is a fully polynomial-time approximation scheme, and it exists for knapsack precisely because the pseudo-polynomial DP exists. The same construction fails for strongly NP-hard problems, which have no FPTAS unless P = NP.

Note the asymmetry: the value-scaling DP and the capacity-indexed DP are the same algorithm with different axes. Either the weight axis or the value axis can be the table index, and the cheaper choice depends on whether total weight or total value is smaller. Choosing the cheaper of W and Σv is a standard practical choice and changes the complexity class not at all.

Bounded quantities and binary splitting

The bounded knapsack variant allows up to m_i copies of item i. The naive reduction to 0/1 knapsack expands each item into m_i copies, which multiplies n by the multiplicities and can be enormous. Binary splitting replaces the m_i copies with ⌊log₂ m_i⌋ + 1 items of sizes 1, 2, 4, …, m_i − 2^k + 1 times the original weight and value. Every count from 0 to m_i is representable as a subset sum of those sizes, so the expanded 0/1 instance has the same feasible solutions. The item count grows from n to O(n log m_max).

The unbounded variant, where each item may be used any number of times, needs the ascending traversal described above and no expansion at all. The distinction between ascending and descending traversal is therefore not a stylistic preference: it is the difference between two problem variants that share a recurrence and differ in one loop bound.

What the DP does not decide

Three properties of the problem are invisible to the table.

Uniqueness. The DP computes one optimal value; the number of distinct optimal subsets can be exponential. Counting them needs a separate recurrence whose transition is the sum of the counts of its predecessors rather than their maximum, and each subset’s canonical decomposition must be fixed so that it is counted once; without that rule the sum overcounts.

Lexicographic tie-breaking. If several subsets achieve the optimum and a specific one is required — the lexicographically smallest index set, say — the DP must carry enough state to compare candidates, which usually means a second criterion in the comparison and a consistent order of iteration.

Exact feasibility with large weights. When weights exceed the capacity individually, the item is simply excluded; when weights are irrational or floating point, the DP’s exact arithmetic assumption fails and the result is approximate in a way that no error bound covers.

The last point connects to the broader question of when a table indexed by a numeric quantity is affordable at all. The answer is always: it is affordable when the quantity is bounded by a polynomial in the input length, or when the problem tolerates scaling. Both conditions are properties of the problem instance, and neither can be established by looking at the code.