0/1 Knapsack Problem — DP Table Animated

State

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

State

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

Transition

dp[i][w] = max(
  dp[i-1][w],           // skip item i
  dp[i-1][w - wt[i]] + val[i]  // take item i (if w >= wt[i])
);

Base cases

dp[0][w] = 0 for all w (no items = no value). dp[i][0] = 0 for all i (no capacity).

Space optimization

Only need previous row. Compress to 1D array, iterate weights in reverse to avoid reusing same item.

int[] dp = new int[W + 1];
for (int i = 0; i < N; i++)
  for (int w = W; w >= wt[i]; w--)
    dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);