Unbounded Knapsack Problem in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the dp vector with zeros for the knapsack capacity.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Acapacity

B0

C1

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 or -1 instead of 0 causes incorrect initial values.

We initialize the dp vector with zeros because initially, the maximum value for any capacity is zero.

2fill in blank

medium

Complete the code to iterate over all capacities from 1 to the given capacity.

DSA Rust

for w in 1..=[1] {

Drag options to blanks, or click blank then click option'

Acapacity

Bweights.len()

Cvalues.len()

Dcapacity + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using weights.len() or values.len() as loop limit is incorrect.

We iterate from 1 up to the capacity to fill dp for all sub-capacities.

3fill in blank

hard

Fix the error in the condition to check if the current item can fit in the knapsack capacity.

DSA Rust

if weights[i] [1]= w {

Drag options to blanks, or click blank then click option'

A==

B<

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using < excludes items that fit exactly.

Using == limits to exact matches only.

The item fits if its weight is less than or equal to the current capacity.

4fill in blank

hard

Fill both blanks to update dp[w] with the maximum value including the current item.

DSA Rust

dp[w] = dp[w].[1](dp[w - weights[i]] + [2][i]);

Drag options to blanks, or click blank then click option'

Amax

Bmin

Cvalues

Dweights

Attempts:

3 left

💡 Hint

Common Mistakes

Using min gives wrong minimum value.

Using weights instead of values adds weight, not value.

We use max to keep the best value and add the current item's value from values array.

5fill in blank

hard

Fill all three blanks to complete the nested loops iterating over items and capacities.

DSA Rust

for [1] in 0..[2] {
    for w in 1..=[3] {
        // update dp
    }
}

Drag options to blanks, or click blank then click option'

Ai

Bweights.len()

Ccapacity

Dvalues.len()

Attempts:

3 left

💡 Hint

Common Mistakes

Using values.len() instead of weights.len() may cause confusion.

Looping capacities incorrectly causes wrong dp updates.

We loop over each item index i from 0 to weights.len() and capacities from 1 to capacity.

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