Unbounded Knapsack Problem in DSA Python

Mental Model

We want to fill a bag with items to get the most value, and we can use each item as many times as we want.

Analogy: Imagine you have a backpack and unlimited candies of different sizes and tastiness. You want to fill your backpack to get the tastiest candies possible, and you can pick any candy multiple times.

Capacity: 5
Items: [weight: 1, value: 10], [weight: 3, value: 40], [weight: 4, value: 50]

Backpack capacity -> [0][1][2][3][4][5]
Values stored ->    [0][ ][ ][ ][ ][ ]

Dry Run Walkthrough

Input: items = [(weight=1, value=10), (weight=3, value=40), (weight=4, value=50)], capacity = 5

Goal: Find the maximum value we can get by filling the backpack of capacity 5 using unlimited items.

Step 1: Start with capacity 0, max value is 0 because no space

Capacity: 0 -> max value: 0

Why: No capacity means no items can be added

Step 2: For capacity 1, try item with weight 1: value 10 fits, update max value to 10

Capacity: 1 -> max value: 10

Why: Item with weight 1 fits exactly, so max value is 10

Step 3: For capacity 2, try item weight 1 twice: value 10 + 10 = 20, update max value to 20

Capacity: 2 -> max value: 20

Why: We can use item with weight 1 twice to fill capacity 2

Step 4: For capacity 3, try item weight 3: value 40 fits better than three times item 1 (30), update max value to 40

Capacity: 3 -> max value: 40

Why: Item with weight 3 has higher value than three items of weight 1

Step 5: For capacity 4, try item weight 4: value 50 fits better than combinations before, update max value to 50

Capacity: 4 -> max value: 50

Why: Item with weight 4 has highest value for capacity 4

Step 6: For capacity 5, try item weight 1 + capacity 4 max value: 10 + 50 = 60, update max value to 60

Capacity: 5 -> max value: 60

Why: Using item weight 1 plus best for capacity 4 gives max value 60

Result:

Capacity: 5 -> max value: 60
Answer: Maximum value = 60

Annotated Code

DSA Python

from typing import List, Tuple

class UnboundedKnapsack:
    def max_value(self, capacity: int, items: List[Tuple[int, int]]) -> int:
        dp = [0] * (capacity + 1)  # dp[i] stores max value for capacity i
        for c in range(1, capacity + 1):
            for weight, value in items:
                if weight <= c:
                    dp[c] = max(dp[c], dp[c - weight] + value)  # choose best value including current item
        return dp[capacity]

if __name__ == '__main__':
    items = [(1, 10), (3, 40), (4, 50)]
    capacity = 5
    knapsack = UnboundedKnapsack()
    result = knapsack.max_value(capacity, items)
    print(f"Maximum value = {result}")

for c in range(1, capacity + 1):

iterate through all capacities from 1 to max capacity

for weight, value in items:

check each item to see if it fits in current capacity

if weight <= c:

only consider items that fit in current capacity

dp[c] = max(dp[c], dp[c - weight] + value)

update max value for capacity c by including current item multiple times

Output

Maximum value = 60

Complexity Analysis

Time: O(n * capacity) because we check each item for every capacity from 1 to capacity

Space: O(capacity) because we store max values for all capacities up to the given capacity

vs Alternative: Compared to 0/1 knapsack which only allows one use per item, unbounded knapsack allows repeated use, but time complexity remains similar with dynamic programming

Edge Cases

capacity = 0

max value is 0 because no capacity to hold items

DSA Python

dp = [0] * (capacity + 1)

items list is empty

max value is 0 because no items to choose from

DSA Python

for weight, value in items:

items with weight greater than capacity

those items are ignored because they don't fit

DSA Python

if weight <= c:

When to Use This Pattern

When you see a problem asking for maximum value with unlimited item usage and capacity constraints, reach for the unbounded knapsack pattern because it handles repeated item selection efficiently.

Common Mistakes

Mistake: Treating unbounded knapsack like 0/1 knapsack and not allowing multiple uses of the same item
Fix: Use dp[c - weight] + value to allow repeated use of items instead of only once

Mistake: Not initializing dp array properly leading to incorrect base cases
Fix: Initialize dp array with zeros for all capacities including zero

Summary

Calculates the maximum value achievable with unlimited use of given items within a capacity limit.

Use when you can pick items multiple times to maximize value under a weight constraint.

The key is to build solutions for all capacities by considering repeated use of each item.

Practice

1. What is the main difference between the 0/1 Knapsack problem and the Unbounded Knapsack problem?

easy

A. Unbounded Knapsack only works with fractional items.

B. In Unbounded Knapsack, you can use unlimited copies of each item.

C. In Unbounded Knapsack, items cannot be repeated.

D. Unbounded Knapsack has a fixed number of items to choose from.

Solution

1. Step 1: Understand 0/1 Knapsack constraints

   In 0/1 Knapsack, each item can be chosen at most once.

2. Step 2: Understand Unbounded Knapsack constraints

   In Unbounded Knapsack, you can pick any item multiple times without limit.

3. Final Answer:

   In Unbounded Knapsack, you can use unlimited copies of each item. -> Option B

4. Quick Check:

   Unbounded means unlimited items [OK]

Hint: Remember: Unbounded means unlimited copies allowed [OK]

Common Mistakes:

• Confusing Unbounded with fractional knapsack
• Thinking items can be chosen only once
• Assuming fixed number of items

2. Which of the following is the correct Python syntax to initialize a list dp of size W+1 with all zeros for the Unbounded Knapsack problem?

easy

A. dp = list(0, W+1)

B. dp = (0) * (W+1)

C. dp = [0] * (W+1)

D. dp = [0 for i in range(W)]

Solution

1. Step 1: Understand list initialization in Python

   To create a list of zeros of length W+1, use list multiplication: [0] * (W+1).

2. Step 2: Check each option

   dp = [0] * (W+1) correctly uses [0] * (W+1). dp = (0) * (W+1) is invalid syntax. dp = [0 for i in range(W)] creates a list of length W, not W+1. dp = list(0, W+1) is invalid syntax.

3. Final Answer:

   dp = [0] * (W+1) -> Option C

4. Quick Check:

   List * integer repeats list [OK]

Hint: Use [0] * (size) to create zero-filled list fast [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Off-by-one size errors
• Using invalid list constructor syntax

3. What will be the output of the following code snippet for weights = [1, 3], values = [10, 40], and W = 5?

dp = [0] * (W+1)
for i in range(1, W+1):
    for j in range(len(weights)):
        if weights[j] <= i:
            dp[i] = max(dp[i], dp[i - weights[j]] + values[j])
print(dp[W])

medium

A. 60

B. 50

C. 90

D. 80

Solution

1. Step 1: Trace dp array updates for each capacity i

   For i=1: dp[1] = max(0, dp[0]+10) = 10
   i=2: dp[2] = max(0, dp[1]+10) = 20
   i=3: dp[3] = max(0, dp[2]+10, dp[0]+40) = max(0,30,40) = 40
   i=4: dp[4] = max(0, dp[3]+10, dp[1]+40) = max(0,50,50) = 50
   i=5: dp[5] = max(0, dp[4]+10, dp[2]+40) = max(0,60,60) = 60

2. Step 2: Final dp[W] value

   The code prints dp[5] which is 60.

3. Final Answer:

   60 -> Option A

4. Quick Check:

   Unbounded knapsack max value for W=5 is 60 [OK]

Hint: Trace dp updates for each weight capacity [OK]

Common Mistakes:

• Ignoring multiple item usage
• Off-by-one errors in dp indexing
• Mixing up weights and values

4. Identify the error in the following Unbounded Knapsack code snippet:

def unbounded_knapsack(W, weights, values):
    dp = [0] * W
    for i in range(1, W+1):
        for j in range(len(weights)):
            if weights[j] <= i:
                dp[i] = max(dp[i], dp[i - weights[j]] + values[j])
    return dp[W]

medium

A. Return statement should be dp[W-1].

B. Loop should start from 0, not 1.

C. Weights and values lists should be sorted.

D. dp list size should be W+1, not W.

Solution

1. Step 1: Check dp list initialization

   dp is initialized with size W, but indices go up to W (inclusive), so dp should be size W+1.

2. Step 2: Impact of incorrect dp size

   Accessing dp[W] will cause an IndexError because dp has indices 0 to W-1 only.

3. Final Answer:

   dp list size should be W+1, not W. -> Option D

4. Quick Check:

   dp size must cover all indices up to W [OK]

Hint: dp size must be W+1 to include capacity W [OK]

Common Mistakes:

• Off-by-one dp size errors
• Ignoring index out of range errors
• Unnecessary sorting of weights/values

5. Given weights = [2, 3, 5], values = [50, 70, 100], and capacity W = 8, what is the maximum value achievable using the Unbounded Knapsack approach?

hard

A. 200

B. 170

C. 220

D. 250

Solution

1. Step 1: Calculate dp values for capacities 1 to 8

   Initialize dp = [0]*9
   i=1: no items fit, dp[1]=0
   i=2: dp[2]=max(0, dp[0]+50)=50
   i=3: dp[3]=max(0, dp[1]+50=0+50=50, dp[0]+70=70)=70
   i=4: dp[4]=max(dp[4], dp[2]+50=50+50=100, dp[1]+70=0+70=70)=100
   i=5: dp[5]=max(dp[5], dp[3]+50=70+50=120, dp[2]+70=50+70=120, dp[0]+100=100)=120
   i=6: dp[6]=max(dp[6], dp[4]+50=100+50=150, dp[3]+70=70+70=140, dp[1]+100=0+100=100)=150
   i=7: dp[7]=max(dp[7], dp[5]+50=120+50=170, dp[4]+70=100+70=170, dp[2]+100=50+100=150)=170
   i=8: dp[8]=max(dp[8], dp[6]+50=150+50=200, dp[5]+70=120+70=190, dp[3]+100=70+100=170)=200

2. Step 2: Check for better combinations

   Try combinations:
   Two 3-weight items + one 2-weight: 70+70+50=190
   One 5-weight + one 3-weight: 100+70=170
   Four 2-weight items: 50*4=200
   So max value is 200 at capacity 8.

3. Final Answer:

   200 -> Option A

4. Quick Check:

   Unbounded knapsack max value for W=8 is 200 [OK]

Hint: Try all item combinations for each capacity [OK]

Common Mistakes:

• Ignoring multiple usage of items
• Not checking all item weights for each capacity
• Off-by-one errors in dp indexing