0 1 Knapsack Problem in DSA Rust - Execution Trace

Concept Flow - 0 1 Knapsack Problem

Start with empty knapsack

↓

For each item i

↓

For each capacity 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 capacities

↓

Final answer in dp[n

We build a table where each cell dp[i][w] stores the best value using first i items and capacity w, choosing to include or exclude each item.

Execution Sample

DSA Rust

weights = [1, 3, 4]
values = [1, 4, 5]
capacity = 7
# Initialize dp array with zeros
let mut dp = vec![vec![0; capacity + 1]; weights.len() + 1];
for i in 1..=weights.len() {
  for w in 0..=capacity {
    if weights[i-1] <= w {
      dp[i][w] = std::cmp::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 row by row, deciding for each item and capacity whether to include or exclude the item to maximize value.

Execution Table

Step	Operation	Item i	Capacity w	Include Value	Exclude Value	dp[i][w]	Table State (dp rows)
1	Initialize dp row 0	0	0-7	-	-	[0,0,0,0,0,0,0,0]	[[0,0,0,0,0,0,0,0]]
2	Process item 1	1	0	-	dp[0][0]=0	0	[[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0]]
3	Process item 1	1	1	value=1+dp[0][0]=1	dp[0][1]=0	1	[[0,0,0,0,0,0,0,0],[0,1,0,0,0,0,0,0]]
4	Process item 1	1	2	1+dp[0][1]=1	dp[0][2]=0	1	[[0,0,0,0,0,0,0,0],[0,1,1,0,0,0,0,0]]
5	Process item 1	1	3	1+dp[0][2]=1	dp[0][3]=0	1	[[0,0,0,0,0,0,0,0],[0,1,1,1,0,0,0,0]]
6	Process item 1	1	4	1+dp[0][3]=1	dp[0][4]=0	1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,0,0,0]]
7	Process item 1	1	5	1+dp[0][4]=1	dp[0][5]=0	1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,0,0]]
8	Process item 1	1	6	1+dp[0][5]=1	dp[0][6]=0	1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,0]]
9	Process item 1	1	7	1+dp[0][6]=1	dp[0][7]=0	1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1]]
10	Process item 2	2	0	-	dp[1][0]=0	0	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0]]
11	Process item 2	2	1	weight=3>1 no include	dp[1][1]=1	1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,0,0,0,0,0,0]]
12	Process item 2	2	2	weight=3>2 no include	dp[1][2]=1	1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,0,0,0,0,0]]
13	Process item 2	2	3	include=4+dp[1][0]=4	exclude=dp[1][3]=1	4	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,0,0,0,0]]
14	Process item 2	2	4	include=4+dp[1][1]=5	exclude=dp[1][4]=1	5	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,0,0,0]]
15	Process item 2	2	5	include=4+dp[1][2]=5	exclude=dp[1][5]=1	5	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,0,0]]
16	Process item 2	2	6	include=4+dp[1][3]=5	exclude=dp[1][6]=1	5	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,5,0]]
17	Process item 2	2	7	include=4+dp[1][4]=5	exclude=dp[1][7]=1	5	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,5,5]]
18	Process item 3	3	0	-	dp[2][0]=0	0	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,5,5],[0,0,0,0,0,0,0,0]]
19	Process item 3	3	1	weight=4>1 no include	dp[2][1]=1	1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,5,5],[0,1,0,0,0,0,0,0]]
20	Process item 3	3	2	weight=4>2 no include	dp[2][2]=1	1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,5,5],[0,1,1,0,0,0,0,0]]
21	Process item 3	3	3	weight=4>3 no include	dp[2][3]=4	4	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,5,5],[0,1,1,4,0,0,0,0]]
22	Process item 3	3	4	include=5+dp[2][0]=5	exclude=dp[2][4]=5	5	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,5,5],[0,1,1,4,5,0,0,0]]
23	Process item 3	3	5	include=5+dp[2][1]=6	exclude=dp[2][5]=5	6	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,5,5],[0,1,1,4,5,6,0,0]]
24	Process item 3	3	6	include=5+dp[2][2]=6	exclude=dp[2][6]=5	6	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,5,5],[0,1,1,4,5,6,6,0]]
25	Process item 3	3	7	include=5+dp[2][3]=9	exclude=dp[2][7]=5	9	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,5,5],[0,1,1,4,5,6,6,9]]

💡 All items processed for all capacities; final answer is dp[3][7] = 9

Variable Tracker

Variable	Start	After Step 9	After Step 17	After Step 25 (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]	N/A	[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]	N/A	[0,0,0,0,0,0,0,0]	[0,1,1,4,5,5,5,5]	[0,1,1,4,5,5,5,5]
dp[3]	N/A	N/A	[0,0,0,0,0,0,0,0]	[0,1,1,4,5,6,6,9]
Final Answer	N/A	N/A	N/A	9

Key Moments - 3 Insights

Why do we compare including and excluding the item?

Because at each capacity, we want the best value. Including the item adds its value plus the best for remaining capacity; excluding keeps previous best. See execution_table rows 13 and 14 where both are compared.

Why do we start dp with zeros for zero items or zero capacity?

Because with no items or zero capacity, max value is zero. This base case is shown in execution_table row 1 where dp[0] is all zeros.

Why does the capacity loop go from 0 to max capacity?

To fill dp for all capacities, so we know best value for any capacity up to max. This is shown in execution_table steps 2-9 for item 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 13, what is the include value for item 2 at capacity 3?

A 4

B 1

C 5

D 0

💡 Hint

Check the 'Include Value' column at step 13 in execution_table

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

A Step 14

B Step 23

C Step 25

D Step 17

💡 Hint

Look at 'dp[i][w]' column values in execution_table rows after step 14

If the weight of item 3 was 2 instead of 4, how would dp[3][3] change at step 21?

A It would remain 4

B It would become 6

C It would become 5

D It would become 9

💡 Hint

Consider that item 3 can now fit in capacity 3, so include value = value[3] + dp[2][3-weight[3]]

Concept Snapshot

0 1 Knapsack Problem:
- Use dp table dp[i][w] for max value with first i items and capacity w
- For each item and capacity, choose max(include item, exclude item)
- Include: value[i-1] + dp[i-1][w - weight[i-1]] if fits
- Exclude: dp[i-1][w]
- Final answer at dp[n][capacity]

Full Transcript

The 0 1 Knapsack Problem uses a table dp where dp[i][w] stores the best value using the first i items with capacity w. We fill this table by checking for each item if it fits in the current capacity. If it fits, we compare including it (adding its value plus the best for remaining capacity) or excluding it (keeping previous best). We start with zero values for zero items or zero capacity. After processing all items and capacities, the answer is in dp[n][capacity]. The execution table shows step-by-step how dp is filled, and the variable tracker shows dp rows after key steps. Key moments clarify why we compare include/exclude, why base cases are zero, and why we loop over all capacities. The visual quiz tests understanding of these steps and changes.

Practice

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

easy

A. The number of items selected

B. The total weight of items regardless of value

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

D. The minimum weight of selected items

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 C

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
• Selecting items multiple times
• Ignoring the weight limit

2. Which of the following Rust code snippets correctly declares a 2D vector for dynamic programming table in 0 1 Knapsack?

easy

A. let mut dp = vec![vec![0; capacity + 1]; n + 1];

B. let dp = vec![0; capacity + 1];

C. let mut dp = [0; n + 1][capacity + 1];

D. let dp = vec![vec![0; n + 1]; capacity + 1];

Solution

1. Step 1: Identify correct 2D vector initialization

   In Rust, a 2D vector is created with vec![vec![initial_value; inner_size]; outer_size].

2. Step 2: Match dimensions for DP table

   DP table size is (n+1) rows and (capacity+1) columns, so vec![vec![0; capacity + 1]; n + 1] is correct.

3. Final Answer:

   let mut dp = vec![vec![0; capacity + 1]; n + 1]; -> Option A

4. Quick Check:

   2D vector with correct sizes = let mut dp = vec![vec![0; capacity + 1]; n + 1]; [OK]

Hint: Use vec![vec![0; cols]; rows] for 2D vectors [OK]

Common Mistakes:

• Using fixed-size arrays incorrectly
• Swapping rows and columns sizes
• Not making vector mutable when updating

3. What is the output of this Rust code snippet for 0 1 Knapsack with weights = [1, 3], values = [10, 20], capacity = 3?

let weights = vec![1, 3];
let values = vec![10, 20];
let capacity = 3;
let n = weights.len();
let mut dp = vec![vec![0; capacity + 1]; n + 1];
for i in 1..=n {
    for w in 0..=capacity {
        if weights[i - 1] <= w {
            dp[i][w] = dp[i - 1][w].max(dp[i - 1][w - weights[i - 1]] + values[i - 1]);
        } else {
            dp[i][w] = dp[i - 1][w];
        }
    }
}
println!("{}", dp[n][capacity]);

medium

A. 30

B. 20

C. 10

D. 0

Solution

1. Step 1: Trace DP table filling for each item and capacity

   For i=1 (weight=1, value=10): dp[1][1..3] = 10. For i=2 (weight=3, value=20): dp[2][3] = max(dp[1][3], dp[1][0]+20) = max(10, 20) = 20; dp[2][1..2] = dp[1][1..2] = 10.

2. Step 2: Check final dp[n][capacity]

   At capacity=3, dp[2][3] = max(10, 20) = 20, but also consider if both items fit: weight sum=4 > 3, so only one item can be chosen. The best is item 2 with value 20 or item 1 with value 10. But wait, item 1 weight=1 and item 2 weight=3, capacity=3, so only one item fits. The max value is 20.

3. Final Answer:

   20 -> Option B

4. Quick Check:

   Max value with capacity 3 = 20 [OK]

Hint: Check if items fit capacity, pick max value [OK]

Common Mistakes:

• Assuming both items fit when total weight exceeds capacity
• Mixing up indices in dp table
• Ignoring max function in dp update

4. Identify the bug in this Rust code snippet for 0 1 Knapsack and select the fix:

let weights = vec![2, 3];
let values = vec![40, 50];
let capacity = 5;
let n = weights.len();
let mut dp = vec![vec![0; capacity + 1]; n + 1];
for i in 1..=n {
    for w in 1..=capacity {
        if weights[i] <= w {
            dp[i][w] = dp[i - 1][w].max(dp[i - 1][w - weights[i]] + values[i]);
        } else {
            dp[i][w] = dp[i - 1][w];
        }
    }
}
println!("{}", dp[n][capacity]);

medium

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

B. Change loop to for i in 0..n

C. Initialize dp with zeros using dp = vec![0; n + 1]

D. Change capacity to capacity - 1 in inner loop

Solution

1. Step 1: Identify index out of bounds error

   Rust vectors are zero-indexed, but code uses weights[i] and values[i] where i starts from 1, causing out-of-bounds access.

2. Step 2: Fix indexing to zero-based

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

3. Final Answer:

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

4. Quick Check:

   Correct zero-based indexing fixes error [OK]

Hint: Use i-1 for zero-based vector indexing [OK]

Common Mistakes:

• Using 1-based indexing on zero-based vectors
• Incorrect loop ranges causing panic
• Wrong dp initialization size

5. Given items with weights = [2, 3, 4, 5], values = [3, 4, 5, 6], and capacity = 5, what is the maximum value achievable using 0 1 Knapsack?

hard

A. 6

B. 9

C. 10

D. 7

Solution

1. Step 1: Evaluate possible item combinations within capacity

   Check items that fit in capacity 5: - Item 1 (weight 2, value 3) - Item 2 (weight 3, value 4) - Item 3 (weight 4, value 5) - Item 4 (weight 5, value 6) Possible pairs: - Items 1+2: weight 5, value 7 - Items 1+3: weight 6 (too heavy) - Items 2+3: weight 7 (too heavy) - Item 4 alone: weight 5, value 6

2. Step 2: Choose combination with highest value under capacity

   Best is items 1 and 2 with total value 7 and weight exactly 5.

3. Final Answer:

   7 -> Option D

4. Quick Check:

   Max value with capacity 5 = 7 [OK]

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

Common Mistakes:

• Choosing single highest value item ignoring weight
• Adding items exceeding capacity
• Forgetting to check pairs or subsets