Pattern visualizer
0-1 Knapsack Problem
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). 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..
1D dp, capacity scanned high-to-low so each item is used once
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.
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] + v6 RETURN dp[capacity]
← / → step · space play · Home restart