Unbounded Knapsack Problem in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unbounded Knapsack DP Table

What is the final maximum value returned by this unbounded knapsack function for the given inputs?

DSA Python

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

W = 8
wt = [2, 3, 5]
val = [15, 20, 50]
n = len(wt)
print(unbounded_knapsack(W, wt, val, n))

A 80

B 120

C 100

D 70

💡 Hint

Think about how many times each item can be chosen to maximize value without exceeding weight.

The function uses dynamic programming to find the maximum value for weight 8.

By choosing the 5-weight item once (value 50) and the 3-weight item once (value 20), total weight is 8 and value is 70.

But better is choosing the 3-weight item twice (20+20=40) and the 2-weight item twice (15+15=30), total value 70.

Actually, the best is choosing the 5-weight item once (50) and the 2-weight item once (15), total 65.

After checking all combinations, the maximum value is 70.

🧠 Conceptual

intermediate

Understanding Unbounded Knapsack Choices

In the unbounded knapsack problem, why can we use the same item multiple times?

A Because the items are divisible into smaller parts to fit the knapsack.

B Because the problem allows unlimited quantity of each item to maximize value within weight limit.

C Because the knapsack capacity is infinite, so all items fit.

D Because each item can only be chosen once but with different weights.

💡 Hint

Think about the difference between 0/1 knapsack and unbounded knapsack.

Unbounded knapsack means you can pick any item multiple times as long as total weight does not exceed capacity.

Option B correctly states this.

Option B describes fractional knapsack, which is different.

Option B is false because capacity is limited.

Option B is false because items can be chosen multiple times, not just once.

🔧 Debug

advanced

Identify the Error in Unbounded Knapsack Implementation

What error does this code produce when run, and why?

DSA Python

def unbounded_knapsack(W, wt, val, n):
    dp = [[0] * (W + 1)] * (n + 1)
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i][w - wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

W = 5
wt = [1, 3, 4]
val = [10, 40, 50]
n = len(wt)
print(unbounded_knapsack(W, wt, val, n))

A The code prints 60 but dp table updates incorrectly due to shallow copy.

B The code raises an IndexError due to wrong indexing.

C The code prints 90 correctly.

D The code raises a TypeError because dp is not a list.

💡 Hint

Check how the dp table is initialized and updated.

The dp table is initialized with dp = [[0] * (W + 1)] * (n + 1), which creates shallow copies of the same list.

Updating dp[i][w] changes multiple rows simultaneously, causing incorrect results.

The output is 60, which happens to be correct, but due to the shallow copy.

Correct initialization should use a list comprehension to create independent rows.

❓ Predict Output

advanced

Output of Recursive Unbounded Knapsack with Memoization

What is the output of this recursive unbounded knapsack function with memoization for the given inputs?

DSA Python

def unbounded_knapsack_recursive(W, wt, val, n, memo):
    if W == 0:
        return 0
    if W in memo:
        return memo[W]
    max_val = 0
    for i in range(n):
        if wt[i] <= W:
            max_val = max(max_val, val[i] + unbounded_knapsack_recursive(W - wt[i], wt, val, n, memo))
    memo[W] = max_val
    return max_val

W = 7
wt = [1, 3, 4]
val = [10, 40, 50]
n = len(wt)
memo = {}
print(unbounded_knapsack_recursive(W, wt, val, n, memo))

A 140

B 110

C 90

D 130

💡 Hint

Try to find the best combination of items to fill weight 7 with maximum value.

Possible combinations:

• 7 items of weight 1: 7*10=70
• 2 items of weight 3 + 1 item of weight 1: 2*40 + 10 = 90
• 1 item of weight 4 + 1 item of weight 3: 50 + 40 = 90
• 1 item of weight 4 + 3 items of weight 1: 50 + 30 = 80

Best is 90.

The code returns 90 correctly.

🧠 Conceptual

expert

Time Complexity of Unbounded Knapsack DP Solution

What is the time complexity of the dynamic programming solution for the unbounded knapsack problem with capacity W and n items?

A O(n * W)

B O(W^n)

C O(n^2 * W)

D O(n + W)

💡 Hint

Consider the nested loops in the DP solution.

The DP solution uses two nested loops: one over weights from 0 to W, and one over n items.

Each dp[i] is computed by checking all n items.

Thus, time complexity is O(n * W).

Option A is exponential, incorrect.

Option A is higher than needed.

Option A is linear, incorrect.

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