0 1 Knapsack Problem in DSA Python - Execution Trace

Concept Flow - 0 1 Knapsack Problem

Start with empty knapsack

↓

For each item i

↓

For each weight w from 0 to max W

↓

Check if item i fits (weight[i

Yes No↓

Include item i: value[i

↓

Choose max of include/exclude

↓

Store result in dp[i

↓

Repeat for all items and weights

↓

Final answer in dp[n

We fill a table step-by-step deciding for each item and weight whether to include or exclude the item to maximize value.

Execution Sample

DSA Python

weights = [1, 3, 4]
values = [1, 4, 5]
W = 7

# Initialize dp table with zeros
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]

# dp table initialization and filling
for i in range(1, n + 1):
    for w in range(W + 1):
        if weights[i - 1] <= w:
            dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
        else:
            dp[i][w] = dp[i - 1][w]

This code fills the dp table for 3 items and max weight 7 to find max value.

Execution Table

Step	Operation	Item (i)	Weight (w)	Include Value	Exclude Value	Chosen Value	DP Table Row i State
1	Initialize dp row 0	0	0-7	-	-	0	[0, 0, 0, 0, 0, 0, 0, 0]
2	Item 1, w=0	1	0	-	0	0	[0, -, -, -, -, -, -, -]
3	Item 1, w=1	1	1	1 + dp[0][0]=1	dp[0][1]=0	1	[0, 1, -, -, -, -, -, -]
4	Item 1, w=2	1	2	1 + dp[0][1]=1	dp[0][2]=0	1	[0, 1, 1, -, -, -, -, -]
5	Item 1, w=3	1	3	1 + dp[0][2]=1	dp[0][3]=0	1	[0, 1, 1, 1, -, -, -, -]
6	Item 1, w=4	1	4	1 + dp[0][3]=1	dp[0][4]=0	1	[0, 1, 1, 1, 1, -, -, -]
7	Item 1, w=5	1	5	1 + dp[0][4]=1	dp[0][5]=0	1	[0, 1, 1, 1, 1, 1, -, -]
8	Item 1, w=6	1	6	1 + dp[0][5]=1	dp[0][6]=0	1	[0, 1, 1, 1, 1, 1, 1, -]
9	Item 1, w=7	1	7	1 + dp[0][6]=1	dp[0][7]=0	1	[0, 1, 1, 1, 1, 1, 1, 1]
10	Item 2, w=0	2	0	-	dp[1][0]=0	0	[0, -, -, -, -, -, -, -]
11	Item 2, w=1	2	1	-	dp[1][1]=1	1	[0, 1, -, -, -, -, -, -]
12	Item 2, w=2	2	2	-	dp[1][2]=1	1	[0, 1, 1, -, -, -, -, -]
13	Item 2, w=3	2	3	4 + dp[1][0]=4	dp[1][3]=1	4	[0, 1, 1, 4, -, -, -, -]
14	Item 2, w=4	2	4	4 + dp[1][1]=5	dp[1][4]=1	5	[0, 1, 1, 4, 5, -, -, -]
15	Item 2, w=5	2	5	4 + dp[1][2]=5	dp[1][5]=1	5	[0, 1, 1, 4, 5, 5, -, -]
16	Item 2, w=6	2	6	4 + dp[1][3]=5	dp[1][6]=1	5	[0, 1, 1, 4, 5, 5, 5, -]
17	Item 2, w=7	2	7	4 + dp[1][4]=5	dp[1][7]=1	5	[0, 1, 1, 4, 5, 5, 5, 5]
18	Item 3, w=0	3	0	-	dp[2][0]=0	0	[0, -, -, -, -, -, -, -]
19	Item 3, w=1	3	1	-	dp[2][1]=1	1	[0, 1, -, -, -, -, -, -]
20	Item 3, w=2	3	2	-	dp[2][2]=1	1	[0, 1, 1, -, -, -, -, -]
21	Item 3, w=3	3	3	-	dp[2][3]=4	4	[0, 1, 1, 4, -, -, -, -]
22	Item 3, w=4	3	4	5 + dp[2][0]=5	dp[2][4]=5	5	[0, 1, 1, 4, 5, -, -, -]
23	Item 3, w=5	3	5	5 + dp[2][1]=6	dp[2][5]=5	6	[0, 1, 1, 4, 5, 6, -, -]
24	Item 3, w=6	3	6	5 + dp[2][2]=6	dp[2][6]=5	6	[0, 1, 1, 4, 5, 6, 6, -]
25	Item 3, w=7	3	7	5 + dp[2][3]=9	dp[2][7]=5	9	[0, 1, 1, 4, 5, 6, 6, 9]

💡 All items and weights processed; final max value is dp[3][7] = 9

Variable Tracker

Variable	Start	After Item 1	After Item 2	After Item 3 (Final)
dp[0]	[0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0]
dp[1]	[-,-,-,-,-,-,-,-]	[0,1,1,1,1,1,1,1]	[0,1,1,1,1,1,1,1]	[0,1,1,1,1,1,1,1]
dp[2]	[-,-,-,-,-,-,-,-]	[-,-,-,-,-,-,-,-]	[0,1,1,4,5,5,5,5]	[0,1,1,4,5,5,5,5]
dp[3]	[-,-,-,-,-,-,-,-]	[-,-,-,-,-,-,-,-]	[-,-,-,-,-,-,-,-]	[0,1,1,4,5,6,6,9]

Key Moments - 3 Insights

Why do we check if the item weight is less than or equal to current weight before including it?

Because we can only include the item if it fits in the current weight capacity. This is shown in execution_table rows where 'Include Value' is calculated only if weights[i-1] <= w.

Why do we take the max of including or excluding the item?

We want the best value possible. Including the item adds its value plus the best value for remaining weight, excluding keeps previous best. The chosen value column in execution_table shows this max choice.

Why does dp have one extra row and column?

Row 0 and column 0 represent no items or zero capacity, so dp[0][w] and dp[i][0] are zero. This base case is initialized in step 1 of execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 13, what is the chosen value for item 2 at weight 3?

A 1

B 4

C 5

D 0

💡 Hint

Check the 'Chosen Value' column at step 13 in execution_table.

At which step does the dp table first show a value greater than 5?

A Step 17

B Step 14

C Step 23

D Step 25

💡 Hint

Look at the 'Chosen Value' column and dp table states in execution_table rows for values > 5.

If the weight of item 3 was 5 instead of 4, how would the chosen value at weight 7 change at step 25?

A It would decrease

B It would remain 9

C It would increase

D It would be zero

💡 Hint

Consider if item 3 fits at weight 7 when weight is 5, and check how include value is computed in execution_table.

Concept Snapshot

0 1 Knapsack Problem:
- Use a 2D dp table: dp[i][w] = max value using first i items with capacity w
- For each item and weight, decide to include or exclude item
- Include only if item weight <= current capacity
- dp[i][w] = max(value[i-1] + dp[i-1][w-weight[i-1]], dp[i-1][w])
- Final answer at dp[n][W]

Full Transcript

The 0 1 Knapsack Problem uses a table to find the best value of items that fit in a knapsack of max weight W. We build a dp table where each cell dp[i][w] shows the max value using first i items with capacity w. For each item and weight, we check if the item fits. If yes, we consider including it (adding its value plus best value for remaining weight) or excluding it (keeping previous best). We pick the max of these two. The table starts with zeros for no items or zero capacity. After filling all rows and columns, the answer is in dp[n][W]. This step-by-step filling is shown in the execution table, tracking choices and dp states. Key points include checking item fit, choosing max value, and base cases. The final max value for the example is 9.

Practice

1. What does the 0 1 Knapsack Problem aim to maximize given a set of items with weights and values?

easy

A. The total value of items without exceeding the weight limit

B. The total weight of items regardless of value

C. The number of items selected

D. The minimum weight of items selected

Solution

1. Step 1: Understand the problem goal

   The 0 1 Knapsack Problem tries to select items to maximize total value without exceeding the weight capacity.

2. Step 2: Clarify constraints

   Each item can be chosen only once (0 or 1 times), so the goal is to maximize value under weight limit.

3. Final Answer:

   The total value of items without exceeding the weight limit -> Option A

4. Quick Check:

   Maximize value under weight limit = The total value of items without exceeding the weight limit [OK]

Hint: Focus on maximizing value, not weight or count [OK]

Common Mistakes:

• Confusing weight maximization with value maximization
• Thinking the problem counts items instead of values
• Ignoring the weight limit constraint

2. Which of the following is the correct Python syntax to initialize a 2D list dp of size (n+1) x (W+1) filled with zeros for the 0 1 Knapsack DP table?

easy

A. dp = [[0 for _ in range(W+1)] for _ in range(n+1)]

B. dp = [[0] * n for _ in range(W)]

C. dp = [0] * (n+1) * (W+1)

D. dp = [[0] * (W+1)] * (n+1)

Solution

1. Step 1: Understand 2D list initialization

   Using list comprehension with nested loops creates independent inner lists, avoiding shared references.

2. Step 2: Analyze each option

   dp = [[0 for _ in range(W+1)] for _ in range(n+1)] correctly uses nested list comprehension to create a (n+1) x (W+1) zero matrix.

3. Final Answer:

   dp = [[0 for _ in range(W+1)] for _ in range(n+1)] -> Option A

4. Quick Check:

   Nested list comprehension for 2D zero matrix = dp = [[0 for _ in range(W+1)] for _ in range(n+1)] [OK]

Hint: Use nested list comprehension for 2D lists [OK]

Common Mistakes:

• Using multiplication for inner lists causing shared references
• Creating 1D list instead of 2D
• Swapping dimensions incorrectly

3. What is the output of the following Python code snippet implementing 0 1 Knapsack DP for items with weights [1, 2, 3] and values [10, 20, 30] and capacity 5?

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

print(knapsack([1,2,3], [10,20,30], 5))

medium

A. 60

B. 40

C. 50

D. 30

Solution

1. Step 1: Trace DP table filling

   Items: (1,10), (2,20), (3,30), Capacity=5. Check combinations:
   - Take items 2 and 3: weight=5, value=50
   - Take items 1 and 3: weight=4, value=40
   - Take all items 1,2,3: weight=6 (exceeds capacity)
   - Take items 1 and 2: weight=3, value=30

2. Step 2: Find max value within capacity

   Best is items 2 and 3 with total value 50, but check if better:
   Actually, items 1,2,3 total weight 6 > 5, so not allowed.
   Items 1,2,3 can't all be taken.
   Check items 1,2,3 subsets:
   Items 2,3: 5 weight, 50 value
   Items 1,3: 4 weight, 40 value
   Items 1,2: 3 weight, 30 value
   So max value is 50.

3. Final Answer:

   50 -> Option C

4. Quick Check:

   Max value under weight 5 = 50 [OK]

Hint: Check all item subsets under capacity for max value [OK]

Common Mistakes:

• Assuming all items fit without checking weight
• Mixing up indices in DP table
• Forgetting to subtract weight when adding value

4. Find the error in this 0 1 Knapsack DP code snippet and select the fix:

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            if weights[i] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i]] + values[i])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

medium

A. Change range(1, W+1) to range(W)

B. Change dp[i-1][w] to dp[i][w]

C. Initialize dp with ones instead of zeros

D. Change weights[i] to weights[i-1] and values[i] to values[i-1]

Solution

1. Step 1: Identify index error in array access

   Python lists are zero-indexed, but loop uses i from 1 to n, so weights[i] and values[i] cause IndexError or wrong access.

2. Step 2: Correct indexing for weights and values

   Use weights[i-1] and values[i-1] to access correct item corresponding to dp row i.

3. Final Answer:

   Change weights[i] to weights[i-1] and values[i] to values[i-1] -> Option D

4. Quick Check:

   Fix indexing to avoid off-by-one errors = Change weights[i] to weights[i-1] and values[i] to values[i-1] [OK]

Hint: Use i-1 to index weights and values inside loops [OK]

Common Mistakes:

• Using i instead of i-1 for zero-based lists
• Changing dp indices incorrectly
• Altering loop ranges unnecessarily

5. Given items with weights [2, 3, 4, 5] and values [3, 4, 5, 6], and a knapsack capacity of 5, which items should be selected to maximize value? Also, what is the maximum value achievable?

hard

A. Select item with weight 5 only; max value 6

B. Select items with weights 2 and 3; max value 7

C. Select items with weights 3 and 4; max value 9

D. Select items with weights 2 and 4; max value 8

Solution

1. Step 1: List possible item combinations under capacity 5

   Check combinations:
   - Item 1 (2,3) + Item 2 (3,4): total weight 5, value 7
   - Item 3 (4,5) alone: weight 4, value 5
   - Item 4 (5,6) alone: weight 5, value 6
   - Item 2 (3,4) + Item 3 (4,5): weight 7 (exceeds capacity)
   - Item 1 (2,3) + Item 3 (4,5): weight 6 (exceeds capacity)

2. Step 2: Choose combination with max value

   Items 1 and 2 together fit exactly and give value 7, which is higher than any single item value under capacity.

3. Final Answer:

   Select items with weights 2 and 3; max value 7 -> Option B

4. Quick Check:

   Max value with capacity 5 = 7 by items 2 and 3 weights [OK]

Hint: Try all item pairs fitting capacity, pick max value [OK]

Common Mistakes:

• Choosing heavier single item over lighter combo
• Ignoring exact capacity limit
• Assuming max value is from single item