Challenge - 5 Problems
Unbounded Knapsack Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Unbounded Knapsack DP Table
What is the final maximum value returned by this Rust function for the given inputs?
DSA Rust
fn unbounded_knapsack(capacity: usize, weights: &[usize], values: &[usize]) -> usize {
let mut dp = vec![0; capacity + 1];
for w in 0..=capacity {
for i in 0..weights.len() {
if weights[i] <= w {
dp[w] = dp[w].max(dp[w - weights[i]] + values[i]);
}
}
}
dp[capacity]
}
fn main() {
let capacity = 5;
let weights = vec![1, 3, 4];
let values = vec![10, 40, 50];
let result = unbounded_knapsack(capacity, &weights, &values);
println!("{}", result);
}Attempts:
2 left
💡 Hint
Think about how many times you can use the item with weight 1 and value 10 to fill capacity 5.
✗ Incorrect
The function calculates the maximum value for capacity 5 using unlimited items. Using five items of weight 1 gives 50. Better is one item of weight 4 (50) + one of weight 1 (10) = 60, or one of weight 3 (40) + two of weight 1 (20) = 60. Combinations like weight 3 + 4 exceed capacity. The maximum is 60.
🧠 Conceptual
intermediate1:30remaining
Understanding Unbounded Knapsack Item Usage
In the unbounded knapsack problem, why can items be chosen multiple times?
Attempts:
2 left
💡 Hint
Think about the difference between 0/1 knapsack and unbounded knapsack.
✗ Incorrect
Unbounded knapsack allows unlimited copies of each item, unlike 0/1 knapsack which allows only one copy per item.
🔧 Debug
advanced2:00remaining
Identify the Bug in This Unbounded Knapsack Code
What error will this Rust code produce when run?
DSA Rust
fn unbounded_knapsack(capacity: usize, weights: &[usize], values: &[usize]) -> usize {
let mut dp = vec![0; capacity];
for w in 0..=capacity {
for i in 0..weights.len() {
if weights[i] <= w {
dp[w] = dp[w].max(dp[w - weights[i]] + values[i]);
}
}
}
dp[capacity]
}Attempts:
2 left
💡 Hint
Check the size of dp vector and the indices accessed.
✗ Incorrect
The dp vector is initialized with size capacity, but indices go up to capacity inclusive, causing out of bounds access.
❓ Predict Output
advanced2:00remaining
Result of Modified Unbounded Knapsack with Zero Weight Item
What happens when the unbounded knapsack function is called with an item of zero weight?
DSA Rust
fn unbounded_knapsack(capacity: usize, weights: &[usize], values: &[usize]) -> usize {
let mut dp = vec![0; capacity + 1];
for w in 0..=capacity {
for i in 0..weights.len() {
if weights[i] <= w {
dp[w] = dp[w].max(dp[w - weights[i]] + values[i]);
}
}
}
dp[capacity]
}
fn main() {
let capacity = 5;
let weights = vec![0, 3];
let values = vec![10, 40];
let result = unbounded_knapsack(capacity, &weights, &values);
println!("{}", result);
}Attempts:
2 left
💡 Hint
Consider what happens when weight is zero in the dp update.
✗ Incorrect
A zero-weight item with positive value is updated once per capacity (dp[w] = max(dp[w], dp[w] + 10)), adding 10 once. Then the weight-3 item updates to max with dp[w-3] + 40, resulting in 50 for capacity 5. No infinite loop occurs as updates are performed a fixed number of times.
🚀 Application
expert3:00remaining
Maximum Value for Large Capacity with Given Items
Given items with weights [2, 3, 5] and values [50, 70, 100], what is the maximum value for capacity 10 using unbounded knapsack?
Attempts:
2 left
💡 Hint
Try combinations of items to fill capacity 10 for max value.
✗ Incorrect
Using five items of weight 2 (50 each) = 250, weight 10. Two weight 5 = 200. Three weight 3 = 210 (weight 9). Two weight 3 + two weight 2 = 140 + 100 = 240 (weight 10). One weight 5 + one weight 3 + one weight 2 = 100 + 70 + 50 = 220. The item weight 2 has the highest value density (25/unit), so 250 is optimal.