Pattern visualizer

Unbounded Knapsack

The only difference from 0/1 knapsack is direction: sweeping capacity w UPWARD from each item's own weight means dp[w - weight] has already been updated by THIS SAME item earlier in the same pass, so picking the item again just reads its own fresher answer. Sweeping downward (0/1's trick) would force at most one copy per item, because it reads only the row from before the item was considered. Animated on: values = [3,4], weights = [2,3], W = 6 — each item can be used unlimited times; maximise total value that fits in capacity W..

dp[w] = max(dp[w], dp[w-weight]+value), swept forward so an item can feed itself

time O(n*W)space O(W)step 1 / 11

dp over capacity 0..6 — dp[w] = max value using capacity <= w

0123456

line 2

dp[0] = 0: with zero capacity nothing fits, so the base case is 0 for every item list.

Pseudocode

1FUNCTION unboundedKnapsack(values, weights, W):
2  dp[0..W] <- 0
3  FOR EACH item (value, weight):
4    FOR w FROM weight TO W:
5      IF dp[w-weight] + value > dp[w]:
6        dp[w] <- dp[w-weight] + value
7      // else dp[w] unchanged
8  RETURN dp[W]

← / → step · space play · Home restart

Where to practice Dynamic Programming

Practice Dynamic Programming problems All Dynamic Programming problems Back to roadmap