The 0/1 Knapsack Problem

The 0/1 knapsack problem is specified by $n$ items, each with a positive weight $w_i$ and a value $v_i$, and a capacity $W$. A feasible solution is a subset $S \subseteq \{1, \dots, n\}$ with $\sum_{i \in S} w_i \le W$. The goal is to find a feasible $S$ maximizing $\sum_{i \in S} v_i$. The name "0/1" emphasizes that each item is either fully included (1) or fully excluded (0) — there is no fractional taking, which distinguishes this from the fractional knapsack problem that a greedy exchange argument solves exactly in $O(n \log n)$ time. The central design insight, shared with all dynamic programming, is optimal substructure: an optimal solution to the whole problem is built from optimal solutions to smaller subproblems. Define

Consider item $i$ in an optimal solution to $OPT(i, c)$. Either item $i$ is excluded — in which case the optimal value is exactly $OPT(i-1, c)$ — or item $i$ is included, which requires $w_i \le c$ and leaves an optimal solution to the remaining items with reduced capacity, contributing $v_i + OPT(i-1, c - w_i)$. Because these are the only two possibilities and each is itself optimal on a strictly smaller subproblem, taking the better of the two gives the recurrence used below. This is the overlapping subproblems property at work: the subproblem $OPT(i-1, c')$ for a fixed $c'$ is reused by many different choices made at later items, so memoizing it (per Memoization versus Tabulation) avoids recomputation.

The recurrence has two indices — the number of items considered and the remaining capacity — so the natural tabulation strategy is a 2D array $dp[i][c]$ for $i = 0, \dots, n$ and $c = 0, \dots, W$.

Recurrence.

The base case $dp[0][c] = 0$ for all $c$ encodes "zero items chosen, zero value, any capacity is trivially respected." The final answer is $dp[n][W]$. Filling the table row by row (increasing $i$), each cell needs only two entries from the previous row, so a straightforward double loop computes the whole table bottom-up, exactly the tabulation style introduced when contrasting it with top-down memoization. ``` function KNAPSACK(weights[1..n], values[1..n], W): // dp[i][c] = best value using items 1..i with capacity c let dp[0..n][0..W] be a new array, all initialized to 0 for i = 1 to n: for c = 0 to W: if weights[i] > c: dp[i][c] = dp[i-1][c] // item i cannot fit else: dp[i][c] = max(dp[i-1][c], values[i] + dp[i-1][c - weights[i]]) return dp[n][W], dp // keep dp for reconstruction function RECONSTRUCT(dp, weights[1..n], values[1..n], W, n): chosen = empty list c = W for i = n downto 1: if dp[i][c] != dp[i-1][c]: // item i's inclusion strictly improved the value at (i, c), // so item i must have been taken chosen.append(i) c = c - weights[i] // else dp[i][c] == dp[i-1][c]: item i was not taken, c unchanged return chosen // list of item indices in the optimal set ``` Two correctness details deserve emphasis. First, the loop order matters only in that row $i$ must be fully computed before row $i+1$ is touched — each row depends solely on the row directly above it, never on itself, so there is no ordering ambiguity within a row. Second, the reconstruction loop works backward precisely because $dp[i][c] \ne dp[i-1][c]$ can only happen when item $i$ was included (excluding it would have reproduced $dp[i-1][c]$ exactly); this is the standard technique of walking parent choices back through a DP table, foreshadowing the explicit choice-tracking used in Backtracking and State-Space Search.

Time complexity. The table has $(n+1)(W+1)$ cells, and each cell is computed in $O(1)$ time by looking at two already-computed entries. Hence the total running time is

Reconstruction walks from row $n$ to row $1$ once, adding $O(n)$ time, which does not change the asymptotic bound.

Space complexity. The full table uses $O(nW)$ space. If only the optimal value is needed (not the item set), the table can be compressed to a single 1D array of size $W+1$, updated in place scanning capacity from high to low within each item's iteration — this reduces space to $O(W)$ but destroys the information needed for reconstruction, since overwriting a row erases the previous row. Keeping the full 2D table (or, more space-efficiently, storing only which item was taken at each cell) is the standard tradeoff when the actual item set is required.

Why "pseudo-polynomial." The input to the problem consists of $n$ numbers for weights, $n$ numbers for values, and the capacity $W$, all typically encoded in binary. The size of this encoding is roughly $O(n \log W)$ bits, not $O(n + W)$. An algorithm is polynomial-time if its running time is polynomial in the bit-length of the input. Here the running time $O(nW)$ is polynomial in the numeric value $W$, but $W$ can require only $\log_2 W$ bits to write down — so if $W$ is, say, $2^{64}$, the table has more cells than atoms in reach, even though the input itself is tiny. This gap between "polynomial in the numbers" and "polynomial in the input size" is exactly the definition of a pseudo-polynomial algorithm, and 0/1 knapsack is the textbook example of the concept. (Indeed 0/1 knapsack is NP-hard in the strong sense's opposite: it is only weakly NP-hard, precisely because this pseudo-polynomial algorithm exists — a strongly NP-hard problem admits no pseudo-polynomial algorithm unless P = NP.)

Correctness proof sketch (induction on $i$). Claim: for every $i$ and $c$, $dp[i][c]$ equals $OPT(i,c)$ as defined above. Base case ($i=0$): with no items available, the best achievable value under any capacity is $0$, matching $dp[0][c]=0$. Inductive step: assume $dp[i-1][c'] = OPT(i-1,c')$ for all $c'$. Fix $c$. Any feasible solution using items $1,\dots,i$ either omits item $i$, in which case its value is at most $OPT(i-1,c) = dp[i-1][c]$, or includes item $i$ (requiring $w_i \le c$), in which case the remaining items form a feasible solution to capacity $c-w_i$, so the total value is at most $v_i + OPT(i-1,c-w_i) = v_i + dp[i-1][c-w_i]$. Since these two cases are exhaustive and each bound is achieved by some solution (by the inductive hypothesis, the subproblems attain their optima), taking the max of the two bounds is both an upper bound on every feasible solution and achievable — hence $dp[i][c]$ equals the true optimum $OPT(i,c)$. By induction this holds for all $i$, in particular $dp[n][W] = OPT(n,W)$, the answer to the original problem. $\blacksquare$

Why reconstruction is correct. At each step, $dp[i][c] \ne dp[i-1][c]$ can only occur if item $i$ contributed to the optimum at $(i,c)$: the recurrence sets $dp[i][c] = dp[i-1][c]$ whenever item $i$ is excluded or doesn't fit, so any difference forces the "include" branch to have been the maximizer, meaning item $i$ is in some optimal solution reachable at that cell. Moving to $c - w_i$ correctly continues the search among the remaining items, so the walk-back invariant (the cell $(i,c)$ visited always still represents an unresolved optimum) is preserved at every step.

Tradeoffs. The DP is exact and simple, but useless when $W$ is huge (a common case in real capital-budgeting or bin-packing-adjacent settings). In that regime, one falls back on the pseudo-polynomial-in-$n \cdot \max(v_i)$ "value-indexed" DP, approximation schemes (a fully polynomial-time approximation scheme, FPTAS, exists by scaling values), or exponential-but-pruned search such as Branch and Bound.

Consider $n=4$ items with capacity $W=7$:

Filling $dp[i][c]$ for $c = 0,\dots,7$:

Sample cell derivations:

• $dp[2][5]$: item 2 has $w_2=3 \le 5$, so $dp[2][5] = \max(dp[1][5],\, 4 + dp[1][2]) = \max(3,\, 4+3) = 7$. (Take items 1 and 2: weight $2+3=5$, value $3+4=7$.)
• $dp[3][6]$: item 3 has $w_3=4 \le 6$, so $dp[3][6] = \max(dp[2][6],\, 5 + dp[2][2]) = \max(7,\, 5+3) = 8$.
• $dp[4][7]$: item 4 has $w_4=5 \le 7$, so $dp[4][7] = \max(dp[3][7],\, 6 + dp[3][2]) = \max(9,\, 6+3) = 9$. Since $9 = dp[3][7]$, item 4 is not taken at the final cell.

Answer: $dp[4][7] = 9$.

Reconstruction, walking backward from $(i=4, c=7)$:

Chosen items: $\{3, 2\}$, weight $4+3=7 \le 7$, value $5+4=9$ — matching $dp[4][7]$ exactly, and confirming the table's claim. Note that the greedy heuristic "sort by value-to-weight ratio and take greedily" would pick item 1 ($3/2=1.5$) first, then item 2 ($4/3\approx1.33$), filling capacity $2+3=5$ with value 7 and no room left for anything of weight $\ge 3$ — strictly worse than the DP's optimal $9$. This gap is the standard demonstration that greedy fails for 0/1 knapsack even though it succeeds for the fractional relaxation.

The knapsack problem's formal study is inseparable from the birth of dynamic programming itself. Richard Bellman, who coined the term "dynamic programming" in the 1950s while working at RAND Corporation, developed the principle of optimality — that an optimal policy consists of optimal sub-policies — which is exactly the substructure argument used above. Knapsack-style allocation problems appeared naturally in Bellman's work on multistage resource-allocation, and the specific DP formulation over weight-capacity was popularized through operations research literature in the following decades. The complexity-theoretic classification of the problem — NP-hard, yet only weakly so, admitting a pseudo-polynomial algorithm and an FPTAS — was cemented once the theory of NP-completeness matured in the 1970s, following the foundational work of Stephen Cook on NP-completeness itself. Karp's 1972 list of 21 NP-complete problems included the closely related subset-sum problem, cementing knapsack-family problems as central examples in complexity theory courses ever since.

Cloud resource schedulers use knapsack-style reasoning to decide which containers or virtual machines to pack onto a physical host without exceeding memory or CPU capacity. Portfolio and capital-budgeting software selects a subset of candidate projects to fund under a fixed budget, directly mapping projects to items and cost to weight. Compilers and embedded-systems toolchains apply knapsack formulations when choosing which optional code transformations to enable under a strict code-size or instruction-count limit. Bioinformatics pipelines use knapsack-adjacent DP when selecting a subset of experiments or reads under a sequencing-budget constraint. In every case, the same three ingredients recur: discrete either/or choices, a single linear resource constraint, and a separable value to maximize — and the $O(nW)$ table-filling technique, together with its reconstruction step, is the standard first tool reached for before escalating to heavier machinery like Branch and Bound or approximation schemes when $W$ grows too large.

:::quiz[What is the base case of the knapsack DP recurrence dp[i][c]?]

• dp[n][W] = 0
• dp[0][c] = 0 for all c ✓
• dp[i][0] = infinity
• dp[i][c] = values[i] for all i

Ask the tutor: How would the recurrence and reconstruction change if each item could be taken multiple times (the unbounded knapsack variant)?