Unbounded Knapsack Problem in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Unbounded Knapsack Problem?

It is a problem where you have items with weights and values, and you want to fill a knapsack to maximize value. You can use unlimited copies of each item.

beginner

How does Unbounded Knapsack differ from 0/1 Knapsack?

In 0/1 Knapsack, each item can be chosen only once. In Unbounded Knapsack, you can choose any item multiple times.

intermediate

What is the main idea behind the dynamic programming solution for Unbounded Knapsack?

Build a table where each entry represents the maximum value for a given capacity. For each capacity, try all items and update the max value by including the item multiple times if possible.

intermediate

What is the time complexity of the Unbounded Knapsack dynamic programming solution?

It is O(n * W), where n is the number of items and W is the knapsack capacity.

beginner

Why can items be chosen multiple times in Unbounded Knapsack?

Because the problem allows unlimited copies of each item, unlike 0/1 Knapsack which restricts to one copy per item.

In Unbounded Knapsack, what can you do with each item?

A Cannot use it

B Use it unlimited times

C Use it twice at most

D Use it only once

Unbounded Knapsack allows unlimited use of each item.

What does the dynamic programming table store in Unbounded Knapsack?

A List of items chosen

B Minimum weight for each value

C Number of items used

D Maximum value for each capacity

The table stores the maximum value achievable for each capacity.

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

A Unbounded allows multiple copies, 0/1 does not

B 0/1 Knapsack allows multiple copies, Unbounded does not

C Both allow unlimited copies

D Neither allows multiple copies

Unbounded Knapsack allows unlimited copies of items; 0/1 Knapsack allows only one.

What is the time complexity of the Unbounded Knapsack DP solution?

A O(n^2)

B O(n + W)

C O(n * W)

D O(W^2)

The DP solution runs in O(n * W), where n is number of items and W is capacity.

If you have an item with weight 2 and value 3, can you use it 3 times in Unbounded Knapsack?

A Yes, if capacity allows

B No, only once

C No, only twice

D No, unlimited use is not allowed

You can use any item unlimited times as long as total weight fits capacity.

Explain how the dynamic programming approach solves the Unbounded Knapsack Problem.

Think about building solutions from smaller capacities up.

Describe the key difference between Unbounded Knapsack and 0/1 Knapsack and why it matters.

Focus on item usage limits.

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