Unbounded Knapsack Problem in DSA Python - Execution Trace

Concept Flow - Unbounded Knapsack Problem

Start with empty DP array

↓

For each capacity from 0 to W

↓

For each item

↓

If item weight <= capacity

Yes↓

Update DP[capacity

↓

Repeat for all capacities and items

↓

DP[W

↓

Return DP[W

We fill a DP array where each position represents max value for that capacity, updating it by considering all items repeatedly.

Execution Sample

DSA Python

weights = [1, 3, 4]
values = [10, 40, 50]
W = 7
DP = [0]*(W+1)
for cap in range(W+1):
  for i in range(len(weights)):
    if weights[i] <= cap:
      DP[cap] = max(DP[cap], DP[cap - weights[i]] + values[i])
print(DP[W])

Calculate max value for capacity 7 with items of weights [1,3,4] and values [10,40,50] allowing unlimited items.

Execution Table

Step	Operation	Capacity (cap)	Item (weight,value)	DP Update	DP Array State
1	Initialize DP	-	-	DP = [0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0]
2	cap=0, i=0	0	(1,10)	No update (weight > cap)	[0,0,0,0,0,0,0,0]
3	cap=0, i=1	0	(3,40)	No update (weight > cap)	[0,0,0,0,0,0,0,0]
4	cap=0, i=2	0	(4,50)	No update (weight > cap)	[0,0,0,0,0,0,0,0]
5	cap=1, i=0	1	(1,10)	DP[1] = max(0, DP[0]+10)=10	[0,10,0,0,0,0,0,0]
6	cap=1, i=1	1	(3,40)	No update (weight > cap)	[0,10,0,0,0,0,0,0]
7	cap=1, i=2	1	(4,50)	No update (weight > cap)	[0,10,0,0,0,0,0,0]
8	cap=2, i=0	2	(1,10)	DP[2] = max(0, DP[1]+10)=20	[0,10,20,0,0,0,0,0]
9	cap=2, i=1	2	(3,40)	No update (weight > cap)	[0,10,20,0,0,0,0,0]
10	cap=2, i=2	2	(4,50)	No update (weight > cap)	[0,10,20,0,0,0,0,0]
11	cap=3, i=0	3	(1,10)	DP[3] = max(0, DP[2]+10)=30	[0,10,20,30,0,0,0,0]
12	cap=3, i=1	3	(3,40)	DP[3] = max(30, DP[0]+40)=40	[0,10,20,40,0,0,0,0]
13	cap=3, i=2	3	(4,50)	No update (weight > cap)	[0,10,20,40,0,0,0,0]
14	cap=4, i=0	4	(1,10)	DP[4] = max(0, DP[3]+10)=50	[0,10,20,40,50,0,0,0]
15	cap=4, i=1	4	(3,40)	DP[4] = max(50, DP[1]+40)=50	[0,10,20,40,50,0,0,0]
16	cap=4, i=2	4	(4,50)	DP[4] = max(50, DP[0]+50)=50	[0,10,20,40,50,0,0,0]
17	cap=5, i=0	5	(1,10)	DP[5] = max(0, DP[4]+10)=60	[0,10,20,40,50,60,0,0]
18	cap=5, i=1	5	(3,40)	DP[5] = max(60, DP[2]+40)=60	[0,10,20,40,50,60,0,0]
19	cap=5, i=2	5	(4,50)	DP[5] = max(60, DP[1]+50)=60	[0,10,20,40,50,60,0,0]
20	cap=6, i=0	6	(1,10)	DP[6] = max(0, DP[5]+10)=70	[0,10,20,40,50,60,70,0]
21	cap=6, i=1	6	(3,40)	DP[6] = max(70, DP[3]+40)=80	[0,10,20,40,50,60,80,0]
22	cap=6, i=2	6	(4,50)	DP[6] = max(80, DP[2]+50)=80	[0,10,20,40,50,60,80,0]
23	cap=7, i=0	7	(1,10)	DP[7] = max(0, DP[6]+10)=90	[0,10,20,40,50,60,80,90]
24	cap=7, i=1	7	(3,40)	DP[7] = max(90, DP[4]+40)=90	[0,10,20,40,50,60,80,90]
25	cap=7, i=2	7	(4,50)	DP[7] = max(90, DP[3]+50)=90	[0,10,20,40,50,60,80,90]

💡 All capacities from 0 to 7 processed with all items, DP[7] = 90 is max value

Variable Tracker

Variable	Start	After cap=1	After cap=2	After cap=3	After cap=4	After cap=5	After cap=6	After cap=7
DP	[0,0,0,0,0,0,0,0]	[0,10,0,0,0,0,0,0]	[0,10,20,0,0,0,0,0]	[0,10,20,40,0,0,0,0]	[0,10,20,40,50,0,0,0]	[0,10,20,40,50,60,0,0]	[0,10,20,40,50,60,80,0]	[0,10,20,40,50,60,80,90]

Key Moments - 3 Insights

Why do we update DP[capacity] multiple times for the same capacity?

Because we consider all items for each capacity, updating DP[capacity] if using an item gives a better value. See steps 11-13 and 23-25 where DP[3] and DP[7] are updated multiple times.

Why can we use the same item multiple times in unbounded knapsack?

Because when updating DP[capacity], we use DP[capacity - item_weight], which may already include that item. This allows repeated use, as shown in step 8 where DP[2] uses DP[1] which used item 0.

Why does the DP array start with zeros?

Because with zero capacity, max value is zero, and initially no items are chosen. This base case is shown in step 1.

Visual Quiz - 3 Questions

Look at the execution table at step 12. What is the DP[3] value after considering item (3,40)?

A 50

B 30

C 40

D 0

💡 Hint

Check the DP Update column at step 12 where DP[3] is updated to max(30, 0+40)=40

At which capacity does the DP array first reach a value of 50?

A Capacity 3

B Capacity 4

C Capacity 5

D Capacity 6

💡 Hint

Look at DP Array State at step 14 where DP[4] becomes 50

If the item with weight 1 and value 10 was removed, how would DP[7] change?

A It would decrease because smaller weights help build up capacity

B It would increase because only bigger items remain

C It would remain 90

D It would become zero

💡 Hint

Refer to variable_tracker showing DP grows by adding small items repeatedly, removing weight 1 item reduces options

Concept Snapshot

Unbounded Knapsack Problem:
- Use DP array of size W+1 for capacities 0..W
- For each capacity, try all items
- Update DP[cap] = max(DP[cap], DP[cap - weight] + value)
- Items can be used unlimited times
- DP[W] gives max value achievable
- Time complexity: O(W * n)

Full Transcript

The Unbounded Knapsack Problem finds the maximum value achievable with unlimited copies of given items within a weight limit W. We use a DP array where each index represents capacity from 0 to W. For each capacity, we check all items. If an item's weight is less or equal to the capacity, we update the DP value by considering including that item. This update uses the DP value at capacity minus the item's weight plus the item's value, allowing repeated use of items. The DP array starts with zeros, representing zero value at zero capacity. After filling the DP array, the value at DP[W] is the maximum value possible. The execution table shows step-by-step updates of the DP array for capacity 0 to 7 with items of weights 1, 3, and 4 and values 10, 40, and 50 respectively. Key moments clarify why multiple updates happen per capacity, why repeated items are allowed, and the base case initialization. The visual quiz tests understanding of DP updates and effects of item removal.

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