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 Maximum Value Calculation
What is the output of the following JavaScript code that solves the unbounded knapsack problem for given weights, values, and capacity?
DSA Javascript
function unboundedKnapsack(W, wt, val, n) {
let dp = Array(W + 1).fill(0);
for (let i = 0; i <= W; i++) {
for (let j = 0; j < n; j++) {
if (wt[j] <= i) {
dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
}
}
}
return dp[W];
}
const W = 5;
const wt = [1, 3, 4];
const val = [10, 40, 50];
const n = wt.length;
console.log(unboundedKnapsack(W, wt, val, n));Attempts:
2 left
💡 Hint
Think about how many times you can use each item to maximize value within the capacity.
✗ Incorrect
The maximum value for capacity 5 is 60 by using one item of weight 4 (value 50) and one item of weight 1 (value 10), total 60, or one item of weight 3 (value 40) and two items of weight 1 (value 10 each), total 60. The code output is 60.
🧠 Conceptual
intermediate1:00remaining
Understanding Unbounded Knapsack Item Usage
In the unbounded knapsack problem, what does 'unbounded' mean regarding item usage?
Attempts:
2 left
💡 Hint
Think about the difference between bounded and unbounded knapsack.
✗ Incorrect
'Unbounded' means you can use each item as many times as you want, unlike the 0/1 knapsack where each item can be used only once.
🔧 Debug
advanced2:00remaining
Identify the Error in Unbounded Knapsack Implementation
What error will the following code produce when run, and why?
function unboundedKnapsack(W, wt, val, n) {
let dp = Array(W + 1).fill(0);
for (let i = 1; i <= W; i++) {
for (let j = 0; j < n; j++) {
if (wt[j] < i) {
dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
}
}
}
return dp[W];
}
const W = 5;
const wt = [1, 3, 4];
const val = [10, 40, 50];
const n = wt.length;
console.log(unboundedKnapsack(W, wt, val, n));
Attempts:
2 left
💡 Hint
Check the condition inside the inner loop carefully.
✗ Incorrect
The condition 'wt[j] < i' excludes the case when wt[j] equals i, so dp[i] is not updated for items that exactly fit the capacity i. This causes dp[i] to be less than the correct maximum value.
🚀 Application
advanced1:30remaining
Maximum Number of Items in Unbounded Knapsack
Given weights [2, 3, 5] and capacity 10, what is the maximum number of items that can be put in the knapsack without exceeding capacity?
Attempts:
2 left
💡 Hint
Try to fill the knapsack with the smallest weight items to maximize count.
✗ Incorrect
Using five items of weight 2 each fills capacity exactly (2*5=10). Using other combinations results in fewer items.
❓ Predict Output
expert2:30remaining
Output of Unbounded Knapsack with Zero Weight Item
What will be the output of this code snippet that includes an item with zero weight in the unbounded knapsack problem?
DSA Javascript
function unboundedKnapsack(W, wt, val, n) {
let dp = Array(W + 1).fill(0);
for (let i = 0; i <= W; i++) {
for (let j = 0; j < n; j++) {
if (wt[j] <= i) {
dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j]);
}
}
}
return dp[W];
}
const W = 5;
const wt = [0, 3, 4];
const val = [10, 40, 50];
const n = wt.length;
console.log(unboundedKnapsack(W, wt, val, n));Attempts:
2 left
💡 Hint
Consider what happens when an item has zero weight but positive value.
✗ Incorrect
Although a zero-weight item with positive value theoretically allows infinite value (unbounded usage), this DP implementation adds its value only once per capacity (since dp[i - 0] uses the current dp[i] before update within the single pass per i and j), resulting in an output of 60.