DSA Tracker

Visualize

Knapsack with Duplicate Items

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

time O(n*W)space O(W)

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.

Details

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.

Problem:Knapsack with Duplicate ItemsMedium

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

step 1 / 11

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

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

Every step in words

Show all 11 steps
  1. dp[0] = 0: with zero capacity nothing fits, so the base case is 0 for every item list.
  2. item 0 (weight 2, value 3): taking it again gives dp[0] + 3 = 3, beating the current dp[2] = 0, so dp[2] <- 3.
  3. item 0 (weight 2, value 3): taking it again gives dp[1] + 3 = 3, beating the current dp[3] = 0, so dp[3] <- 3.
  4. item 0 (weight 2, value 3): taking it again gives dp[2] + 3 = 6, beating the current dp[4] = 0, so dp[4] <- 6.
  5. item 0 (weight 2, value 3): taking it again gives dp[3] + 3 = 6, beating the current dp[5] = 0, so dp[5] <- 6.
  6. item 0 (weight 2, value 3): taking it again gives dp[4] + 3 = 9, beating the current dp[6] = 0, so dp[6] <- 9.
  7. item 1 (weight 3, value 4): taking it again gives dp[0] + 4 = 4, beating the current dp[3] = 3, so dp[3] <- 4.
  8. item 1 (weight 3, value 4): dp[1] + 4 = 4 does not beat dp[4] = 6, so dp[4] stays put — skipping this item here was already better.
  9. item 1 (weight 3, value 4): taking it again gives dp[2] + 4 = 7, beating the current dp[5] = 6, so dp[5] <- 7.
  10. item 1 (weight 3, value 4): dp[3] + 4 = 8 does not beat dp[6] = 9, so dp[6] stays put — skipping this item here was already better.
  11. dp[6] = 9 is the answer: the best total value packable into capacity 6 when every item can be reused.

Now solve it yourself

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

Solve Knapsack with Duplicate Items in the editorAll Dynamic Programming problemsBack to roadmap