0 1 Knapsack Problem in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of 0 1 Knapsack DP Table Calculation

What is the maximum value that can be carried in the knapsack with capacity 50 using the given weights and values?

DSA Rust

fn knapsack(values: &[i32], weights: &[i32], capacity: usize) -> i32 {
    let n = values.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] as usize <= w {
                dp[i][w] = dp[i - 1][w].max(dp[i - 1][w - weights[i - 1] as usize] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    dp[n][capacity]
}

fn main() {
    let values = [60, 100, 120];
    let weights = [10, 20, 30];
    let capacity = 50;
    println!("{}", knapsack(&values, &weights, capacity));
}

A 220

B 180

C 160

D 200

💡 Hint

Think about which items fit within the capacity and maximize value.

The knapsack can hold items with weights 20 and 30 for a total value of 100 + 120 = 220, which is the maximum possible.

❓ Predict Output

intermediate

Value of dp Table Cell in 0 1 Knapsack

What is the value of dp[2][20] after processing the first two items in the knapsack problem with values [60, 100] and weights [10, 20] and capacity 50?

DSA Rust

fn knapsack_dp_cell() -> i32 {
    let values = [60, 100];
    let weights = [10, 20];
    let capacity = 50;
    let n = values.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] as usize <= w {
                dp[i][w] = dp[i - 1][w].max(dp[i - 1][w - weights[i - 1] as usize] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    dp[2][20]
}

fn main() {
    println!("{}", knapsack_dp_cell());
}

A 160

B 0

C 60

D 100

💡 Hint

Check if the second item fits exactly in capacity 20.

At capacity 20, the second item (weight 20, value 100) fits exactly, so dp[2][20] = max(dp[1][20], dp[1][0] + 100) = max(60, 100) = 100.

🔧 Debug

advanced

Identify the error in this 0 1 Knapsack implementation

What error will this Rust code produce when run?

DSA Rust

fn knapsack(values: &[i32], weights: &[i32], capacity: usize) -> i32 {
    let n = values.len();
    let mut dp = vec![vec![0; capacity]; n + 1];
    for i in 1..=n {
        for w in 0..capacity {
            if weights[i - 1] as usize <= w {
                dp[i][w] = dp[i - 1][w].max(dp[i - 1][w - weights[i - 1] as usize] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    dp[n][capacity]
}

fn main() {
    let values = [60, 100, 120];
    let weights = [10, 20, 30];
    let capacity = 50;
    println!("{}", knapsack(&values, &weights, capacity));
}

A Infinite loop

B Compilation error due to type mismatch

C Index out of bounds panic at dp[i][capacity]

D No error, outputs 220

💡 Hint

Check the range of the inner loop for w.

The inner loop runs w from 0 to capacity-1, so dp[i][capacity] is never assigned and accessing dp[n][capacity] causes an index out of bounds panic.

🧠 Conceptual

advanced

Time Complexity of 0 1 Knapsack DP Solution

What is the time complexity of the dynamic programming solution for the 0 1 Knapsack problem with n items and capacity W?

A O(n + W)

B O(n * W)

C O(n^2 * W)

D O(2^n)

💡 Hint

Consider the nested loops over items and capacity.

The DP solution uses a table of size n by W and fills each cell once, so time complexity is O(n * W).

🚀 Application

expert

Maximum Value and Items Selected in 0 1 Knapsack

Given values [20, 5, 10, 40, 15, 25], weights [1, 2, 3, 8, 7, 4], and capacity 10, which set of items gives the maximum value without exceeding capacity?

A [20, 5, 25]

B [20, 10, 15, 25]

C [5, 10, 40]

D [20, 40, 25]

💡 Hint

Sum weights and values of each option and check capacity limit.

Option A items have weights 1 + 2 + 4 = 7 <= 10 and values 20 + 5 + 25 = 50, which is the maximum value achievable within capacity.

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