Page 32Dynamic Programming

32 — 0/1 Knapsack (DP)

DP table fill and backtracking chosen items.

0/1 Knapsack DP

Weights Values Capacity

Decision

For each item, choose: do not take it, or take it if weight allows.

dp[i][c] = dp[i-1][c] // exclude item i if weight[i] <= c: dp[i][c] = max(dp[i][c], value[i] + dp[i-1][c-weight[i]]) Backtrack: if dp[i][c] != dp[i-1][c], item i was chosen.