1. Recurrence
if weight[i] <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
else:
dp[i][w] = dp[i-1][w]Loading...
Binary decision per item (take or skip) across capacities. Foundation for many resource allocation problems.
dp[i][w] best value using first i items
take vs skip item i-1
1D array backward iterate
if weight[i] <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
else:
dp[i][w] = dp[i-1][w]for each item i:
for w from W down to weight[i]:
dp[w] = max(dp[w], dp[w-weight[i]] + value[i])Descending w ensures dp[w-weight[i]] refers to previous item row.
Walk backwards: if value changed from previous row at capacity w, item was taken, subtract weight and continue.