Unbounded knapsack
HardTaking an item does not consume it
Problem
Maximize value in a knapsack of capacity W where each item may be taken unlimited times.
Like knapsack but each item can repeat, so fill capacities using the same item again.
The idea
The same knapsack recurrence except taking an item recurses on the same index, since the supply is unlimited. In the 1-D form that means iterating capacity forwards rather than backwards.
The trick
- Forward capacity loop allows reuse; backward forbids it (0/1 knapsack).
- O(n × capacity).
0
∞
∞
∞
∞
∞
∞
0
1
2
3
4
5
6
Step 1 of 8. dp[a] = fewest coins to make amount a. Coins 1, 3, 4. dp[0] = 0, the rest start at ∞. Values: 0, ∞, ∞, ∞, ∞, ∞, ∞.
1/8
Optimal
timeO(amount·coins)spaceO(amount)
Unbounded knapsack.
1const dp = Array(amount + 1).fill(Infinity);2dp[0] = 0;3for (let a = 1; a <= amount; a++)4 for (const c of coins)5 if (c <= a) dp[a] = Math.min(dp[a], 1 + dp[a - c]);6return dp[amount] === Infinity ? -1 : dp[amount];Input
- array
- [0, ∞, ∞, ∞, ∞, ∞, ∞]
Memory
- a
- —
- a−c
- —
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- wt = [2,4,6], val = [5,11,13], W = 10
- Output:
- 27
- Explanation:
- Reuse items freely for max value 27.
Example 2
- Input:
- wt = [1], val = [7], W = 3
- Output:
- 21
- Explanation:
- Take the weight-1 item 3 times → 21.
Example 3
- Input:
- wt = [3], val = [4], W = 2
- Output:
- 0
- Explanation:
- Nothing fits → 0.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.