0 1 Knapsack Problem in DSA Rust - Build from Scratch

0 1 Knapsack Problem

📖 Scenario: You are packing a backpack for a hiking trip. You have a list of items, each with a weight and a value. Your backpack can only carry a limited weight. You want to choose items to maximize the total value without exceeding the weight limit.

🎯 Goal: Build a Rust program that solves the 0 1 Knapsack problem using dynamic programming. You will create the data for items, set the backpack capacity, implement the core logic to find the maximum value, and print the result.

📋 What You'll Learn

Create a vector of tuples called items where each tuple contains weight and value as usize.

Create a variable called capacity of type usize representing the maximum weight the backpack can carry.

Implement the 0 1 Knapsack dynamic programming logic using a 2D vector called dp.

Print the maximum value that can be carried in the backpack.

💡 Why This Matters

🌍 Real World

Packing efficiently for trips, resource allocation, budget management, and many optimization problems in logistics and finance use the 0 1 Knapsack approach.

💼 Career

Understanding dynamic programming and optimization problems like 0 1 Knapsack is essential for software engineers, data scientists, and algorithm developers working on resource management and decision-making systems.

1

Create the list of items

Create a vector called items with these exact tuples: (2, 3), (3, 4), (4, 5), (5, 8). Each tuple represents (weight, value) as usize.

DSA Rust

# Create the vector of items with weight and value tuples
# Your code here

Hint

Use let items: Vec<(usize, usize)> = vec![(2, 3), (3, 4), (4, 5), (5, 8)]; to create the vector.

2

Set the backpack capacity

Create a variable called capacity of type usize and set it to 8.

DSA Rust

fn main() {
    let items: Vec = vec![(2, 3), (3, 4), (4, 5), (5, 8)];
    // Set the backpack capacity
    // Your code here
}

Hint

Use let capacity: usize = 8; to set the capacity.

3

Implement the 0 1 Knapsack dynamic programming logic

Create a 2D vector called dp with dimensions items.len() + 1 by capacity + 1, initialized with zeros. Use nested for loops with variables i and w to fill dp using the 0 1 Knapsack logic. Use items[i - 1].0 for weight and items[i - 1].1 for value.

DSA Rust

fn main() {
    let items: Vec = vec![(2, 3), (3, 4), (4, 5), (5, 8)];
    let capacity: usize = 8;
    // Create dp vector and fill it with 0 1 Knapsack logic
    // Your code here
}

Hint

Use a 2D vector dp and nested loops over i and w. Update dp[i][w] with the max of not taking or taking the item.

4

Print the maximum value

Print the maximum value that can be carried in the backpack by printing dp[items.len()][capacity].

DSA Rust

fn main() {
    let items: Vec = vec![(2, 3), (3, 4), (4, 5), (5, 8)];
    let capacity: usize = 8;

    let n = items.len();
    let mut dp = vec![vec![0; capacity + 1]; n + 1];

    for i in 1..=n {
        let (weight, value) = items[i - 1];
        for w in 0..=capacity {
            if weight <= w {
                dp[i][w] = dp[i - 1][w].max(dp[i - 1][w - weight] + value);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    // Print the maximum value
    // Your code here
}

Hint

Use println!("{}", dp[n][capacity]); to print the maximum value.

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