Unbounded Knapsack Problem in DSA Python - Build from Scratch

Unbounded Knapsack Problem

📖 Scenario: You are packing a bag for a hiking trip. You have several types of items, each with a weight and a value. You can take any number of each item type, even multiple times. Your goal is to maximize the total value without exceeding the bag's weight limit.

🎯 Goal: Build a program that calculates the maximum value you can carry in your bag using the unbounded knapsack approach.

📋 What You'll Learn

Create a list of item weights called weights with values [2, 3, 4]

Create a list of item values called values with values [15, 20, 30]

Create an integer variable called max_weight set to 7

Use a list called dp to store maximum values for weights from 0 to max_weight

Use a for loop with variable w from 1 to max_weight

Use a nested for loop with variable i to iterate over item indices

Update dp[w] with the maximum value possible by including items multiple times

Print the maximum value stored in dp[max_weight]

💡 Why This Matters

🌍 Real World

This problem models packing efficiently for trips, shipping, or resource allocation where items can be repeated.

💼 Career

Understanding unbounded knapsack helps in optimization tasks in software engineering, logistics, and finance.

1

Create the item weights and values lists

Create a list called weights with values [2, 3, 4] and a list called values with values [15, 20, 30]

DSA Python

# Create the weights and values lists
# Your code here

Hint

Use square brackets to create lists with the exact numbers given.

2

Set the maximum weight the bag can carry

Create an integer variable called max_weight and set it to 7

DSA Python

weights = [2, 3, 4]
values = [15, 20, 30]
# Set the max_weight variable
# Your code here

Hint

Use a simple assignment to create the variable max_weight.

3

Calculate maximum values for each weight using unbounded knapsack logic

Create a list called dp of size max_weight + 1 filled with zeros. Use a for loop with variable w from 1 to max_weight inclusive. Inside it, use another for loop with variable i to iterate over the indices of weights. If weights[i] is less than or equal to w, update dp[w] to the maximum of its current value and values[i] + dp[w - weights[i]].

DSA Python

weights = [2, 3, 4]
values = [15, 20, 30]
max_weight = 7
# Create dp list and fill with zeros
# Use nested loops to fill dp with max values
# Your code here

Hint

Remember to initialize dp with zeros and use two loops: one for weights and one for items.

4

Print the maximum value for the full bag weight

Print the value stored in dp[max_weight] to show the maximum value that can be carried.

DSA Python

weights = [2, 3, 4]
values = [15, 20, 30]
max_weight = 7
dp = [0] * (max_weight + 1)
for w in range(1, max_weight + 1):
    for i in range(len(weights)):
        if weights[i] <= w:
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
# Print the maximum value for max_weight
# Your code here

Hint

Use print(dp[max_weight]) to show the final answer.

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