Unbounded Knapsack Problem in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Unbounded Knapsack Problem?

It is a problem where you have unlimited copies of each item and want to maximize the total value in a knapsack without exceeding its capacity.

beginner

How does the Unbounded Knapsack Problem differ from the 0/1 Knapsack Problem?

In Unbounded Knapsack, you can use an item multiple times, while in 0/1 Knapsack, each item can be used only once.

intermediate

What is the main idea behind the dynamic programming solution for the Unbounded Knapsack Problem?

Build a table where each entry represents the maximum value for a given capacity by considering all items and allowing repeated use.

intermediate

In Rust, what data structure is commonly used to store the maximum values for capacities in Unbounded Knapsack?

A vector (Vec<usize>) is used to store maximum values for each capacity from 0 up to the knapsack capacity.

beginner

Why is the Unbounded Knapsack Problem considered a classic example of dynamic programming?

Because it breaks the problem into smaller subproblems (smaller capacities) and builds up the solution efficiently by reusing results.

In the Unbounded Knapsack Problem, what can you do with each item?

A Use it only once

B Cannot use it

C Use it twice at most

D Use it unlimited times

Unbounded means unlimited use of each item.

What does the dynamic programming table store in the Unbounded Knapsack solution?

A Maximum value for each capacity

B Minimum weight for each value

C Number of items used

D List of items chosen

The table stores the best value achievable for every capacity.

Which Rust data type is best for storing the DP table in Unbounded Knapsack?

A Vec<usize>

B HashMap<usize, usize>

C LinkedList<usize>

D Tuple<usize, usize>

A vector is simple and efficient for indexed storage.

What is the time complexity of the Unbounded Knapsack dynamic programming solution?

A O(n^2)

B O(n + W)

C O(n * W)

D O(W^2)

It depends on number of items (n) and capacity (W).

If the knapsack capacity is 5 and items have weights [1, 3] and values [10, 20], what is the maximum value?

A 40

B 50

C 100

D 70

Using five items of weight 1 (value 10) gives 50, better than one item of weight 3 plus others.

Explain how the dynamic programming approach solves the Unbounded Knapsack Problem step-by-step.

Think about building solutions from smaller capacities to larger.

Describe the difference between 0/1 Knapsack and Unbounded Knapsack and why it matters for the solution.

Focus on item usage limits and DP updates.

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