Unbounded Knapsack Problem in DSA Rust

Mental Model

We want to fill a bag with items to get the most value, and we can use each item as many times as we want.

Analogy: Imagine you have a backpack and unlimited candies of different sizes and tastiness. You want to fill your backpack to get the tastiest mix, and you can pick any candy multiple times.

Capacity: 5
Items: [weight: 1, value: 10], [weight: 3, value: 40], [weight: 4, value: 50]
Backpack capacity -> [0][1][2][3][4][5]
Values stored -> [0][ ][ ][ ][ ][ ]

Dry Run Walkthrough

Input: items: [(weight=1, value=10), (weight=3, value=40), (weight=4, value=50)], capacity=5

Goal: Find the maximum value we can get by filling the backpack with unlimited items without exceeding capacity 5

Step 1: Start with capacity 0, max value is 0 because no space

dp: [0, 0, 0, 0, 0, 0]

Why: Base case: no capacity means no items can be taken

Step 2: For capacity 1, try item weight 1: value 10 fits, update dp[1] = 10

dp: [0, 10, 0, 0, 0, 0]

Why: Item 1 fits once, gives value 10

Step 3: For capacity 2, try item weight 1 twice: dp[2] = dp[1] + 10 = 20

dp: [0, 10, 20, 0, 0, 0]

Why: Using item 1 twice gives value 20

Step 4: For capacity 3, try item weight 3: dp[3] = max(dp[3], dp[0] + 40) = 40

dp: [0, 10, 20, 40, 0, 0]

Why: Item 2 fits exactly, better than using item 1 thrice (30)

Step 5: For capacity 4, try item weight 4: dp[4] = max(dp[4], dp[0] + 50) = 50

dp: [0, 10, 20, 40, 50, 0]

Why: Item 3 fits exactly, value 50 better than previous

Step 6: For capacity 5, try item weight 1: dp[5] = max(dp[5], dp[4] + 10) = 60

dp: [0, 10, 20, 40, 50, 60]

Why: Add item 1 to capacity 4's best value 50 to get 60

Result:

dp: [0, 10, 20, 40, 50, 60]
Maximum value for capacity 5 is 60

Annotated Code

DSA Rust

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

fn unbounded_knapsack(items: &[Item], capacity: usize) -> usize {
    let mut dp = vec![0; capacity + 1];
    for cap in 1..=capacity {
        for item in items {
            if item.weight <= cap {
                let candidate = dp[cap - item.weight] + item.value;
                if candidate > dp[cap] {
                    dp[cap] = candidate; // update max value for this capacity
                }
            }
        }
    }
    dp[capacity]
}

fn main() {
    let items = vec![
        Item { weight: 1, value: 10 },
        Item { weight: 3, value: 40 },
        Item { weight: 4, value: 50 },
    ];
    let capacity = 5;
    let max_value = unbounded_knapsack(&items, capacity);
    println!("Maximum value for capacity {} is {}", capacity, max_value);
}

for cap in 1..=capacity {

iterate over all capacities from 1 to max

for item in items {

check each item for current capacity

if item.weight <= cap {

only consider items that fit in current capacity

let candidate = dp[cap - item.weight] + item.value;

calculate value if we add this item (possibly multiple times)

if candidate > dp[cap] { dp[cap] = candidate; }

update dp if new value is better

Output

Maximum value for capacity 5 is 60

Complexity Analysis

Time: O(n * capacity) because we check each item for every capacity up to max

Space: O(capacity) because we store max values for each capacity in dp array

vs Alternative: Compared to 0/1 knapsack which is also O(n * capacity), unbounded knapsack allows repeated items, but complexity remains similar

Edge Cases

capacity is zero

returns zero because no items can be taken

DSA Rust

let mut dp = vec![0; capacity + 1];

items list is empty

returns zero because no items to choose from

DSA Rust

for item in items {

item weight greater than capacity

item is skipped because it cannot fit

DSA Rust

if item.weight <= cap {

When to Use This Pattern

When a problem allows unlimited use of items to maximize value within capacity, reach for the unbounded knapsack pattern because it efficiently builds solutions using dynamic programming.

Common Mistakes

Mistake: Treating unbounded knapsack like 0/1 knapsack and not allowing repeated items
Fix: Allow repeated use by checking dp[cap - item.weight] + item.value for all capacities

Mistake: Not initializing dp array with zero for base case
Fix: Initialize dp with zeros to represent zero value at zero capacity

Summary

Finds the maximum value achievable with unlimited copies of given items within a capacity limit.

Use when you can pick items multiple times to fill a capacity for maximum value.

The key is to build up solutions for all capacities by reusing previous results allowing repeated items.

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