Unbounded Knapsack Problem in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

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));

A 100

B 90

C 120

D 80

💡 Hint

Think about how many times you can pick the item with weight 1 and value 10 to maximize value.

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

intermediate

Understanding Unbounded Knapsack Item Choices

In the unbounded knapsack problem, why can items be chosen multiple times?

A Because the problem allows unlimited quantity of each item to maximize value within weight limit.

B Because items are duplicated in the input list to simulate multiple quantities.

C Because the knapsack capacity is infinite, so all items fit.

D Because the problem only considers the first occurrence of each item.

💡 Hint

Think about the difference between 0/1 knapsack and unbounded knapsack.

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

advanced

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));

A Infinite loop occurs

B Returns 90 correctly

C Returns 0

D Throws runtime error: dp[i - wt[j]] is undefined

💡 Hint

Check the condition inside the inner loop carefully.

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

advanced

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];
}

A for (let i = 0; i <= W; i++) {

B if (wt[j] <= i) {

C const dp: number[] = new Array(W + 1).fill(0);

D dp[i] = Math.max(dp[i], dp[i - wt[j]] + val[j])

💡 Hint

Look for missing punctuation in the code lines.

Option D is missing a semicolon at the end of the statement, which causes a syntax error in TypeScript.

🚀 Application

expert

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?

A 250

B 300

C 270

D 200

💡 Hint

Try combinations of items that fill the capacity exactly or nearly exactly with maximum value.

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.