Unbounded Knapsack Problem in DSA Rust - Time & Space Complexity

Time Complexity: Unbounded Knapsack Problem

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to solve the Unbounded Knapsack Problem grows as the input size increases.

Specifically, how the number of items and the knapsack capacity affect the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds the maximum value achievable with unlimited items and a given knapsack capacity.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops: outer loop over capacities, inner loop over items.
• How many times: Outer loop runs (capacity + 1) times, inner loop runs for each item each time.

How Execution Grows With Input

As capacity grows, the outer loop runs more times. For each capacity, we check all items.

Input Size (capacity n)	Approx. Operations (n * number_of_items)
10	10 * items
100	100 * items
1000	1000 * items

Pattern observation: The work grows linearly with capacity and linearly with the number of items.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the product of capacity (n) and number of items (m).

Common Mistake

[X] Wrong: "The time complexity is just O(n) because we only loop over capacity once."

[OK] Correct: Because for each capacity, we check all items, so the inner loop multiplies the work by the number of items.

Interview Connect

Understanding this complexity helps you explain how dynamic programming solves problems efficiently by breaking them into smaller parts.

Self-Check

"What if we sorted items by weight and stopped inner loop early? How would the time complexity change?"

Practice

1. What is the main difference between the Unbounded Knapsack Problem and the 0/1 Knapsack Problem?

easy

A. There is no difference; both problems are the same.

B. In Unbounded Knapsack, items cannot be repeated.

C. In 0/1 Knapsack, items can be used unlimited times.

D. In Unbounded Knapsack, you can use unlimited copies of each item.

Solution

1. Step 1: Understand item usage rules

   In 0/1 Knapsack, each item can be chosen at most once. In Unbounded Knapsack, items can be chosen multiple times.

2. Step 2: Compare problem definitions

   Unbounded Knapsack allows unlimited copies of each item, unlike 0/1 Knapsack.

3. Final Answer:

   In Unbounded Knapsack, you can use unlimited copies of each item. -> Option D

4. Quick Check:

   Unbounded = unlimited copies [OK]

Hint: Unbounded means unlimited items allowed [OK]

Common Mistakes:

• Confusing 0/1 and unbounded item usage
• Thinking items cannot repeat in unbounded knapsack
• Assuming both problems have same constraints

2. Which of the following Rust code snippets correctly initializes the DP array for the Unbounded Knapsack problem with capacity `W`?

easy

A. let mut dp = vec![std::i32::MAX; W + 1];

B. let mut dp = vec![1; W];

C. let mut dp = vec![0; W + 1];

D. let mut dp = vec![None; W + 1];

Solution

1. Step 1: Understand DP array purpose

   DP array stores max value for capacities from 0 to W, initialized with 0 as base case.

2. Step 2: Check initialization correctness

   let mut dp = vec![0; W + 1]; initializes dp with zeros for all capacities including 0 to W, which is correct.

3. Final Answer:

   let mut dp = vec![0; W + 1]; -> Option C

4. Quick Check:

   DP array zero-initialized for capacities [OK]

Hint: DP array size = capacity + 1, initialize with zeros [OK]

Common Mistakes:

• Using MAX instead of 0 for initialization
• Wrong vector size (W instead of W+1)
• Using None instead of integer values

3. What will be the output of the following Rust code snippet for Unbounded Knapsack?

let weights = vec![2, 3, 4];
let values = vec![15, 20, 30];
let capacity = 7;
let mut dp = vec![0; capacity + 1];

for w in 1..=capacity {
    for i in 0..weights.len() {
        if weights[i] <= w {
            dp[w] = dp[w].max(dp[w - weights[i]] + values[i]);
        }
    }
}
println!("{}", dp[capacity]);

medium

A. 65

B. 50

C. 45

D. 60

Solution

1. Step 1: Trace DP array updates for capacity 7

   Calculate max value for each capacity: - w=1: no items fit, dp[1]=0 - w=2: use item 0 (weight 2, value 15), dp[2]=15 - w=3: item 1 fits (3,20), dp[3]=20 - w=4: item 2 fits (4,30), dp[4]=30; also dp[4-2]=dp[2]=15 + 15=30, max=30 - w=5: check items: item0: dp[5-2]=dp[3]=20 +15=35 item1: dp[5-3]=dp[2]=15 +20=35 item2: dp[5-4]=dp[1]=0 +30=30 max=35 - w=6: item0: dp[6-2]=dp[4]=30 +15=45 item1: dp[6-3]=dp[3]=20 +20=40 item2: dp[6-4]=dp[2]=15 +30=45 max=45 - w=7: item0: dp[7-2]=dp[5]=35 +15=50 item1: dp[7-3]=dp[4]=30 +20=50 item2: dp[7-4]=dp[3]=20 +30=50 max=50

2. Step 2: Verify final dp[7]

   dp[7] = 50

3. Final Answer:

   50 -> Option B

4. Quick Check:

   Max value at capacity 7 = 50 [OK]

Hint: Check all items for each capacity and pick max value [OK]

Common Mistakes:

• Not considering multiple uses of same item
• Incorrectly updating dp array
• Off-by-one errors in loops

4. Identify the bug in the following Rust code snippet for Unbounded Knapsack and select the correct fix:

let weights = vec![1, 3, 4];
let values = vec![10, 40, 50];
let capacity = 6;
let mut dp = vec![0; capacity];

for w in 1..=capacity {
    for i in 0..weights.len() {
        if weights[i] <= w {
            dp[w] = dp[w].max(dp[w - weights[i]] + values[i]);
        }
    }
}
println!("{}", dp[capacity]);

medium

A. Initialize dp with size capacity + 1 instead of capacity.

B. Change loop to for w in 0..capacity instead of 1..=capacity.

C. Use dp[w + weights[i]] instead of dp[w - weights[i]].

D. Replace max with min in dp update.

Solution

1. Step 1: Check dp vector size

   dp is initialized with size capacity (6), but indices go up to capacity (6), so dp[6] access is out of bounds.

2. Step 2: Fix dp size to capacity + 1

   Initialize dp with size capacity + 1 to safely access dp[capacity].

3. Final Answer:

   Initialize dp with size capacity + 1 instead of capacity. -> Option A

4. Quick Check:

   dp size = capacity + 1 to avoid index error [OK]

Hint: DP array size must be capacity + 1 for indexing [OK]

Common Mistakes:

• Off-by-one error in dp array size
• Accessing dp out of bounds
• Incorrect loop ranges

5. Given items with weights [1, 3, 4] and values [10, 40, 50], and a knapsack capacity of 7, what is the maximum value achievable using the Unbounded Knapsack approach?

hard

A. 90

B. 120

C. 140

D. 110

Solution

1. Step 1: Calculate dp values for capacities 1 to 7

   Weights = [1,3,4], Values = [10,40,50] - w=1: dp[1] = max(dp[1-1]+10) = 10 - w=2: dp[2] = max(dp[2-1]+10) = dp[1]+10=20 - w=3: dp[3] = max(dp[3-1]+10=dp[2]+10=30, dp[3-3]+40=dp[0]+40=40) = 40 - w=4: dp[4] = max(dp[4-1]+10=dp[3]+10=50, dp[4-3]+40=dp[1]+40=50, dp[4-4]+50=dp[0]+50=50) = 50 - w=5: dp[5] = max(dp[5-1]+10=dp[4]+10=60, dp[5-3]+40=dp[2]+40=60, dp[5-4]+50=dp[1]+50=60) = 60 - w=6: dp[6] = max(dp[6-1]+10=dp[5]+10=70, dp[6-3]+40=dp[3]+40=80, dp[6-4]+50=dp[2]+50=70) = 80 - w=7: dp[7] = max(dp[7-1]+10=dp[6]+10=90, dp[7-3]+40=dp[4]+40=90, dp[7-4]+50=dp[3]+50=90) = 90

2. Step 2: Re-check calculations for maximum value

   Check if combining items differently yields more: Try using item 3 (weight 4, value 50) twice: total weight 8 > 7 (not possible) Try using item 1 (weight 1, value 10) seven times: 7*10=70 < 90 Try using item 2 (weight 3, value 40) twice + item 1 once: 3+3+1=7 weight, value=40+40+10=90 Maximum value is 90.

3. Final Answer:

   90 -> Option A

4. Quick Check:

   Max value at capacity 7 = 90 [OK]

Hint: Build dp from 1 to capacity, pick max value each step [OK]

Common Mistakes:

• Ignoring multiple item usage
• Wrong dp updates
• Miscalculating max values