---
title: Knapsack & Subset Problems
module: Dynamic Programming
moduleNumber: 8
lessonNumber: 4
order: 804
summary: |
  We start from $\textsc{Subset-sum}$ — does some sublist hit a target $t$? — and its
  include/exclude recurrence over a boolean table $A(i, u)$, then bolt on values
  to get 0/1 knapsack as the same machine with $\lor$ promoted to $\max$. We fill
  both tables, recover the chosen items, and confront the surprise that the
  $\Theta(nt)$ running time is only _pseudo-polynomial_ — exponential in the bit
  length $b$, and unimprovable unless $\mathrm{P}=\mathrm{NP}$ since subset-sum is
  $\textsc{NP-complete}$. The fractional variant reveals the sharp line between greedy
  and dynamic programming.
topics: [Dynamic Programming]
sources:
  - book: CLRS
    ref: "Ch. 15 — Dynamic Programming"
  - book: Skiena
    ref: "§10 — Dynamic Programming"
  - book: Erickson
    ref: "Ch. 3 — Dynamic Programming"
practice:
  - title: 'Partition Equal Subset Sum'
    slug: partition-equal-subset-sum
    difficulty: Medium
  - title: 'Coin Change'
    slug: coin-change
    difficulty: Medium
  - title: 'Coin Change II'
    slug: coin-change-ii
    difficulty: Medium
  - title: 'Target Sum'
    slug: target-sum
    difficulty: Medium
  - title: 'Ones and Zeroes'
    slug: ones-and-zeroes
    difficulty: Medium
---

A thief breaks into a warehouse carrying a knapsack that holds at most $W$ units
of weight. Item $i$ weighs $w_i$ and is worth $v_i$. Each item is taken whole or
left behind, with no fractions and no duplicates. Which subset maximizes the value
carried out without exceeding the capacity? This is the **0/1 knapsack problem**.
Despite the toy framing, it underlies resource allocation, budgeting, and
cutting-stock problems, and it is a canonical $\textsc{NP-hard}$ optimization problem
whose dynamic program illustrates what "polynomial" really means.[^skiena-knap]

We will arrive at knapsack through its simpler decision cousin, $\textsc{Subset-sum}$,
which strips away the values and asks a plain yes/no question. The include/exclude
recurrence is identical, the running-time subtlety is identical, and subset-sum is
the cleanest place to see both.

## Subset-sum: the decision core

> **Input:** a list $L = \langle a_1, a_2, \dots, a_n\rangle$ of positive integers
> and a target integer $t > 0$.
> **Output (simplified):** $\text{yes}$ if some sublist of $L$ sums to exactly
> $t$, and $\text{no}$ otherwise.

The brute-force space is the $2^n$ sublists. To get a recurrence we shrink the
instance one element at a time; the _second_ dimension comes from making the
_target itself_ a parameter of the subproblem.

> **Definition (Subset-sum subproblem).** Let $A(i, u)$ be $\text{true}$ exactly when some sublist of the prefix
> $L[1..i] = \langle a_1, \dots, a_i\rangle$ sums to $u$, and $\text{false}$
> otherwise.

The answer we want is $A(n, t)$. Now look at $a_i$, the last element we are
allowed to use, and make the **include/exclude** decision that defines every
0/1 dynamic program:

- **Exclude $a_i$.** Then some sublist of the first $i-1$ elements must already
  hit $u$ on its own: $A(i-1, u)$.
- **Include $a_i$.** Then it contributes $a_i$ toward the target, and the first
  $i-1$ elements must cover the shortfall: $A(i-1, u - a_i)$.

The element can be used in _either_ way, so the subproblem is true if _either_
branch succeeds, a logical $\lor$. The base cases specify the boundary: a
budget of $0$ is always reachable by the empty set; a positive budget is
unreachable with no elements; a negative budget is impossible:
$$
A(i,u) =
\begin{cases}
\text{true} & \text{if } u = 0, \\[3pt]
\text{false} & \text{if } u < 0, \\[3pt]
\text{false} & \text{if } i = 0 \text{ and } u > 0, \\[3pt]
A(i-1, u)\ \lor\ A(i-1,\, u - a_i) & \text{if } i > 0,\ u > 0.
\end{cases}
$$
Every entry depends only on two entries of the _previous row_ ($i-1$): the one
directly above (exclude) and the one above and $a_i$ columns to the left
(include). So we fill the table **row by row** in increasing $i$, sweeping the
budget $u = 0, \dots, t$ within each row.

### The subset-sum table, filled

Take $L = \langle 1, 3, 4, 2\rangle$ and target $t = 6$. The table holds the
boolean $A(i, u)$: row $0$ is $\text{true}$ only in column $0$ (the empty set
sums to $0$), and each later row ORs the _exclude_ cell directly above with the
_include_ cell $a_i$ columns to its left. The shaded cell $A(4,6)$ is the answer;
the two arrows show its include/exclude dependency.

$$
% caption: Boolean subset-sum table with the answer cell and its include and exclude
%          predecessors.
\begin{tikzpicture}[
  >=Stealth,
  T/.style={draw, minimum size=8mm, inner sep=1pt, font=\small, fill=acc!15},
  F/.style={draw, minimum size=8mm, inner sep=1pt, font=\small},
  lbl/.style={draw=none, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % header: budgets u = 0..6
  \node[lbl] at (0,0) {$A(i,u)$};
  \foreach \u in {0,...,6} { \node[lbl] at (\u+1,0) {$u{=}\u$}; }
  % row labels (with a_i)
  \node[lbl] at (0,-1) {$i{=}0$};
  \node[lbl] at (0,-2) {$1\ (a{=}1)$};
  \node[lbl] at (0,-3) {$2\ (a{=}3)$};
  \node[lbl] at (0,-4) {$3\ (a{=}4)$};
  \node[lbl] at (0,-5) {$4\ (a{=}2)$};
  % row 0: only u=0 true
  \node[T] at (1,-1) {T};
  \foreach \c in {2,...,7} { \node[F] at (\c,-1) {F}; }
  % row 1: a=1 -> sums {0,1}
  \node[T] at (1,-2) {T}; \node[T] at (2,-2) {T};
  \foreach \c in {3,...,7} { \node[F] at (\c,-2) {F}; }
  % row 2: a=3 -> sums {0,1,3,4}
  \node[T] at (1,-3) {T}; \node[T] at (2,-3) {T}; \node[F] at (3,-3) {F};
  \node[T] at (4,-3) {T}; \node[T] at (5,-3) {T}; \node[F] at (6,-3) {F}; \node[F] at (7,-3) {F};
  % row 3: a=4 -> sums {0,1,3,4,5,7,8}∩[0,6] = {0,1,3,4,5}
  \node[T] at (1,-4) {T}; \node[T] at (2,-4) {T}; \node[F] at (3,-4) {F};
  \node[T] at (4,-4) {T}; \node[T] at (5,-4) {T}; \node[T] at (6,-4) {T}; \node[F] at (7,-4) {F};
  % row 4: a=2 -> add 2 to {0,1,3,4,5} -> {2,3,5,6,7}; union {0,1,3,4,5} = {0,1,2,3,4,5,6}
  \node[T] at (1,-5) {T}; \node[T] at (2,-5) {T}; \node[T] at (3,-5) {T};
  \node[T] at (4,-5) {T}; \node[T] at (5,-5) {T}; \node[T] at (6,-5) {T};
  \node[T, fill=acc!45] (ans) at (7,-5) {T};
  % --- the answer's two predecessors, dashed accent borders (the T/F letter stays visible) ---
  \node[draw=acc, very thick, dashed, minimum size=8mm, inner sep=1pt] (exc) at (7,-4) {};
  \node[draw=acc, very thick, dashed, minimum size=8mm, inner sep=1pt] (inc) at (5,-4) {};
  % EXCLUDE arrow: predecessor sits directly above, so a short bow down the right edge.
  \draw[->, very thick, red!75!black] (exc.east) to[out=0, in=0, looseness=2.3] (ans.east);
  \node[lbl, anchor=west, align=left, text=red!75!black] at (8.15,-4)
    {\itshape exclude $a_4$:\\skip it, copy the\\cell above, $A(3,6)$};
  % INCLUDE arrow: predecessor is two columns left (u-a_4). Route it cleanly around the
  % outside — down the column-4/5 gap, along below the table, up into the answer — so it
  % never cuts through a cell.
  \draw[->, very thick, red!75!black]
    (inc.south) -- (4.5,-4.5) -- (4.5,-6.1) -- (7,-6.1) -- (ans.south);
  \node[lbl, align=center, text=red!75!black] at (5.75,-6.55)
    {\itshape include $a_4{=}2$: jump back $2$ columns, $A(3,4)$};
\end{tikzpicture}
$$

The answer is $A(4,6) = \text{true}$, witnessed by $\set{4, 2}$ or
$\set{1,3,2}$. Reading its two dashed predecessors: _exclude_ $a_4$ reads
$A(3,6) = \text{false}$ (no subset of $\langle1,3,4\rangle$ hits $6$), while
_include_ $a_4{=}2$ reads $A(3, 6-2) = A(3,4) = \text{true}$; the $\lor$ makes
the cell true through the include branch.

### Subset-sum in pseudocode

```algorithm
caption: $\textsc{Subset-Sum}(L[1..n], t)$ — does some sublist sum to $t$?
number: 1
$A[0..n][0..t] \gets \text{false}$
$A[0..n][0] \gets \text{true}$ // empty set reaches $0$
for $i \gets 1$ to $n$ do
  for $u \gets 1$ to $t$ do
    if $a_i > u$ then
      $A[i][u] \gets A[i-1][u]$ // $a_i$ too big: exclude
    else
      $A[i][u] \gets A[i-1][u] \lor A[i-1][u - a_i]$ // exclude or include
return $A[n][t]$
```

This fills $(n+1)(t+1)$ boolean cells in $\Theta(1)$ apiece, for $\Theta(nt)$
time and $\Theta(nt)$ space, and the space drops to $\Theta(t)$ because each row
reads only the one above it. We return to the $\Theta(nt)$ bound below; it is
less benign than it looks. First, 0/1 knapsack is the same recurrence with
values added.

## The problem and why greed fails

> **Input:** $n$ items with positive integer weights $w_1, \dots, w_n$ and values
> $v_1, \dots, v_n$, and an integer capacity $W$.
> **Output:** a subset $S \subseteq \set{1, \dots, n}$ with $\sum_{i \in S} w_i
> \le W$ maximizing $\sum_{i \in S} v_i$.

Knapsack is subset-sum with two upgrades: each item carries a separate **value**
$v_i$ as well as a weight $w_i$, and the capacity $W$ is an _upper bound_ rather
than an exact target, so we **maximize** value instead of answering yes/no. The
include/exclude decision is unchanged: the $\lor$ of subset-sum becomes a $\max$,
and the boolean cell becomes a value. (Set $v_i = w_i = a_i$ and the answer
$K(n,t) = t$ recovers subset-sum exactly, a reduction we make precise
[below](#subset-sum-as-a-special-case).)

> **Claim.** The greedy by-ratio strategy (take items in decreasing order of
> $v_i / w_i$) is _not_ optimal for the 0/1 problem.

> **Proof.** A single counterexample suffices. Take $W = 10$ and items
> $A = (w{=}6, v{=}10)$, $B = (w{=}5, v{=}9)$, $C = (w{=}5, v{=}9)$. Item $A$ has
> the best ratio ($1.67$ per unit), so greed grabs it first; then nothing else
> fits, for a total value of $10$. But taking $B$ and $C$ together fills the
> knapsack exactly for value $18 > 10$, so greedy is not optimal. $\qed$

The greedy strategy fails because a locally efficient item can block a globally
better combination; the 0/1 problem lacks the structure that lets greedy choices
succeed on [matroids](/algorithms/greedy/matroids). We need to consider subsets,
and that calls for dynamic programming.

$$
% caption: Why greedy fails for 0/1 knapsack ($W=10$). Best ratio first grabs $A$
%          ($v/w = 1.67$) and then nothing fits: value $10$. Taking $B$ and $C$ instead
%          fills capacity exactly for value $18$.
\begin{tikzpicture}[
  >=Stealth,
  it/.style={draw, font=\footnotesize, inner sep=2pt},
  lbl/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[lbl] at (0,1.5) {\itshape greedy: ratio f\/irst};
  \node[it, minimum width=15.6mm, fill=acc!15] (gA) at (-0.26,0) {$A\ (w6,v10)$};
  \draw[thick] (-1.3,-0.55) rectangle (1.3,0.55);
  \node[lbl] at (-1.7,-0.95) {$0$};
  \node[lbl] at (1.3,-0.95) {$W{=}10$};
  \node[lbl, acc] at (0,-1.4) {value $= 10$};
  \node[lbl] at (5,1.5) {\itshape optimal: $B+C$};
  \node[it, minimum width=10.4mm, fill=acc!15] (oB) at (4.06,0) {$B$};
  \node[it, minimum width=10.4mm, fill=acc!15] (oC) at (5.94,0) {$C$};
  \draw[thick] (3.7,-0.55) rectangle (6.3,0.55);
  \node[lbl] at (3.3,-0.95) {$0$};
  \node[lbl] at (6.3,-0.95) {$W{=}10$};
  \node[lbl, acc] at (5,-1.4) {value $= 18$};
\end{tikzpicture}
$$

The high-ratio item $A$ is locally efficient yet blocks the $B + C$ pair that
packs the knapsack with no waste.

## The subproblem and recurrence

The brute-force space is the $2^n$ subsets. To get a recurrence we need a
subproblem definition that shrinks the instance one decision at a time. The
_second_ dimension comes from tracking not only _which items_ remain available
but _how much capacity_ is left.

> **Definition (Knapsack DP state).** Let $K(i, w)$ be the maximum value achievable using only the first $i$ items
> $\set{1, \dots, i}$ within a weight budget of $w$.

The answer is $K(n, W)$. Now consider item $i$, the last one we are allowed to
use, and make the same include/exclude decision as in subset-sum; this is the
"0/1" in the name.

**Exclude item $i$.** Then the best we can do is whatever the first $i-1$ items
achieve within the same budget: $K(i-1, w)$.

**Include item $i$.** This is only possible if it fits, $w_i \le w$. We collect
its value $v_i$ and spend $w_i$ of the budget, leaving $w - w_i$ for the first
$i-1$ items: $v_i + K(i-1, w - w_i)$.

We take the better of the two, and if item $i$ does not fit, only the first
option is available:[^clrs-knap]
$$
K(i,w) =
\begin{cases}
0 & \text{if } i = 0 \text{ or } w = 0, \\[3pt]
K(i-1, w) & \text{if } w_i > w, \\[3pt]
\max\parens{K(i-1, w),\ v_i + K(i-1, w - w_i)} & \text{if } w_i \le w.
\end{cases}
$$
The base case says: with no items, or no capacity, the value is $0$. Each entry
depends only on entries in the _previous row_ ($i-1$), so we fill the table **row
by row** in increasing $i$, and within each row over all budgets $w = 0, \dots,
W$.

## The DP table, filled

Take capacity $W = 5$ and four items: $1{:}(w{=}1, v{=}1)$, $2{:}(w{=}2,
v{=}6)$, $3{:}(w{=}3, v{=}10)$, $4{:}(w{=}5, v{=}16)$. The table holds $K(i, w)$;
row $0$ is all zeros (no items), and each later row applies the recurrence across
budgets $0$ through $5$.

$$
% caption: Filled 0/1 knapsack value table with include and exclude arrows into the
%          answer.
\begin{tikzpicture}[
  >=Stealth,
  every node/.style={draw, minimum size=8mm, inner sep=1pt, font=\small},
  lbl/.style={draw=none}]
  \definecolor{acc}{HTML}{2348F2}
  % header: budgets
  \node[lbl] at (0,0) {\texttt{K(i,w)}};
  \node[lbl] at (1,0) {$w{=}0$};
  \node[lbl] at (2,0) {$1$};
  \node[lbl] at (3,0) {$2$};
  \node[lbl] at (4,0) {$3$};
  \node[lbl] at (5,0) {$4$};
  \node[lbl] at (6,0) {$5$};
  % row labels
  \node[lbl] at (0,-1) {$i{=}0$};
  \node[lbl] at (0,-2) {$1\ (w{=}1)$};
  \node[lbl] at (0,-3) {$2\ (w{=}2)$};
  \node[lbl] at (0,-4) {$3\ (w{=}3)$};
  \node[lbl] at (0,-5) {$4\ (w{=}5)$};
  % row 0
  \node at (1,-1) {0}; \node at (2,-1) {0}; \node at (3,-1) {0}; \node at (4,-1) {0}; \node at (5,-1) {0}; \node at (6,-1) {0};
  % row 1: (1,1)
  \node at (1,-2) {0}; \node at (2,-2) {1}; \node at (3,-2) {1}; \node at (4,-2) {1}; \node at (5,-2) {1}; \node at (6,-2) {1};
  % row 2: (2,6) -- include/exclude sources for K(3,5)
  \node at (1,-3) {0}; \node at (2,-3) {1}; \node[draw=acc, dashed] (kinc) at (3,-3) {6}; \node at (4,-3) {7}; \node at (5,-3) {7}; \node[draw=acc, dashed] (kexc) at (6,-3) {7};
  % row 3: (3,10)
  \node at (1,-4) {0}; \node at (2,-4) {1}; \node at (3,-4) {6}; \node at (4,-4) {10}; \node at (5,-4) {11}; \node[fill=acc!15, draw=acc, very thick] (k35) at (6,-4) {16};
  % row 4: (5,16)
  \node at (1,-5) {0}; \node at (2,-5) {1}; \node at (3,-5) {6}; \node at (4,-5) {10}; \node at (5,-5) {11}; \node[fill=acc!15] at (6,-5) {16};
  % dependency arrows into K(3,5)=16
  \draw[->, thick, red!75!black] (kexc.south) -- (k35.north);
  \draw[->, thick, red!75!black] (kinc.south east) to[bend left=12] (k35.north west);
  \node[lbl, anchor=west] at (6.55,-3.0) {\itshape exclude $3$};
  \node[lbl] (inclbl3) at (2.5,-6) {\itshape include $3$ (back $w=3$)};
  \draw[->, thin, red!75!black] (inclbl3.north) -- (2.5,-3) -- (kinc.west);
\end{tikzpicture}
$$

The shaded answer is $K(4, 5) = 16$. The arrows trace the highlighted entry
$K(3,5)$: item $3$ weighs $3 \le 5$, so we compare _excluding it_ ($K(2,5) = 7$,
the cell directly above) against _including it_ ($v_3 + K(2, 5-3) = 10 + K(2,2) =
10 + 6 = 16$, reaching $w_3 = 3$ columns to the left); the include branch wins at
$16$. One row down, $K(4,5)$ compares _excluding item $4$_ ($K(3,5) = 16$)
against _including it_ ($16 + K(3, 0) = 16$), a tie at $16$.

To see the whole table appear rather than just its answer, walk the rows in order.
Row $0$ is the boundary: with no items every budget yields value $0$. Each later
row copies the row above (the exclude branch) and then, wherever item $i$ fits,
overwrites the cell with the larger of that copy and $v_i + K(i-1, w - w_i)$.

- **Row $1$**, item $(w{=}1, v{=}1)$. It fits from $w = 1$ onward, and once it
  fits it is always worth taking, so $K(1,0) = 0$ and $K(1,w) = 1$ for $w \ge 1$.
- **Row $2$**, item $(w{=}2, v{=}6)$. At $w = 2$ we compare exclude $K(1,2) = 1$
  against include $6 + K(1,0) = 6$; include wins, $K(2,2) = 6$. At $w = 3$,
  include gives $6 + K(1,1) = 7$, beating the copied $1$. From $w = 3$ up the row
  reads $7$, since one unit of budget past the pair adds nothing new.
- **Row $3$**, item $(w{=}3, v{=}10)$. At $w = 3$, include gives $10 + K(2,0) =
  10 > K(2,3) = 7$. At $w = 4$, include gives $10 + K(2,1) = 11$. At $w = 5$,
  include gives $10 + K(2,2) = 10 + 6 = 16$, the entry the arrows highlighted.
- **Row $4$**, item $(w{=}5, v{=}16)$. It fits only at $w = 5$, where include
  gives $16 + K(3,0) = 16$, tying the copied $K(3,5) = 16$. The recurrence keeps
  the earlier winner on a tie, so the answer $K(4,5) = 16$ is achieved _without_
  item $4$.

A cell is never touched again once written: every dependency points one row up,
so the sweep in increasing $i$ always finds its inputs already final.

## The algorithm

```algorithm
caption: $\textsc{Knapsack-01}(w, v, n, W)$ — maximum value within capacity $W$
number: 2
for $b \gets 0$ to $W$ do
  $K[0][b] \gets 0$ // no items: value $0$
for $i \gets 1$ to $n$ do
  for $b \gets 0$ to $W$ do
    $K[i][b] \gets K[i-1][b]$ // skip item $i$
    if $w[i] \le b$ then
      $take \gets v[i] + K[i-1][b - w[i]]$
      $K[i][b] \gets \max(K[i][b],\ take)$ // take item $i$
return $K[n][W]$
```

**Recovering the chosen items.** As with every DP, the table holds the value; the
_subset_ is recovered by walking backward from $K[n][W]$. At row $i$, if $K[i][b]
\neq K[i-1][b]$ then item $i$ was taken: record it and drop the budget to
$b - w_i$; otherwise it was skipped. Continue down to row $0$.

```algorithm
caption: $\textsc{Knapsack-Items}(K, w, n, W)$ — recover the optimal subset
number: 3
$S \gets \emptyset$
$b \gets W$
for $i \gets n$ downto $1$ do
  if $K[i][b] \neq K[i-1][b]$ then
    $S \gets S \cup \set{i}$ // item $i$ taken
    $b \gets b - w[i]$
return $S$
```

On the filled table above ($W = 5$), the walk starts at $K[4][5]$ and reads off
one decision per row, dropping the budget by $w_i$ whenever an item is taken:

$$
% caption: Backward reconstruction from $K[4][5]=16$. At each row, $K[i][b]=K[i-1][b]$
%          means item $i$ was skipped (budget unchanged); a jump means it was taken
%          (budget drops by $w_i$). Items $3$ and $2$ are recovered, weight $3+2=5$, value
%          $10+6=16$.
\begin{tikzpicture}[
  >=Stealth,
  row/.style={draw, minimum width=34mm, minimum height=8mm, inner sep=2pt, font=\small},
  take/.style={row, fill=acc!15, draw=acc, very thick},
  skip/.style={row},
  bud/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[skip] (r4) at (0,0)    {$i{=}4$:  K[4][5] = K[3][5]};
  \node[take] (r3) at (0,-1.1) {$i{=}3$:  K[3][5] not= K[2][5]};
  \node[take] (r2) at (0,-2.2) {$i{=}2$:  K[2][2] not= K[1][2]};
  \node[skip] (r1) at (0,-3.3) {$i{=}1$:  K[1][0] = K[0][0]};
  % decision + budget column on the right, dropping as items are taken
  \node[bud, anchor=west] at (2.05,0)    {skip, $b{=}5$};
  \node[bud, anchor=west, acc] at (2.05,-1.1) {take $3$, b: 5 to 2};
  \node[bud, anchor=west, acc] at (2.05,-2.2) {take $2$, b: 2 to 0};
  \node[bud, anchor=west] at (2.05,-3.3) {skip, $b{=}0$};
  \draw[->, red!75!black, thick] (r4.south) -- (r3.north);
  \draw[->, red!75!black, thick] (r3.south) -- (r2.north);
  \draw[->, red!75!black, thick] (r2.south) -- (r1.north);
  \node[bud, acc, align=center] at (0,-4.25) {chosen items 2 and 3, \ value $16$};
\end{tikzpicture}
$$

The same walk drawn on the grid is a staircase: a _vertical_ step means the item
was skipped (budget held), and a _diagonal drop_ down and to the left means it was
taken (budget falls by $w_i$). The path starts at the answer $K(4,5)$ and lands at
the origin $K(0,0)$; the diagonal drops mark exactly the chosen items.

$$
% caption: The traceback path on the value grid. From the answer $K(4,5)=16$, a vertical
%          move (skip) keeps the budget; a diagonal move down-left (take) drops it by
%          $w_i$. The two diagonal drops recover items $3$ and $2$; the path ends at
%          $K(0,0)$.
\begin{tikzpicture}[
  >=Stealth,
  every node/.style={draw, minimum size=8mm, inner sep=1pt, font=\small},
  lbl/.style={draw=none},
  on/.style={fill=acc!45},
  seen/.style={fill=acc!15}]
  \definecolor{acc}{HTML}{2348F2}
  \node[lbl] at (0,0) {\texttt{K(i,w)}};
  \foreach \w in {0,...,5} { \node[lbl] at (\w+1,0) {$w{=}\w$}; }
  \node[lbl] at (0,-1) {$i{=}0$};
  \node[lbl] at (0,-2) {$1\ (w{=}1)$};
  \node[lbl] at (0,-3) {$2\ (w{=}2)$};
  \node[lbl] at (0,-4) {$3\ (w{=}3)$};
  \node[lbl] at (0,-5) {$4\ (w{=}5)$};
  % row 0
  \node[on] (c00) at (1,-1) {0}; \node at (2,-1) {0}; \node at (3,-1) {0}; \node at (4,-1) {0}; \node at (5,-1) {0}; \node at (6,-1) {0};
  % row 1
  \node at (1,-2) {0}; \node at (2,-2) {1}; \node at (3,-2) {1}; \node at (4,-2) {1}; \node at (5,-2) {1}; \node at (6,-2) {1};
  % row 2
  \node at (1,-3) {0}; \node at (2,-3) {1}; \node[on] (c22) at (3,-3) {6}; \node at (4,-3) {7}; \node at (5,-3) {7}; \node at (6,-3) {7};
  % row 3
  \node at (1,-4) {0}; \node at (2,-4) {1}; \node at (3,-4) {6}; \node at (4,-4) {10}; \node at (5,-4) {11}; \node[on] (c35) at (6,-4) {16};
  % row 4
  \node at (1,-5) {0}; \node at (2,-5) {1}; \node at (3,-5) {6}; \node at (4,-5) {10}; \node at (5,-5) {11}; \node[on] (c45) at (6,-5) {16};
  % staircase path routed through the row/column gaps so no arrow crosses a cell interior
  \draw[->, very thick, red!75!black] (c45.north) -- (c35.south);
  \draw[->, very thick, red!75!black] (c35.north) -- (6,-3.5) -- (3,-3.5) -- (c22.south);
  \draw[->, very thick, red!75!black] (c22.north) -- (3,-2.5) -- (1.5,-2.5) -- (1.5,-1) -- (c00.east);
  \node[lbl, anchor=west, text=red!75!black, align=left] at (6.7,-5) {skip item $4$\\(budget held)};
  \node[lbl, anchor=west, text=red!75!black, align=left] at (6.7,-3.5) {take item $3$\\($w$ drops $3$)};
  \node[lbl, anchor=north, text=red!75!black, align=center] at (2.3,-5.75) {take item $2$: $w$ drops $2$};
\end{tikzpicture}
$$

::impl{algo="knapsack"}

## Running time and the pseudo-polynomial trap

The table has $(n + 1)(W + 1)$ entries, each filled in $\Theta(1)$, so
$\textsc{Knapsack-01}$ runs in
$$
\Theta(nW)
$$
time and space. (Space drops to $\Theta(W)$ if only the value is needed, since
each row reads only the previous one, so scan $b$ from high to low to reuse a
single array.)

The descending sweep is the correctness argument for the 1-D version: when we
apply an item, $K[b - w_i]$ must still hold the value from
_before_ this item was available, so we must reach $b$ before we overwrite
$b - w_i$ — that is, go high to low.

$$
% caption: 0/1 knapsack on one rolling array, applying item $2$ ($w{=}2,v{=}6$) with the
%          budget swept $b = 5 \to 2$ (descending). Each update
%          $K[b] \gets \max(K[b],\,6 + K[b{-}2])$ reads $K[b{-}2]$ before it is
%          overwritten, so item $2$ is used at most once.
\begin{tikzpicture}[
  >=Stealth,
  cell/.style={draw, minimum size=9mm, inner sep=1pt, font=\small},
  upd/.style={cell, fill=acc!18},
  lbl/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[lbl] at (-1.85,0) {before};
  \foreach \v/\x in {0/0,1/1,1/2,1/3,1/4,1/5} { \node[cell] at (\x,0) {$\v$}; }
  \foreach \x in {0,...,5} { \node[lbl] at (\x,0.72) {$b{=}\x$}; }
  \node[lbl] at (-1.85,-2.2) {after};
  \foreach \v/\x/\s in {0/0/cell,1/1/cell,6/2/upd,7/3/upd,7/4/upd,7/5/upd} { \node[\s] at (\x,-2.2) {$\v$}; }
  \draw[->, thick, red!75!black] (5.55,-1.1) -- (1.55,-1.1) node[midway, above, draw=none, font=\footnotesize, red!75!black] {sweep $b$ high to low};
\end{tikzpicture}
$$

Sweeping the other way, low to high, would let $K[b - w_i]$ already include item
$2$, silently packing it twice — the reuse that the
[unbounded knapsack](/algorithms/dynamic-programming/coin-change-and-unbounded)
requires, and that the ascending sweep there deliberately permits.

The failure is easy to trace on the same array. Sweeping upward, $K[2]$ becomes
$6$ first. Then at $b = 4$ the update reads $K[4 - 2] = K[2]$, which _already_
holds item $2$; adding $v_2$ again yields $12$, as if two copies of a
weight-$2$ item were packed into a budget of $4$. The descending sweep reads
$K[2]$ while it still holds its pre-item value, so no cell is ever charged
item $2$ twice.

$$
% caption: The ascending sweep double-counts item $2$ ($w{=}2,v{=}6$). Updating $b=2$
%          first makes $K[2]=6$; the later update at $b=4$ then reads that fresh $K[2]$
%          and adds $v_2$ again, giving $12$ — item $2$ packed twice into a budget of $4$.
\begin{tikzpicture}[
  >=Stealth,
  cell/.style={draw, minimum size=9mm, inner sep=1pt, font=\small},
  bad/.style={cell, fill=acc!18},
  lbl/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[lbl] at (-1.85,0) {before};
  \foreach \v/\x in {0/0,1/1,1/2,1/3,1/4,1/5} { \node[cell] at (\x,0) {$\v$}; }
  \foreach \x in {0,...,5} { \node[lbl] at (\x,0.72) {$b{=}\x$}; }
  \node[lbl] at (-1.85,-2.2) {after};
  \foreach \v/\x/\s in {0/0/cell,1/1/cell,6/2/bad,7/3/cell,12/4/bad,13/5/cell} { \node[\s] at (\x,-2.2) {$\v$}; }
  \node[lbl, red!75!black] at (4,-3.15) {\texttt{12 = item 2 counted twice}};
  \draw[->, thick, red!75!black] (1.45,-1.1) -- (5.55,-1.1) node[midway, above, draw=none, font=\footnotesize, red!75!black] {sweep $b$ low to high (wrong)};
\end{tikzpicture}
$$

That $\Theta(nW)$ looks polynomial, but the accounting deserves scrutiny.

**Is this _really_ "polynomial time"?** It is tempting to call $\Theta(nt)$ (or
$\Theta(nW)$) polynomial: the input is a list of $n+1$ numbers, so surely its
size is $\approx \Theta(n)$, and $nt$ is polynomial in $n$. That accounting is
wrong. We have to count the input's size _in bits_, not in numbers. This is the same bit-length accounting that underlies
[asymptotic analysis](/algorithms/foundations/asymptotic-analysis).

> **Remark (An honest size parameter).** Suppose each $a_i$ fits in $b$ bits, so
> $0 \le a_i \le 2^b - 1$, and likewise $0 \le t \le 2^b - 1$. Then the _entire_
> input — the $n$ integers plus the target — is written in about $(n+1)b$ bits.
> That, not $n$ alone, is the honest size parameter.

Now rewrite the running time against $b$. Since $t$ can be as large as $2^b - 1$,
$$
\Theta(nt) \;=\; \Theta\!\parens{n \cdot 2^{b}},
$$
which is **exponential** in $b$, the number of bits of a single input integer.
Doubling the bits used to write the target squares $t$ and thus squares the
running time. An algorithm whose time is polynomial in the _numeric value_ of an
input but exponential in its _encoded length_ is called **pseudo-polynomial**: it
counts as "polynomial" only if we dishonestly pretend an integer $s$ has size
$|s|$ rather than its true size $\Theta(\log |s|)$.[^erickson-knap] Such running
times are central to
[coping with hardness](/algorithms/intractability/coping-with-hardness).

> **Remark (Pseudo-polynomial complexity).** Can we get a _real_ polynomial-time algorithm? That would mean running time
> $T(n, b) = \poly(n, b) = \Theta(n^{c_1} b^{c_2})$ for some
> constants $c_1, c_2$ — polynomial in the _bit length_, not the value.
> **Most likely not, unless $\mathrm{P} = \mathrm{NP}$:** $\textsc{Subset-sum}$
> (and hence 0/1 knapsack) is $\textsc{NP-complete}$.

The $\Theta(nt)$ DP is the best we currently know how to do. It is fast and
practical precisely when the numbers are small
(a target in the thousands, say), and uselessly slow when $t$ is a $200$-bit
integer, even though both instances have the same handful of elements. The
lesson generalizes: any DP whose table is indexed by a numeric quantity (a
target sum, a capacity) inherits this pseudo-polynomial character. The same
pattern recurs in
[coin change and the unbounded knapsack](/algorithms/dynamic-programming/coin-change-and-unbounded).

## Subset-sum as a special case

We opened with subset-sum and built knapsack on top of it; the reduction also
runs the other way, and making it precise shows the two problems are
equivalent. Take any subset-sum instance $\langle a_1, \dots, a_n\rangle$ with
target $t$, and feed it to 0/1 knapsack with each item's value equal to its
weight, $v_i = w_i = a_i$, and capacity $W = t$. The most value you can pack into
a capacity-$t$ knapsack is at most $t$, and it _equals_ $t$ exactly when some
subset of weights sums to $t$ without waste. So
$$
K(n, t) = t \iff \text{some sublist of } L \text{ sums to } t,
$$
and one call to $\textsc{Knapsack-01}$ answers subset-sum. The two recurrences have
the same shape with the $\lor$ of the boolean table promoted to a $\max$ over
values, which is why everything transfers: $\Theta(nt)$ time,
pseudo-polynomial, and $\textsc{NP-complete}$ / NP-hard in general.

## Where greed _does_ work: fractional knapsack

Change one rule, letting items be split so that we may take any fraction $0 \le x_i \le
1$ of item $i$, and the problem **fractional knapsack** becomes _easy_, solvable
by the very greedy strategy that failed the 0/1 version. Sort items by
value-per-weight ratio $v_i / w_i$ and take them greedily, highest ratio first,
slicing the last item to fill the knapsack exactly.

```algorithm
caption: $\textsc{Fractional-Knapsack}(w, v, n, W)$ — greedy, fractions allowed
number: 4
sort items so that $v[1]/w[1] \ge v[2]/w[2] \ge \cdots \ge v[n]/w[n]$
$value \gets 0$;  $b \gets W$ // remaining capacity
for $i \gets 1$ to $n$ do
  if $w[i] \le b$ then
    $value \gets value + v[i]$ // take all of item $i$
    $b \gets b - w[i]$
  else
    $value \gets value + v[i] \cdot (b / w[i])$ // fraction fills exactly
    return $value$
return $value$
```

This runs in $\Theta(n \log n)$; the sort dominates.

> **Claim.** The greedy by-ratio strategy is optimal for fractional knapsack.

> **Proof.** By an exchange argument. Consider any optimal solution and suppose it
> differs from the greedy one. Then it must take some amount of a lower-ratio item
> while leaving capacity that a higher-ratio item could fill. Swap an
> $\varepsilon$ of weight from the lower-ratio item to the higher-ratio one: the
> value strictly increases (or stays equal), and the capacity constraint still
> holds. Repeating these swaps rearranges any optimal solution into the greedy
> one without losing value, so the greedy solution is itself optimal.
> $\qed$

The contrast between the two variants is the point.

> **Remark (Greedy vs. DP).** The fractional relaxation has a greedy-choice property; the 0/1 problem does
> not. When we may take fractions, the most valuable per-unit material should
> always come first, and filling greedily can never be improved. When items are
> indivisible, that local argument breaks, since a high-ratio item can crowd out a
> better combination, and we are forced to consider subsets, which is what
> the $K(i, w)$ dynamic program does. One small change to the rules moves a
> problem across the line between _greedy_ and _dynamic programming_, and across
> the line between polynomial and NP-hard.

## Approximation and the two ways to be pseudo-polynomial

Knapsack's $\Theta(nW)$ table is _pseudo-polynomial_ — polynomial in the numeric
capacity $W$, exponential in its bit length. The same limitation makes possible a
strong approximation result: knapsack admits a **fully polynomial-time
approximation scheme** (FPTAS). Given any $\varepsilon > 0$, one can
find a packing within a $(1 - \varepsilon)$ factor of optimal in time
$O(n^3 / \varepsilon)$ — polynomial in both $n$ and $1/\varepsilon$ — by
dynamic-programming on _value_ instead of weight and then **rounding the
values**: divide every $v_i$ by a scaling factor $K = \varepsilon v_{\max}/n$ and
round, which shrinks the value-indexed table to polynomial size while losing at most
an $\varepsilon$ fraction of the objective (Ibarra and Kim, 1975; the treatment in
Vazirani's _Approximation Algorithms_ is the standard reference). Few NP-hard
problems can be approximated this well; knapsack can precisely _because_ it is
only weakly NP-hard, i.e. hard only when the numbers are large.

The complementary DP, keyed on value rather than weight ($D[v] =$ minimum weight
achieving value exactly $v$), runs in $\Theta(n \cdot V)$ where $V$ is the total
value, and is the one the FPTAS rounds; whichever of $W$ and $V$ is smaller gives the
better bound. Two related results extend this. The **meet-in-the-middle**
technique (Horowitz and Sahni, 1974) solves subset-sum in $O(2^{n/2})$ time by
splitting the items in half, enumerating each half's subset sums, and merging — far
better than $2^n$ when $W$ is astronomically large and the $\Theta(nW)$ table is
useless. And **strong** NP-hardness marks the boundary of the FPTAS approach:
problems like bin packing and 3-partition remain hard even with small numbers, so
no pseudo-polynomial algorithm exists for them unless P $=$ NP. The FPTAS
exploits precisely that large-number weakness of Knapsack.[^knap-beyond]

## Takeaways

- $\textsc{Subset-sum}$ and **0/1 knapsack** share one structure: a _two-dimensional_
  subproblem ($A(i,u)$ / $K(i,w)$) indexed by _items available_ and _budget
  remaining_, because how much budget is left is part of the state.
- The recurrence is the **include/exclude** choice on the last element: a $\lor$
  of two previous-row cells for subset-sum, a $\max$ for knapsack. Each cell
  depends on the one _directly above_ (exclude) and the one $a_i$/$w_i$ columns
  _to the left_ (include); the optimal subset is recovered by walking backward.
- $\Theta(nt)$ / $\Theta(nW)$ is **pseudo-polynomial**: polynomial in the
  numeric _value_ of the target, but with an honest size of $(n+1)b$ bits it is
  $\Theta(n \cdot 2^b)$, _exponential_ in the bit length $b$ of one integer.
- A _truly_ polynomial $\poly(n, b)$ algorithm is unlikely:
  $\textsc{Subset-sum}$ is $\textsc{NP-complete}$, so one exists only if
  $\mathrm{P} = \mathrm{NP}$.
- **Fractional knapsack** flips to a $\Theta(n\log n)$ _greedy_ algorithm:
  allowing fractions restores the greedy-choice property that indivisibility
  destroys, so one rule change crosses the line from NP-hard to easy.

[^skiena-knap]: **Skiena**, §10 — Dynamic Programming: 0/1 knapsack as a canonical NP-hard resource-allocation problem solved by DP.
[^clrs-knap]: **CLRS**, Ch. 15 — Dynamic Programming: the 0/1 knapsack value recurrence $K(i,w)$ taking the max of exclude and include.
[^erickson-knap]: **Erickson**, Ch. 3 — Dynamic Programming: the pseudo-polynomial $\Theta(nt)$ running time, exponential in the input's bit length.
[^knap-beyond]: **Ibarra & Kim** (1975) for the knapsack FPTAS by value-rounding (see **Vazirani**, _Approximation Algorithms_, Ch. 8); **Horowitz & Sahni** (1974) for the $O(2^{n/2})$ meet-in-the-middle subset-sum. Bin packing and 3-partition are strongly NP-hard, so they admit no pseudo-polynomial algorithm unless P $=$ NP.