Course contentsShow
← Computer Science
Lesson 931 of 2,87222. Dynamic ProgrammingFree lesson

Unbounded Knapsack Problem

Solve knapsack variant where each item can be selected unlimited times for maximum value.

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 i with weight wt[i] and value val[i]:
    • If wt[i] <= w, you can take item i:
      • dp[w] = max(dp[w], dp[w - wt[i]] + val[i])

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.