0 1 Knapsack Problem in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the '0 1' in the 0 1 Knapsack Problem mean?

It means each item can either be taken completely (1) or not taken at all (0). You cannot take fractional parts of an item.

beginner

What is the main goal of the 0 1 Knapsack Problem?

To maximize the total value of items put in the knapsack without exceeding its weight capacity.

intermediate

In the dynamic programming solution of 0 1 Knapsack, what does the DP table represent?

Each cell dp[i][w] represents the maximum value achievable using the first i items with a weight limit w.

intermediate

Why can't greedy algorithms solve the 0 1 Knapsack Problem optimally?

Because choosing items based only on value or weight ratio can miss combinations that yield higher total value within the weight limit.

intermediate

What is the time complexity of the classic dynamic programming solution for the 0 1 Knapsack Problem?

O(n * W), where n is the number of items and W is the maximum weight capacity of the knapsack.

In the 0 1 Knapsack Problem, what does the '1' represent?

A Taking half the item

B Taking the whole item

C Not taking the item

D Taking fractional parts

The '1' means you either take the whole item or none at all.

What does dp[i][w] represent in the DP table for 0 1 Knapsack?

A Total weight of first i items

B Minimum weight to achieve value w using i items

C Number of items used to reach weight w

D Maximum value using first i items with weight limit w

dp[i][w] stores the best value achievable with first i items and weight limit w.

Which approach is best to solve the 0 1 Knapsack Problem optimally?

A Greedy algorithm

B Divide and conquer

C Dynamic programming

D Brute force only

Dynamic programming efficiently finds the optimal solution by building up from smaller subproblems.

What is the main constraint in the 0 1 Knapsack Problem?

A Maximum total weight

B Maximum total value

C Minimum total weight

D Maximum number of items

The total weight of chosen items must not exceed the knapsack's capacity.

If you have 5 items and a knapsack capacity of 10, what is the time complexity of the DP solution?

A O(5 * 10)

B O(5 + 10)

C O(5^10)

D O(10^5)

The DP solution runs in O(n * W), here 5 * 10 = 50.

Explain how the dynamic programming table is built for the 0 1 Knapsack Problem.

Think about how you decide to take or skip each item step by step.

Describe why greedy methods fail for the 0 1 Knapsack Problem but work for fractional knapsack.

Consider the difference between taking whole items vs parts.

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