0
0
DSA Typescriptprogramming~20 mins

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

Choose your learning style9 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Challenge - 5 Problems
🎖️
Knapsack Mastery
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate
2:00remaining
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));
A9
B10
C11
D12
Attempts:
2 left
💡 Hint
Think about which items fit best without exceeding capacity 7.
❓ Predict Output
intermediate
2:00remaining
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);
A9
B7
C5
D11
Attempts:
2 left
💡 Hint
Count each function call including base cases.
🔧 Debug
advanced
3:00remaining
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));
ATypeError
B55
CBug: Using weights[i] and values[i] instead of weights[i-1] and values[i-1]
D40
E65
FBug: Incorrect initialization of dp array
GBug: Loop boundaries off by one
HBug: Missing base case for capacity zero
Attempts:
2 left
💡 Hint
Check array indexing inside the loops carefully.
❓ Predict Output
advanced
2:00remaining
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));
A10
B12
C11
D9
Attempts:
2 left
💡 Hint
Memoization avoids repeated calculations but result matches DP solution.
🧠 Conceptual
expert
2:00remaining
Time Complexity of 0 1 Knapsack Variants
Which statement correctly describes the time complexity of the 0 1 Knapsack problem algorithms?
AThe 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.
BThe DP solution has exponential time complexity because it tries all subsets, while memoization reduces it to linear time O(n).
CAll 0 1 Knapsack solutions have polynomial time complexity O(n*log W) due to sorting items by value.
DThe naive recursive solution runs in linear time O(n), but memoization and DP increase it to exponential time due to overhead.
Attempts:
2 left
💡 Hint
Consider how many subproblems DP solves compared to recursion.