0/1 Knapsack via Dynamic Programming

Problem

Given $n$ items with profit $p_i$, weight $w_i$, capacity $W$, maximize $\sum p_i x_i$ s.t. $\sum w_i x_i\le W$, $x_i\in\{0,1\}$ (no fractional).

Optimal Substructure & Recurrence

Let $dp[i][w]$ = max profit using first $i$ items with capacity $w$.
$$dp[0][w]=0,\; dp[i][0]=0\\ dp[i][w]=\begin{cases} dp[i-1][w] & w_i>w \\ \max(dp[i-1][w],\; dp[i-1][w-w_i]+p_i) & w_i\le w \end{cases}$$
Answer = $dp[n][W]$.

Algorithm

for w=0..W: dp[0][w]=0
for i=1..n:
  for w=0..W:
    if w_i <= w: dp[i][w]=max(dp[i-1][w], dp[i-1][w-w_i]+p_i)
    else dp[i][w]=dp[i-1][w]
// trace back to find chosen items

Time $O(nW)$ (pseudo-polynomial), Space $O(nW)$ → optimizable to $O(W)$ with 1D array iterating $w$ descending.

Why DP vs Greedy

Fractional knapsack greedy by $p_i/w_i$ is optimal $O(n\log n)$, but 0/1 knapsack greedy fails (needs DP). Example earlier where greedy ratio fails, DP finds optimal.

Example (for Q90 values)

$n=4$, $p=(10,5,7,11)$, $w=(3,4,3,5)$, $W=15$ → total weight 15 if take all → profit 33 optimal. Table yields $dp[4][15]=33$ (all items). Backtracking confirms inclusion of all.

Complexity

• $O(nW)$ time, $O(W)$ space optimized.
• Not polynomial in input size (W may be exponential in bits) → pseudo-polynomial; problem is NP-hard.