0/1 Knapsack

Maximizes value from items placed in a weight-limited knapsack.

Bookw=2 v=3

Musicw=3 v=4

Cameraw=4 v=5

Phonew=5 v=6

Capacity: 8

Step 1 of 39

0/1 Knapsack: 4 items, capacity = 8. Build a (5)×(9) table where dp[i][w] = max value using first i items with capacity w.

▶Algorithm

Knapsack(items, W):
dp[0][w] = 0 for all w
for i = 1..n, w = 0..W:
if item.weight > w:
  dp[i][w] = dp[i−1][w]
else:
  dp[i][w] = max(dp[i−1][w],
             dp[i−1][w−wt]+v)
backtrack to find selected items

Legend

Current cell

Dependencies

Optimal path

Computed

dp[i][w] = max value using the first i items with weight capacity w. Rows = items, columns = capacity.

1 / 39Speed