Unbounded Knapsack Problem in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the DP array for the unbounded knapsack problem.

DSA Python

dp = [0] * ([1] + 1)

Drag options to blanks, or click blank then click option'

AW

Bn

Cweights

Dvalues

Attempts:

3 left

💡 Hint

Common Mistakes

Using number of items 'n' instead of capacity 'W' for dp size.

Using weights or values list length instead of capacity.

The DP array size depends on the maximum weight capacity W, so we create an array of size W + 1.

2fill in blank

medium

Complete the code to iterate over all weights from 1 to W.

DSA Python

for weight in range(1, [1] + 1):

Drag options to blanks, or click blank then click option'

An

Bmax_weight

Clen(weights)

DW

Attempts:

3 left

💡 Hint

Common Mistakes

Using number of items 'n' instead of capacity 'W' in the loop.

Using incorrect variable names.

We iterate from 1 to the maximum capacity W to fill the DP array.

3fill in blank

hard

Fix the error in the condition to check if the current item can fit in the knapsack.

DSA Python

if weights[i] [1] weight:

Drag options to blanks, or click blank then click option'

A>=

B<=

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using only less than '<' excludes items that exactly fit.

Using greater than operators causes logic errors.

The item can be included if its weight is less than or equal to the current weight capacity.

4fill in blank

hard

Fill both blanks to update the DP array with the maximum value including the current item.

DSA Python

dp[weight] = max(dp[weight], dp[weight [1] weights[i]] [2] values[i])

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction for the index.

Using multiplication or division instead of addition for the value.

We subtract the item's weight from the current weight to find the remaining capacity, then add the item's value to the DP value at that remaining capacity.

5fill in blank

hard

Fill all three blanks to complete the unbounded knapsack function.

DSA Python

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

Drag options to blanks, or click blank then click option'

Aweights

Bvalues

CW

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'n' instead of 'W' for capacity.

Swapping order of weights and values.

The function takes three parameters: weights list, values list, and the maximum capacity W.

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