Chapter XVIII Knapsack

The knapsack

Just because it's NP-complete doesn't mean it's slow in practice.

Given n items with weights and values, and a capacity W, the 0-1 knapsack picks a subset to maximize total value without exceeding the budget:

max i \in S \sum v_{i} subject to i \in S \sum w_{i} \leq W, S \subseteq {1, \dots, n} . (1)

Form (1) is NP-complete in W's binary encoding (Karp), but the standard DP solves it in time

O (n \cdot W) . (2)

The runtime (2) is pseudo-polynomial — the table size depends on W itself, not on log W. For practical W in the millions, that's fast. The recurrence underlying (2) is

dp [i, w] = max (dp [i - 1, w], dp [i - 1, w - w_{i}] + v_{i}) . (3)

Knapsack is the friendly NP-complete problem: (3) gives exact answers fast on practical sizes, and an FPTAS exists — any approximation ratio (1 − ε) in time polynomial in 1/ε.

Figures, in plain terms

(1)

max Σ over i ∈ S of v_i is "maximize the total value of chosen items." The big-Σ sums up value contributions; the index i ranges over our choice S.

subject to introduces the constraints: Σ w_i ≤ W says the total weight of chosen items must not exceed the capacity W.

S ⊆ {1, ..., n} declares S as a subset of the item indices — a yes/no decision per item, all-or-nothing.

So (1) reads: pick a subset of items to maximize total value while keeping total weight within budget. The "all-or-nothing" choice (no half items) is what makes it 0-1 knapsack rather than the easier fractional version.

(2)

O(n · W) is pseudo-polynomial — polynomial in n and W, but not in the input size.

The size of the input is roughly n × log W bits (you can write W in log₂ W bits). The runtime depends on W itself, not log W, so doubling the bit-length of W doubles the bit-length of the input but squares the runtime.

For practical W in the millions, n · W is a few seconds of computation. For W in the gigabits, it's intractable. That's why knapsack is "easy in practice" but still NP-complete in theory.

(3)

dp[i, w] is a 2D table indexed by item count and remaining capacity. The brackets are "lookup at this index."

The right side is max(...) — pick whichever choice produces the bigger value. Two choices:

dp[i−1, w]: the best value if we skip item i (capacity w stays the same; we have one fewer item to consider).

dp[i−1, w − w_i] + v_i: the best value if we take item i — capacity drops by w_i (the weight of item i), then we add v_i (the value).

The max of these two recursive lookups gives the optimal answer for this state. Walk i from 1 to n and w from 0 to W; the bottom-right cell holds the answer.