0 1 Knapsack Problem in DSA C++ - Execution Trace

Concept Flow - 0 1 Knapsack Problem

Start with empty knapsack

↓

For each item i

↓

For each weight w from 0 to max capacity

↓

Check if item i fits (weight[i

Yes No↓

Include item i: value[i

↓

Take max of include/exclude

↓

Fill dp table

↓

Answer is dp[number_of_items

We fill a table where each cell shows the best value for items up to i and capacity w, choosing to include or exclude the current item.

Execution Sample

DSA C++

int knapsack(int W, int wt[], int val[], int n) {
  int dp[n+1][W+1];
  for (int i = 0; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
      if (i == 0 || w == 0) dp[i][w] = 0;
      else if (wt[i-1] <= w) dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w]);
      else dp[i][w] = dp[i-1][w];
    }
  }
  return dp[n][W];
}

This code fills a table to find the max value for given items and capacity, deciding to include or exclude each item.

Execution Table

Step	Operation	Item i	Weight w	Condition (wt[i-1] <= w)	Include Value	Exclude Value	dp[i][w]	DP Table Row State
1	Initialize dp row 0	0	0 to 7	N/A	N/A	N/A	0	[0,0,0,0,0,0,0,0]
2	Initialize dp column 0	1	0	N/A	N/A	N/A	0	[0,0,0,0,0,0,0,0]
3	Check item 1 (wt=1,val=1)	1	1	Yes	1 + dp[0][0]=1	dp[0][1]=0	1	[0,1,0,0,0,0,0,0]
4	Check item 1	1	2	Yes	1 + dp[0][1]=1	dp[0][2]=0	1	[0,1,1,0,0,0,0,0]
5	Check item 1	1	3	Yes	1 + dp[0][2]=1	dp[0][3]=0	1	[0,1,1,1,0,0,0,0]
6	Check item 1	1	4	Yes	1 + dp[0][3]=1	dp[0][4]=0	1	[0,1,1,1,1,0,0,0]
7	Check item 1	1	5	Yes	1 + dp[0][4]=1	dp[0][5]=0	1	[0,1,1,1,1,1,0,0]
8	Check item 1	1	6	Yes	1 + dp[0][5]=1	dp[0][6]=0	1	[0,1,1,1,1,1,1,0]
9	Check item 1	1	7	Yes	1 + dp[0][6]=1	dp[0][7]=0	1	[0,1,1,1,1,1,1,1]
10	Check item 2 (wt=3,val=4)	2	1	No	N/A	dp[1][1]=1	1	[0,1,1,1,1,1,1,1]
11	Check item 2	2	2	No	N/A	dp[1][2]=1	1	[0,1,1,1,1,1,1,1]
12	Check item 2	2	3	Yes	4 + dp[1][0]=4	dp[1][3]=1	4	[0,1,1,4,1,1,1,1]
13	Check item 2	2	4	Yes	4 + dp[1][1]=5	dp[1][4]=1	5	[0,1,1,4,5,1,1,1]
14	Check item 2	2	5	Yes	4 + dp[1][2]=5	dp[1][5]=1	5	[0,1,1,4,5,5,1,1]
15	Check item 2	2	6	Yes	4 + dp[1][3]=5	dp[1][6]=1	5	[0,1,1,4,5,5,5,1]
16	Check item 2	2	7	Yes	4 + dp[1][4]=5	dp[1][7]=1	5	[0,1,1,4,5,5,5,5]
17	Check item 3 (wt=4,val=5)	3	1	No	N/A	dp[2][1]=1	1	[0,1,1,4,5,5,5,5]
18	Check item 3	3	2	No	N/A	dp[2][2]=1	1	[0,1,1,4,5,5,5,5]
19	Check item 3	3	3	No	N/A	dp[2][3]=4	4	[0,1,1,4,5,5,5,5]
20	Check item 3	3	4	Yes	5 + dp[2][0]=5	dp[2][4]=5	5	[0,1,1,4,5,5,5,5]
21	Check item 3	3	5	Yes	5 + dp[2][1]=6	dp[2][5]=5	6	[0,1,1,4,5,6,5,5]
22	Check item 3	3	6	Yes	5 + dp[2][2]=6	dp[2][6]=5	6	[0,1,1,4,5,6,6,5]
23	Check item 3	3	7	Yes	5 + dp[2][3]=9	dp[2][7]=5	9	[0,1,1,4,5,6,6,9]

💡 All items and weights processed; dp[n][W] = 9 is the max value.

Variable Tracker

Variable	Start	After Step 3	After Step 12	After Step 23	Final
i (item index)	0	1	2	3	3
w (weight capacity)	0	1	3	7	7
dp row 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]	[0,0,0,0,0,0,0,0]
dp row 1	[0,0,0,0,0,0,0,0]	[0,1,1,1,1,1,1,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 row 2	[0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0]	[0,1,1,4,5,5,5,5]	[0,1,1,4,5,5,5,5]	[0,1,1,4,5,5,5,5]
dp row 3	[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,1,1,4,5,6,6,9]	[0,1,1,4,5,6,6,9]

Key Moments - 3 Insights

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

Because if the item is heavier than the current capacity (w), we cannot include it. This is shown in the execution_table rows where condition is 'No' and dp[i][w] equals dp[i-1][w], meaning we skip the item.

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

We want the best value possible. Including the item adds its value plus the best value for the remaining capacity. Excluding keeps the previous best. The dp[i][w] cell stores the max of these two, as seen in the execution_table where dp[i][w] is max(include, exclude).

Why do we initialize the first row and column of the dp table with zeros?

The first row (i=0) means no items, so value is zero. The first column (w=0) means zero capacity, so no items can be included. This base case is shown in steps 1 and 2 where dp[i][0] and dp[0][w] are set to 0.

Visual Quiz - 3 Questions

Look at the execution_table at step 12, what is the value of dp[2][3]?

A 4

B 1

C 5

D 0

💡 Hint

Refer to the 'dp[i][w]' column in execution_table row with Step 12.

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

A Step 14

B Step 21

C Step 16

D Step 23

💡 Hint

Check the 'dp[i][w]' column for values > 5 in execution_table rows.

If the weight of item 2 was 4 instead of 3, how would step 12 change?

A No change, dp[2][3] remains 4

B Condition would be Yes and dp[2][3] would increase

C Condition would be No and dp[2][3] would equal dp[1][3]

D dp[2][3] would be zero

💡 Hint

Look at the condition column and how weight affects inclusion in execution_table step 12.

Concept Snapshot

0 1 Knapsack Problem:
- Use a 2D dp table dp[n+1][W+1]
- dp[i][w] = max value using first i items with capacity w
- If item i fits (wt[i-1] <= w), choose max(include, exclude)
- Else exclude item
- Answer at dp[n][W]

Full Transcript

The 0 1 Knapsack Problem uses a table to find the best value of items fitting in a knapsack of capacity W. We build a dp table where each cell dp[i][w] shows the max value using first i items and capacity w. For each item and capacity, we check if the item fits. If yes, we decide to include it or not by comparing values. If no, we skip it. The first row and column are zeros because no items or zero capacity means zero value. The final answer is dp[n][W].

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 weight of items without exceeding the value limit

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

C. The number of items selected regardless of weight

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: Identify the constraint

   The total weight of selected items must not exceed the given weight limit.

3. Final Answer:

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

4. Quick Check:

   Maximize value with weight limit = A [OK]

Hint: Maximize value, keep total weight ≤ capacity [OK]

Common Mistakes:

• Confusing weight limit with value limit
• Trying to maximize weight instead of value
• Ignoring the weight constraint

2. Which of the following is the correct way to declare the DP table for the 0 1 Knapsack Problem in C++ if n is number of items and W is max weight?

easy

A. int dp[n+1][W+1];

B. int dp[W+1][n+1];

C. int dp[n][W];

D. int dp[W][n];

Solution

1. Step 1: Understand DP table dimensions

   The DP table stores solutions for items 0 to n and weights 0 to W, so size is (n+1) x (W+1).

2. Step 2: Match correct declaration

   int dp[n+1][W+1]; declares dp with dimensions [n+1][W+1], matching the problem requirements.

3. Final Answer:

   int dp[n+1][W+1]; -> Option A

4. Quick Check:

   DP table size = (n+1) x (W+1) [OK]

Hint: DP table size = items+1 by weight+1 [OK]

Common Mistakes:

• Using dp[n][W] misses base case row/column
• Swapping dimensions incorrectly
• Declaring smaller arrays causing out-of-bound errors

3. What is the output of the following C++ code snippet for 0 1 Knapsack Problem?

int values[] = {60, 100, 120};
int weights[] = {10, 20, 30};
int W = 50;
int n = 3;

int dp[4][51] = {0};

for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= W; w++) {
        if (weights[i-1] <= w) {
            dp[i][w] = std::max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
        } else {
            dp[i][w] = dp[i-1][w];
        }
    }
}

std::cout << dp[n][W] << std::endl;

medium

A. 160

B. 180

C. 220

D. 250

Solution

1. Step 1: Understand the DP logic

   The code fills dp table to find max value for weight limit 50 with items of given weights and values.

2. Step 2: Calculate max value manually

   Items: (10,60), (20,100), (30,120). Max value for weight 50 is choosing items 2 and 3: 100 + 120 = 220.

3. Final Answer:

   220 -> Option C

4. Quick Check:

   Max value for W=50 = 220 [OK]

Hint: Pick items with max value under weight limit [OK]

Common Mistakes:

• Adding weights instead of values
• Choosing items exceeding weight limit
• Misindexing arrays causing wrong dp values

4. Identify the bug in this 0 1 Knapsack DP code snippet:

for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= W; w++) {
        if (weights[i] <= w) {
            dp[i][w] = std::max(dp[i-1][w], dp[i-1][w - weights[i]] + values[i]);
        } else {
            dp[i][w] = dp[i-1][w];
        }
    }
}

medium

A. Indexing weights and values with i instead of i-1

B. Loop ranges should start from 0 instead of 1

C. Using std::max instead of a custom max function

D. Not initializing dp array to zero

Solution

1. Step 1: Check array indexing

   Arrays weights and values are zero-indexed, but code uses i which starts at 1, causing out-of-bound or wrong access.

2. Step 2: Correct indexing

   Use weights[i-1] and values[i-1] to access correct elements.

3. Final Answer:

   Indexing weights and values with i instead of i-1 -> Option A

4. Quick Check:

   Zero-based arrays need i-1 index [OK]

Hint: Use i-1 for zero-based arrays in loops starting at 1 [OK]

Common Mistakes:

• Accessing arrays with wrong index causing runtime errors
• Starting loops at 0 but using i-1 indexing
• Ignoring dp initialization

5. Given items with values {20, 5, 10, 40, 15, 25} and weights {1, 2, 3, 8, 7, 4}, and max weight 10, what is the maximum value achievable using 0 1 Knapsack?

hard

A. 75

B. 65

C. 70

D. 60

Solution

1. Step 1: Analyze items and weight limit

   Items: values = {20,5,10,40,15,25}, weights = {1,2,3,8,7,4}, max weight = 10.

2. Step 2: Find best combination under weight 10

   Choose items with weights 1,3,4 (values 20,10,25) total weight 8, value 55; or items 1,2,6 (weights 1,2,4) value 20+5+25=50; best is items 1,4 (weights 1+8=9) value 20+40=60; or items 4 and 6 (8+4=12 >10) invalid; items 1,5,6 (1+7+4=12 >10) invalid; items 1,3,5 (1+3+7=11 >10) invalid; items 2,3,6 (2+3+4=9) value 5+10+25=40; items 1,2,3,6 (1+2+3+4=10) value 20+5+10+25=60; items 1,2,3,5 (1+2+3+7=13 >10) invalid; items 1,2,3,4 (1+2+3+8=14 >10) invalid; items 1,2,6,5 (1+2+4+7=14 >10) invalid; items 1,3,6 (1+3+4=8) value 20+10+25=55; items 1,2,3,6 total value 60 and weight 10 fits exactly.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   Max value with weight 10 = 60 [OK]

Hint: Try combinations fitting weight limit, sum max values [OK]

Common Mistakes:

• Ignoring weight limit when summing values
• Missing best combination with multiple items
• Assuming greedy choice works always