0 1 Knapsack Problem in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of 0 1 Knapsack Recursive Call

What is the output of the following JavaScript code that solves the 0 1 Knapsack problem recursively for given weights and values?

DSA Javascript

function knapsack(W, weights, values, n) {
  if (n === 0 || W === 0) return 0;
  if (weights[n - 1] > W) {
    return knapsack(W, weights, values, n - 1);
  } else {
    return Math.max(
      values[n - 1] + knapsack(W - weights[n - 1], weights, values, n - 1),
      knapsack(W, weights, values, n - 1)
    );
  }
}

const weights = [1, 3, 4, 5];
const values = [1, 4, 5, 7];
const W = 7;
const n = weights.length;
console.log(knapsack(W, weights, values, n));

A 10

B 12

C 9

D 11

💡 Hint

Think about which items fit into the knapsack without exceeding the weight limit and maximize the value.

The maximum value that fits into the knapsack of capacity 7 is 9, achieved by selecting items with weights 3 and 4 (values 4 and 5).

❓ Predict Output

intermediate

Output of 0 1 Knapsack Dynamic Programming Table

What is the maximum value stored in dp[4][7] after running the bottom-up dynamic programming solution for the 0 1 Knapsack problem with these inputs?

DSA Javascript

function knapsackDP(W, weights, values, n) {
  const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= W; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][W];
}

const weights = [1, 3, 4, 5];
const values = [1, 4, 5, 7];
const W = 7;
const n = weights.length;
console.log(knapsackDP(W, weights, values, n));

A 9

B 10

C 11

D 12

💡 Hint

The dp table stores max values for subproblems. Check combinations that fit weight 7.

The dp table correctly computes the max value as 9 for capacity 7 with given weights and values.

🧠 Conceptual

advanced

Time Complexity of 0 1 Knapsack DP Solution

What is the time complexity of the bottom-up dynamic programming solution for the 0 1 Knapsack problem with n items and capacity W?

A O(n * W)

B O(2^n)

C O(n^2 * W)

D O(n + W)

💡 Hint

Consider the nested loops over items and weight capacities.

The solution uses two nested loops: one over items (n) and one over capacities (W), resulting in O(n * W) time complexity.

🔧 Debug

advanced

Identify the Bug in Recursive Knapsack Code

Which option contains the bug that causes incorrect output in this recursive 0 1 Knapsack implementation?

DSA Javascript

function knapsack(W, weights, values, n) {
  if (n === 0 || W === 0) return 0;
  if (weights[n - 1] >= W) {
    return knapsack(W, weights, values, n - 1);
  } else {
    return Math.max(
      values[n - 1] + knapsack(W - weights[n - 1], weights, values, n - 1),
      knapsack(W, weights, values, n - 1)
    );
  }
}

A return knapsack(W, weights, values, n - 1) should be return knapsack(W - weights[n - 1], weights, values, n - 1)

B weights[n - 1] >= W should be weights[n - 1] > W

C The base case should be if (n === 0 && W === 0) return 0

D Math.max should be Math.min to get max value

💡 Hint

Check the condition that decides if the current item fits in the knapsack.

Using >= excludes items that exactly fit the remaining capacity, causing incorrect results.

🚀 Application

expert

Maximum Value and Items Selected in 0 1 Knapsack

Given weights = [2, 3, 1, 4], values = [3, 4, 2, 5], and capacity W = 5, what is the maximum value and which items (by index starting at 0) are selected in the optimal 0 1 Knapsack solution?

DSA Javascript

function knapsackDP(W, weights, values, n) {
  const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= W; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  let res = dp[n][W];
  let w = W;
  const selected = [];
  for (let i = n; i > 0 && res > 0; i--) {
    if (res !== dp[i - 1][w]) {
      selected.push(i - 1);
      res -= values[i - 1];
      w -= weights[i - 1];
    }
  }
  return { maxValue: dp[n][W], items: selected.reverse() };
}

const weights = [2, 3, 1, 4];
const values = [3, 4, 2, 5];
const W = 5;
const n = weights.length;
console.log(knapsackDP(W, weights, values, n));

A {"maxValue":10,"items":[0,1,2]}

B {"maxValue":9,"items":[1,2]}

C {"maxValue":8,"items":[2,3]}

D {"maxValue":7,"items":[0,1]}

💡 Hint

Trace the dp table and backtrack to find selected items.

The maximum value is 7 by selecting items at indices 0 and 1 (weights 2 and 3, values 3 and 4).

Practice

1. What does the 0 1 Knapsack Problem aim to maximize given a set of items with weights and values?

easy

A. The total value of items without exceeding the weight limit

B. The total weight of items without exceeding the value limit

C. The number of items selected regardless of weight

D. The minimum weight of items selected

Solution

1. Step 1: Understand the problem goal

   The 0 1 Knapsack Problem tries to select items to maximize total value without exceeding the weight capacity.

2. Step 2: Identify the constraint

   The total weight of selected items must not exceed the knapsack's weight limit.

3. Final Answer:

   The total value of items without exceeding the weight limit -> Option A

4. Quick Check:

   Maximize value with weight limit = B [OK]

Hint: Remember: maximize value, not weight or count [OK]

Common Mistakes:

• Confusing weight limit with value limit
• Thinking the problem maximizes number of items
• Ignoring the weight constraint

2. Which of the following is the correct way to initialize the DP array for the 0 1 Knapsack Problem in JavaScript?

easy

A. const dp = new Array(n + 1).fill(new Array(W + 1).fill(0));

B. const dp = Array(n + 1).fill(Array(W + 1).fill(0));

C. const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));

D. const dp = Array(n).fill(Array(W).fill(0));

Solution

1. Step 1: Understand DP array initialization

   We need a 2D array where each row is a separate array to avoid reference issues.

2. Step 2: Choose correct initialization

   Using Array.from with a function creates independent inner arrays, preventing shared references.

3. Final Answer:

   const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0)); -> Option C

4. Quick Check:

   Independent inner arrays = A [OK]

Hint: Use Array.from with function to avoid shared references [OK]

Common Mistakes:

• Using fill with array directly causing shared references
• Initializing with wrong dimensions
• Forgetting to fill inner arrays

3. What is the output of the following code snippet for weights = [1, 3, 4], values = [15, 50, 60], and W = 5?

function knapsack(weights, values, W) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= W; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][W];
}

console.log(knapsack([1, 3, 4], [15, 50, 60], 5));

medium

A. 65

B. 80

C. 60

D. 75

Solution

1. Step 1: Trace DP table filling

   Check items one by one and weights up to 5:
   - Item 1 (weight 1, value 15): dp[1][1..5] = 15
   - Item 2 (weight 3, value 50): dp[2][3] = max(15, 0+50)=50, dp[2][4]=max(15,15+50)=65, dp[2][5]=max(15,15+50)=65
   - Item 3 (weight 4, value 60): dp[3][4]=max(65,0+60)=65, dp[3][5]=max(65,15+60)=75

2. Step 2: Find final answer

   The maximum value for weight 5 is dp[3][5] = 75.

3. Final Answer:

   75 -> Option D

4. Quick Check:

   Max value at W=5 = 75 [OK]

Hint: Trace DP table row by row for each item [OK]

Common Mistakes:

• Adding values without checking weight limit
• Confusing indices in dp array
• Forgetting to compare including vs excluding item

4. Identify the bug in this 0 1 Knapsack implementation and select the fix:

function knapsack(weights, values, W) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= W; w++) {
      if (weights[i] <= w) {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i]] + values[i]);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][W];
}

medium

A. Change weights[i] and values[i] to weights[i - 1] and values[i - 1]

B. Change loop to start i from 0 instead of 1

C. Initialize dp with zeros using fill(1)

D. Change inner loop to run from w = 0 to W - 1

Solution

1. Step 1: Identify index error in array access

   Arrays in JavaScript are zero-indexed, but loop starts at 1, so weights[i] accesses out-of-bound or wrong element.

2. Step 2: Correct index usage

   Use weights[i - 1] and values[i - 1] to access correct item corresponding to dp row i.

3. Final Answer:

   Change weights[i] and values[i] to weights[i - 1] and values[i - 1] -> Option A

4. Quick Check:

   Fix index offset = D [OK]

Hint: Remember dp row i corresponds to item i-1 [OK]

Common Mistakes:

• Using wrong indices causing undefined values
• Changing loop start incorrectly
• Incorrect dp initialization

5. Given items with weights = [2, 3, 5, 7], values = [10, 5, 15, 7], and knapsack capacity W = 10, which set of items maximizes value without exceeding weight? Select the correct maximum value.
Note: You can only take each item once.

hard

A. 25

B. 30

C. 27

D. 22

Solution

1. Step 1: Consider all item combinations within weight limit 10

   Possible combinations:
   - Items 1,2,3: weights 2+3+5=10, values 10+5+15=30 (exceeds capacity? No, equals 10)
   - Items 1,3,4: weights 2+5+7=14 (exceeds 10)
   - Items 2,3,4: weights 3+5+7=15 (exceeds 10)
   - Items 1,4: weights 2+7=9, values 10+7=17
   - Items 3 alone: weight 5, value 15
   - Items 1,2,4: weights 2+3+7=12 (exceeds 10)

2. Step 2: Find max value without exceeding weight

   Best valid combination is items 1,2,3 with total weight 10 and value 30. But since weight is exactly 10, it's valid.
   Check if any other combination gives more value:
   Items 1,3: weight 7, value 25
   Items 3,4: weight 12 (exceeds)
   So max value is 30.

3. Final Answer:

   30 -> Option B

4. Quick Check:

   Max value with W=10 = 30 [OK]

Hint: Try all combos within weight limit to find max value [OK]

Common Mistakes:

• Ignoring exact weight limit equality
• Adding values of items exceeding capacity
• Missing best combination