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 unbounded knapsack function for the given inputs?
DSA Typescript
function unboundedKnapsack(W: number, wt: number[], val: number[], n: number): number {
const dp: number[] = new 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 = 7;
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 pick the item with weight 1 and value 10 to maximize value.
✗ Incorrect
The code computes the maximum value using a 1D DP array for unbounded knapsack. For W=7, combinations like one weight-3 (40) + one weight-4 (50) = 90, or two weight-3 (80) + one weight-1 (10) = 90. Picking seven weight-1 items gives only 70. The DP correctly finds 90.
🧠 Conceptual
intermediate1:30remaining
Understanding Unbounded Knapsack Item Choices
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 means you can pick any item as many times as you want, as long as the total weight does not exceed the capacity. This differs from 0/1 knapsack where each item can be chosen at most once.
🔧 Debug
advanced2:00remaining
Identify the Error in This Unbounded Knapsack Code
What error will this TypeScript code produce when run?
DSA Typescript
function unboundedKnapsack(W: number, wt: number[], val: number[], n: number): number {
const dp: number[] = new 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];
}
console.log(unboundedKnapsack(5, [5], [100], 1));Attempts:
2 left
💡 Hint
Check the condition inside the inner loop carefully.
✗ Incorrect
The condition 'wt[j] < i' excludes the case when wt[j] == i, so dp[i] never gets updated for weights exactly equal to an item weight if no smaller items can build it. Here, with single item wt=5, dp[5] remains 0.
📝 Syntax
advanced1:30remaining
Syntax Error in Unbounded Knapsack Code
Which option contains a syntax error preventing the code from compiling?
DSA Typescript
function unboundedKnapsack(W: number, wt: number[], val: number[], n: number): number {
const dp: number[] = new 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];
}Attempts:
2 left
💡 Hint
Look for missing punctuation in the code lines.
✗ Incorrect
Option D is missing a semicolon at the end of the statement, which causes a syntax error in TypeScript.
🚀 Application
expert3:00remaining
Maximum Value for Large Capacity with Given Items
Given items wt = [2, 3, 5], val = [50, 70, 100], and knapsack capacity W = 10, what is the maximum value achievable using unbounded knapsack?
Attempts:
2 left
💡 Hint
Try combinations of items that fill the capacity exactly or nearly exactly with maximum value.
✗ Incorrect
The optimal is five items of weight 2 (50 each): total weight 10, value 250. Two weight-5 items: 200. Two weight-3 + two weight-2: 240. One weight-5 + one weight-3 + one weight-2: 220. No better combination exceeds 250.