DSA Tracker

Visualize

0 - 1 Knapsack Problem

1D dp, capacity scanned high-to-low so each item is used once

time O(n * capacity)space O(capacity)

dp[c] tracks the best value achievable in capacity c using items considered SO FAR. Updating capacity from high down to low for each item is the trick that enforces 'at most once': dp[c-w] still refers to a state that hasn't used this item yet (a low-to-high scan would let the same item get counted twice, since dp[c-w] could already include it).

Details

Animated on: weights=[1,3,4,5], values=[1,4,5,7], capacity=7 — maximize value without exceeding capacity, each item usable at most once.

Problem:0 - 1 Knapsack ProblemMedium

1D dp, capacity scanned high-to-low so each item is used once

step 1 / 19

0
[0]
0
[1]
0
[2]
0
[3]
0
[4]
0
[5]
0
[6]
0
[7]

1D dp array, dp[c] = best value achievable with capacity exactly-or-up-to c. Process items one at a time, capacity HIGH to LOW so each item is only used once.

Pseudocode
1FUNCTION knapsack(weights, values, capacity):
2  dp = a list of capacity+1 zeros (dp[c] = best value for capacity c)
3  FOR each item with weight w and value v:
4    FOR c from capacity down to w:
5      dp[c] = the larger of dp[c] and dp[c-w] + v
6  RETURN dp[capacity]

← / → step · space play · Home restart

Every step in words

Show all 19 steps
  1. 1D dp array, dp[c] = best value achievable with capacity exactly-or-up-to c. Process items one at a time, capacity HIGH to LOW so each item is only used once.
  2. item(w=1,v=1), c=7: skip gives 0, take gives dp[6]+1=1. Take it — dp[7]=1.
  3. item(w=1,v=1), c=6: skip gives 0, take gives dp[5]+1=1. Take it — dp[6]=1.
  4. item(w=1,v=1), c=5: skip gives 0, take gives dp[4]+1=1. Take it — dp[5]=1.
  5. item(w=1,v=1), c=4: skip gives 0, take gives dp[3]+1=1. Take it — dp[4]=1.
  6. item(w=1,v=1), c=3: skip gives 0, take gives dp[2]+1=1. Take it — dp[3]=1.
  7. item(w=1,v=1), c=2: skip gives 0, take gives dp[1]+1=1. Take it — dp[2]=1.
  8. item(w=1,v=1), c=1: skip gives 0, take gives dp[0]+1=1. Take it — dp[1]=1.
  9. item(w=3,v=4), c=7: skip gives 1, take gives dp[4]+4=5. Take it — dp[7]=5.
  10. item(w=3,v=4), c=6: skip gives 1, take gives dp[3]+4=5. Take it — dp[6]=5.
  11. item(w=3,v=4), c=5: skip gives 1, take gives dp[2]+4=5. Take it — dp[5]=5.
  12. item(w=3,v=4), c=4: skip gives 1, take gives dp[1]+4=5. Take it — dp[4]=5.
  13. item(w=3,v=4), c=3: skip gives 1, take gives dp[0]+4=4. Take it — dp[3]=4.
  14. item(w=4,v=5), c=7: skip gives 5, take gives dp[3]+5=9. Take it — dp[7]=9.
  15. item(w=4,v=5), c=6: skip gives 5, take gives dp[2]+5=6. Take it — dp[6]=6.
  16. item(w=4,v=5), c=5: skip gives 5, take gives dp[1]+5=6. Take it — dp[5]=6.
  17. item(w=5,v=7), c=6: skip gives 6, take gives dp[1]+7=8. Take it — dp[6]=8.
  18. item(w=5,v=7), c=5: skip gives 6, take gives dp[0]+7=7. Take it — dp[5]=7.
  19. dp[7] = 9 — the best total value fitting in capacity 7.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve 0 - 1 Knapsack Problem in the editorAll Dynamic Programming problemsBack to roadmap