0 1 Knapsack Problem in DSA Rust

Mental Model

Choose items to maximize value without exceeding weight limit, picking each item only once.

Analogy: Packing a backpack for a hike: you want the most useful things but can only carry so much weight, and you can't take half an item.

Knapsack capacity: 5
Items:
[Weight: 2, Value: 3]
[Weight: 3, Value: 4]
[Weight: 4, Value: 5]

Backpack (capacity 5) -> Choose items fully or not at all

Dry Run Walkthrough

Input: items: [(weight=2, value=3), (weight=3, value=4), (weight=4, value=5)], capacity=5

Goal: Find the maximum total value of items that fit in the knapsack without exceeding capacity 5

Step 1: Start with no items, capacity 0 to 5, all values 0

DP table row 0 (no items): [0, 0, 0, 0, 0, 0]

Why: Base case: no items means no value

Step 2: Consider item 1 (weight 2, value 3), update DP for capacities 0 to 5

DP row 1: [0, 0, 3, 3, 3, 3]

Why: For capacity >= 2, can take item 1 for value 3

Step 3: Consider item 2 (weight 3, value 4), update DP for capacities 0 to 5

DP row 2: [0, 0, 3, 4, 4, 7]

Why: At capacity 5, taking items 1 and 2 gives value 7

Step 4: Consider item 3 (weight 4, value 5), update DP for capacities 0 to 5

DP row 3: [0, 0, 3, 4, 5, 7]

Why: At capacity 5, best value remains 7 by skipping item 3

Result:

Maximum value = 7
DP final row: [0, 0, 3, 4, 5, 7]

Annotated Code

DSA Rust

struct Item {
    weight: usize,
    value: usize,
}

fn knapsack_01(items: &[Item], capacity: usize) -> usize {
    let n = items.len();
    let mut dp = vec![vec![0; capacity + 1]; n + 1];

    for i in 1..=n {
        let item = &items[i - 1];
        for w in 0..=capacity {
            if item.weight <= w {
                dp[i][w] = dp[i - 1][w].max(dp[i - 1][w - item.weight] + item.value);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    dp[n][capacity]
}

fn main() {
    let items = vec![
        Item { weight: 2, value: 3 },
        Item { weight: 3, value: 4 },
        Item { weight: 4, value: 5 },
    ];
    let capacity = 5;
    let max_value = knapsack_01(&items, capacity);
    println!("Maximum value = {}", max_value);
}

for i in 1..=n {

iterate over items to build DP table row by row

for w in 0..=capacity {

iterate over all capacities from 0 to max capacity

if item.weight <= w {

check if current item fits in current capacity

dp[i][w] = dp[i - 1][w].max(dp[i - 1][w - item.weight] + item.value);

choose max between skipping or taking the item

else { dp[i][w] = dp[i - 1][w]; }

cannot take item, so keep previous max value

Output

Maximum value = 7

Complexity Analysis

Time: O(n * capacity) because we fill a table with n items and capacity columns

Space: O(n * capacity) for the DP table storing max values for each item and capacity

vs Alternative: Naive approach tries all subsets with exponential time O(2^n), DP reduces it to polynomial time

Edge Cases

empty items list

returns 0 because no items to pick

DSA Rust

for i in 1..=n {

capacity zero

returns 0 because knapsack can't hold anything

DSA Rust

for w in 0..=capacity {

items heavier than capacity

items are skipped, result is 0 or max of lighter items

DSA Rust

if item.weight <= w {

When to Use This Pattern

When you need to pick items with weights and values to maximize value without splitting items, use 0 1 Knapsack DP pattern.

Common Mistakes

Mistake: Allowing fractional items instead of whole items
Fix: Ensure to only pick whole items by checking weight fits and not splitting

Mistake: Not initializing DP table correctly causing index errors
Fix: Initialize DP table with size (n+1) x (capacity+1) and base case zeros

Summary

Find max value of items fitting in knapsack without exceeding capacity, picking each item once.

Use when you must choose whole items to maximize value under weight limit.

The key is building a table of best values for each item count and capacity step.

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