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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of 0 1 Knapsack DP Table

What is the final maximum value stored in the DP table for the given weights and values after running the 0 1 Knapsack algorithm?

DSA Typescript

const weights = [1, 3, 4, 5];
const values = [1, 4, 5, 7];
const capacity = 7;

function knapsack01(weights: number[], values: number[], capacity: number): number {
  const n = weights.length;
  const dp: number[][] = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= capacity; 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][capacity];
}

console.log(knapsack01(weights, values, capacity));

A 9

B 10

C 11

D 12

💡 Hint

Think about which items fit best without exceeding capacity 7.

The DP table computes the maximum value of 9 by selecting the items with weights 3 and 4 (values 4 + 5 = 9). Combinations like weights 3+5=8 (values 4+7=11) exceed capacity, and 1+5=6 (1+7=8) is less.

❓ Predict Output

intermediate

Output of Knapsack Recursive Call Count

How many recursive calls are made when running the naive recursive 0 1 Knapsack function with weights [2, 3], values [4, 5], and capacity 5?

DSA Typescript

let callCount = 0;
function knapsackRecursive(weights: number[], values: number[], capacity: number, n: number): number {
  callCount++;
  if (n === 0 || capacity === 0) return 0;
  if (weights[n - 1] > capacity) {
    return knapsackRecursive(weights, values, capacity, n - 1);
  } else {
    return Math.max(
      values[n - 1] + knapsackRecursive(weights, values, capacity - weights[n - 1], n - 1),
      knapsackRecursive(weights, values, capacity, n - 1)
    );
  }
}

knapsackRecursive([2, 3], [4, 5], 5, 2);
console.log(callCount);

A 9

B 7

C 5

D 11

💡 Hint

Count each function call including base cases.

The recursive calls expand as follows: knapsackRecursive(5,2) calls knapsackRecursive(5,1) and knapsackRecursive(3,1), each further calls base cases. Total calls counted are 7.

🔧 Debug

advanced

Identify the bug in 0 1 Knapsack DP implementation

What is the output of the following code snippet and what is the bug causing it?

DSA Typescript

const weights = [1, 2, 3];
const values = [10, 15, 40];
const capacity = 5;

function knapsack(weights: number[], values: number[], capacity: number): number {
  const n = weights.length;
  const dp: number[][] = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= capacity; 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][capacity];
}

console.log(knapsack(weights, values, capacity));

A TypeError

B 55

C Bug: Using weights[i] and values[i] instead of weights[i-1] and values[i-1]

D 40

E 65

F Bug: Incorrect initialization of dp array

G Bug: Loop boundaries off by one

H Bug: Missing base case for capacity zero

💡 Hint

Check array indexing inside the loops carefully.

The code outputs 55 (correct value by coincidence). The bug is using weights[i] and values[i] instead of weights[i-1] and values[i-1], causing out-of-bounds access at i=n (undefined values). The if condition evaluates to false, copying the previous row without error here.

❓ Predict Output

advanced

Output of Knapsack with Memoization

What is the output of the following memoized 0 1 Knapsack function call?

DSA Typescript

const weights = [1, 3, 4, 5];
const values = [1, 4, 5, 7];
const capacity = 7;

const memo: number[][] = Array.from({ length: weights.length + 1 }, () => Array(capacity + 1).fill(-1));

function knapsackMemo(weights: number[], values: number[], capacity: number, n: number): number {
  if (n === 0 || capacity === 0) return 0;
  if (memo[n][capacity] !== -1) return memo[n][capacity];

  if (weights[n - 1] <= capacity) {
    memo[n][capacity] = Math.max(
      values[n - 1] + knapsackMemo(weights, values, capacity - weights[n - 1], n - 1),
      knapsackMemo(weights, values, capacity, n - 1)
    );
  } else {
    memo[n][capacity] = knapsackMemo(weights, values, capacity, n - 1);
  }
  return memo[n][capacity];
}

console.log(knapsackMemo(weights, values, capacity, weights.length));

A 10

B 12

C 11

D 9

💡 Hint

Memoization avoids repeated calculations but result matches DP solution.

The memoized solution returns the same maximum value as the DP table approach, which is 9 for the given input.

🧠 Conceptual

expert

Time Complexity of 0 1 Knapsack Variants

Which statement correctly describes the time complexity of the 0 1 Knapsack problem algorithms?

A The naive recursive solution has exponential time complexity, while the DP and memoized solutions have polynomial time complexity O(n*W), where n is number of items and W is capacity.

B The DP solution has exponential time complexity because it tries all subsets, while memoization reduces it to linear time O(n).

C All 0 1 Knapsack solutions have polynomial time complexity O(n*log W) due to sorting items by value.

D The naive recursive solution runs in linear time O(n), but memoization and DP increase it to exponential time due to overhead.

💡 Hint

Consider how many subproblems DP solves compared to recursion.

Naive recursion explores all subsets leading to exponential time. DP and memoization store results of subproblems, reducing complexity to O(n*W).

Practice

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

easy

A. The minimum weight of items selected

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

C. The number of items selected regardless of weight

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

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 constraint is the maximum weight the knapsack can carry, so total weight must not exceed this limit.

3. Final Answer:

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

4. Quick Check:

   Maximize value under weight limit = The total value of items without exceeding the weight limit [OK]

Hint: Maximize value, not weight, under capacity limit [OK]

Common Mistakes:

• Confusing weight limit with value limit
• Trying to maximize weight instead of value
• Ignoring the weight constraint

2. Which of the following TypeScript function signatures correctly represents the 0 1 Knapsack function?

easy

A. function knapsack(weights: number[], values: number[], capacity: number): number

B. function knapsack(weights: number, values: number, capacity: number[]): number[]

C. function knapsack(weights: string[], values: string[], capacity: string): string

D. function knapsack(weights: number[], values: number[], capacity: string): void

Solution

1. Step 1: Check parameter types

   Weights and values should be arrays of numbers, capacity a number, and return type a number representing max value.

2. Step 2: Match correct signature

   function knapsack(weights: number[], values: number[], capacity: number): number matches this: arrays for weights and values, number for capacity, returns number.

3. Final Answer:

   function knapsack(weights: number[], values: number[], capacity: number): number -> Option A

4. Quick Check:

   Correct types and return = function knapsack(weights: number[], values: number[], capacity: number): number [OK]

Hint: Weights and values are number arrays; capacity is a number [OK]

Common Mistakes:

• Using string types instead of number
• Swapping array and single number types
• Incorrect return type

3. What is the output of the following TypeScript code snippet for 0 1 Knapsack?

const weights = [1, 3, 4];
const values = [15, 50, 60];
const capacity = 5;

function knapsack(w: number[], v: number[], c: number): number {
  const n = w.length;
  const dp = Array(n + 1).fill(null).map(() => Array(c + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= c; j++) {
      if (w[i - 1] <= j) {
        dp[i][j] = Math.max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - w[i - 1]]);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n][c];
}

console.log(knapsack(weights, values, capacity));

medium

A. 65

B. 60

C. 75

D. 50

Solution

1. Step 1: Understand DP table filling

   For capacity 5, items: (1,15), (3,50), (4,60). Check combinations: - Item1 + Item2: weight 4, value 65 - Item3 alone: weight 4, value 60 - Item2 alone: weight 3, value 50 - Item1 + Item3: weight 5, value 75

2. Step 2: Find max value under capacity

   Item1 + Item3 total weight 5, value 75 is max possible under capacity 5.

3. Final Answer:

   75 -> Option C

4. Quick Check:

   Max value with capacity 5 = 75 [OK]

Hint: Check all item combos fitting capacity, pick max value [OK]

Common Mistakes:

• Ignoring combined items
• Choosing single highest value item only
• Miscomputing weights or values

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

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

medium

A. Change Array(n + 1).fill([]) to Array(n + 1).fill(null)

B. Change Array(n + 1).fill([]) to Array(n + 1).fill([]).map(() => Array(capacity + 1).fill(0))

C. No bug, code is correct

D. Change Array(n + 1).fill([]) to Array(n + 1).fill(0)

Solution

1. Step 1: Examine the dp array initialization

   The code uses Array(n + 1).fill([]).map(() => Array(capacity + 1).fill(0)), but fill([]) fills all elements with the same array reference, which is then overridden by map creating new arrays. However, the initial fill([]) is unnecessary and can cause confusion or bugs if map is removed.

2. Step 2: Correct initialization

   Better to initialize dp as Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0)) or directly with map to ensure independent arrays without shared references.

3. Final Answer:

   Change Array(n + 1).fill([]) to Array(n + 1).fill([]).map(() => Array(capacity + 1).fill(0)) -> Option B

4. Quick Check:

   Ensure dp rows are independent arrays to avoid shared reference bugs [OK]

Hint: Use map to create independent arrays for dp rows [OK]

Common Mistakes:

• Assuming fill([]) creates independent arrays
• Ignoring shared reference issues
• Claiming no bug when shared references exist

5. Given items with weights [2, 3, 5, 7] and values [10, 5, 15, 7], and a knapsack capacity of 10, which set of items maximizes value without exceeding capacity?

hard

A. Items with weights 2, 3, and 5 (total value 30)

B. Items with weights 3 and 7 (total value 12)

C. Items with weights 5 and 7 (total value 22)

D. Items with weights 2 and 7 (total value 17)

Solution

1. Step 1: Calculate total weights and values for each option

   Items with weights 2, 3, and 5 (total value 30): weights 2+3+5=10, values 10+5+15=30 Items with weights 3 and 7 (total value 12): weights 3+7=10, values 5+7=12 Items with weights 5 and 7 (total value 22): weights 5+7=12 (exceeds capacity) Items with weights 2 and 7 (total value 17): weights 2+7=9, values 10+7=17

2. Step 2: Choose max value under capacity

   Items with weights 2, 3, and 5 (total value 30) fits capacity exactly and has highest value 30.

3. Final Answer:

   Items with weights 2, 3, and 5 (total value 30) -> Option A

4. Quick Check:

   Max value under capacity 10 = 30 [OK]

Hint: Sum weights ≤ capacity; pick max value combo [OK]

Common Mistakes:

• Choosing items exceeding capacity
• Ignoring combined item values
• Selecting fewer items with lower total value