Unbounded Knapsack Problem
What you'll learn: How to maximize value in a knapsack when you can pick the same item multiple times.
The Core Idea
You've just learned the 0/1 Knapsack Problem where each item could be used at most once. The Unbounded Knapsack variant removes that restriction—now you can select each item unlimited times as long as your knapsack capacity allows.
Imagine a vending machine with unlimited stock: you have $10 and want maximum snacks. You can buy the same candy bar five times if that gives you the best value!
How It Differs from 0/1 Knapsack
In 0/1 Knapsack, after considering an item, you moved to the next item in your state. In Unbounded Knapsack, after taking an item, you can take it again—you stay with the same item index.
The State Transition
Define dp[w] = maximum value achievable with capacity w.
For each capacity from 1 to your knapsack limit:
- For each item
iwith weightwt[i]and valueval[i]:- If
wt[i] <= w, you can take itemi:dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
- If
Notice: we look at dp[w - wt[i]] (not a "previous item" state), which already allows that same item to have been picked before.
Example Intuition
Items: {weight=2, value=3}, {weight=3, value=4}, Capacity = 7
- You could take item 1 three times (weight 6, value 9) plus can't fit more
- Or item 2 twice (weight 6, value 8) plus item 1 once (weight 2, value 3) = total weight 8 ❌
- Best: Item 1 three times gives value 9
Key Takeaway: Unbounded Knapsack allows unlimited item reuse; update DP states by considering the same capacity tier, enabling repeated selection of high-value items.