Knapsack
Motivation
You have a knapsack of capacity \(W\) and \(n\) items, item \(i\) with weight \(w_i\) and value \(v_i\). Pick a subset of items whose total weight is at most \(W\) to maximize total value. This 0/1 knapsack problem is the second canonical introductory example of dynamic programming (after weighted interval scheduling), and it is the textbook illustration of a problem whose DP runs in pseudo-polynomial time — polynomial in the numerical value of \(W\) but not in its bit-length (Kleinberg and Tardos 2005; Cormen et al. 2009).
The 0/1 knapsack problem is NP-hard (as a decision problem, it is in NP and reducible from subset sum), so we do not expect a true polynomial-time algorithm. The pseudo-polynomial DP, plus an FPTAS based on rounding values, gives the best practical algorithms.
A different version, fractional knapsack (items can be split), is solvable greedily in \(O(n \log n)\) — sort by value-density. The 0/1 version is the hard one.
Problem
Given \(n\) items with positive integer weights \(w_1, \dots, w_n\) and values \(v_1, \dots, v_n\), and a capacity \(W\), choose \(S \subseteq \{1, \dots, n\}\) with \(\sum_{i \in S} w_i \le W\) to maximize \(\sum_{i \in S} v_i\).
Key Ideas
Binary choice over items
For each item \(i\), an optimal solution either uses \(i\) or it does not. As with weighted interval scheduling, the two cases lead to disjoint subproblems — but here the residual problem is parameterized by the remaining capacity, not just the prefix of items. So the DP state is two-dimensional: \((i, c)\) = “what’s the best I can do with items \(\le i\) and capacity \(c\)?”
The recurrence is the standard DP-vs-greedy story: greedy by value-density (the trick that works for the fractional version) fails on 0/1 instances where a single high-density item is too heavy to fit alongside the others. Only the systematic comparison of include-vs-exclude at every \((i, c)\) catches the right trade.
Pseudo-polynomial, not polynomial
The DP table has \(n(W+1)\) cells, so its size — and therefore the runtime — depends on the numerical capacity \(W\), not just \(n\). Since \(W\) is encoded in \(O(\log W)\) bits in the input, \(O(nW)\) is exponential in the input length. The algorithm is fast when \(W\) is small (a few thousand) and useless when \(W\) is huge (\(2^{60}\)).
This is what pseudo-polynomial means: polynomial in \(n\) and the value \(W\), but not in the length \(\log W\). It is a signature of weakly NP-hard problems: hard only because the input numbers can be exponentially large. If a truly polynomial algorithm existed, it would solve subset sum — a famous open problem since 1972, presumed impossible.
Deriving the Solution
Let \(\text{OPT}(i, c)\) be the maximum value achievable using items \(\{1, \dots, i\}\) with a knapsack of capacity \(c\).
Either we use item \(i\) or we do not:
- If \(w_i > c\), item \(i\) does not fit: \(\text{OPT}(i, c) = \text{OPT}(i-1, c)\).
- Otherwise, \(\text{OPT}(i, c) = \max\left( \text{OPT}(i-1, c), \; v_i + \text{OPT}(i-1, c - w_i) \right)\).
Base case: \(\text{OPT}(0, c) = 0\) for every \(c\).
Each cell depends only on cells in the previous row, so a bottom-up fill in increasing \(i\) visits each of the \(n(W+1)\) entries exactly once.
Algorithm
M[0][c] = 0 for c = 0..W
for i = 1 to n:
for c = 0 to W:
if w_i > c:
M[i][c] = M[i-1][c]
else:
M[i][c] = max(M[i-1][c], v_i + M[i-1][c - w_i])
return M[n][W]To recover the chosen set, back-trace from \(M[n][W]\): at each \((i, c)\) check whether \(M[i][c] = M[i-1][c]\) (skipped item \(i\)) or \(M[i][c] = v_i + M[i-1][c - w_i]\) (took item \(i\)), and move to the corresponding previous cell.
Walkthrough
A four-item DP table
Four items with \((w, v)\) values \((3, 4), (4, 5), (2, 3), (5, 7)\) and capacity \(W = 8\). The table \(M[i][c]\) is filled top-to-bottom, left-to-right. Cells on the back-trace from \(M[4][8]\) are shaded green; the optimal value \(M[4][8] = 11\) is bold.
The cell \(M[4][8]\) is filled by comparing \(M[3][8] = 9\) (skip item \(4\)) with \(7 + M[3][3] = 7 + 4 = 11\) (take item \(4\)). Taking it wins, so the back-trace jumps from \((4, 8)\) to \((3, 3)\). From there, \(M[3][3] = M[2][3] = M[1][3] = 4\), all unchanged because items \(3\) and \(2\) either don’t help or don’t fit; the only contributor below is item \(1\), which was taken when transitioning from \((0, 0)\) to \((1, 3)\). Filling all \(5 \times 9 = 45\) cells took \(O(nW)\) time — fast for \(W = 8\), hopeless for \(W = 10^{15}\).
Correctness
By induction on \(i\). The base \(\text{OPT}(0, c) = 0\) is correct: with no items, the only feasible subset is empty. Inductively suppose \(M[i-1][\cdot]\) is correct. Any optimal subset over \(\{1, \ldots, i\}\) with capacity \(c\) either contains \(i\) or does not:
- If it does not contain \(i\), it is also an optimal subset over \(\{1, \ldots, i-1\}\) with capacity \(c\), of value \(M[i-1][c]\).
- If it contains \(i\) (and \(w_i \le c\)), the remaining items are an optimal subset over \(\{1, \ldots, i-1\}\) with the reduced capacity \(c - w_i\), of value \(v_i + M[i-1][c - w_i]\).
The recurrence picks the max, so \(M[i][c] = \text{OPT}(i, c)\).
Complexity and Tradeoffs
The table has \(n \cdot (W+1)\) entries, each filled in \(O(1)\). Total: \(O(nW)\) time and space. The space can be reduced to \(O(W)\) by sweeping rows in place.
This is pseudo-polynomial: polynomial in \(n\) and \(W\), but \(W\) takes only \(O(\log W)\) bits to write down, so \(O(nW)\) is exponential in the input length. For modest \(W\) (a few thousand) the algorithm is fast; for \(W = 2^{60}\) it is hopeless.
Connection to LP
Knapsack admits a natural linear programming formulation: \[ \max \sum_i v_i x_i \quad \text{s.t.} \quad \sum_i w_i x_i \le W, \quad 0 \le x_i \le 1, \quad x_i \in \{0, 1\}. \] The integrality constraint makes this an integer linear program. Dropping it (allowing \(x_i \in [0,1]\)) gives the LP relaxation, which is the fractional knapsack — and provides an upper bound on the optimal 0/1 value, useful for branch-and-bound.
When to Use It
| Situation | Approach |
|---|---|
| 0/1 knapsack, \(W\) modest (thousands) | Capacity-DP, \(O(nW)\). |
| 0/1 knapsack, \(W\) huge, values modest | Value-DP, \(O(n V_{\max})\) — see Variants. |
| 0/1 knapsack, both \(W\) and values huge | FPTAS via value rounding — see Variants. |
| Fractional knapsack (splittable items) | Greedy by value-density, \(O(n \log n)\). |
| Multiple capacity constraints | LP relaxation + branch-and-bound. |
| Items can be repeated | Unbounded knapsack — see Variants. |
Variants
- DP by value (the FPTAS). Define \(\text{OPT}'(i, V)\) = the minimum total weight needed to achieve total value exactly \(V\) using items \(\{1, \dots, i\}\). The recurrence is symmetric: \[ \text{OPT}'(i, V) = \min\left( \text{OPT}'(i-1, V), \; w_i + \text{OPT}'(i-1, V - v_i) \right). \] The table size is \(n \cdot V_{\max}\) where \(V_{\max} = \sum v_i\), also pseudo-polynomial — useful when values are smaller than capacities. Combined with value rounding (\(v_i \mapsto \lfloor v_i / K \rfloor\) for an appropriate \(K\)), this yields a fully polynomial-time approximation scheme (FPTAS): for any \(\epsilon > 0\), an algorithm running in time polynomial in \(n\) and \(1/\epsilon\) that returns a solution within \((1 - \epsilon)\) of optimal.
- Unbounded knapsack. Each item may be picked any number of times. The recurrence becomes \(\text{OPT}(c) = \max_i (v_i + \text{OPT}(c - w_i))\), \(O(nW)\) but with a one-dimensional table.
- Multidimensional knapsack. Multiple capacity constraints (weight, volume). NP-hard, often solved with LP relaxation.
- Bin packing. Dual problem — fit items into the fewest knapsacks. Also NP-hard.