DSA DP: The 0/1 Knapsack Problem

The 0/1 Knapsack problem is the definitive introduction to 2D Dynamic Programming.

Problem: Maximize value given items with weight/value and a fixed capacity. You cannot split items (0 or 1).

State Transition

dp[i][w] = max value using first i items with capacity w.

if (wt[i-1] <= w)
    dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w-wt[i-1]]);
else
    dp[i][w] = dp[i-1][w];

Optimization: Can be reduced to O(W) space by iterating backwards.