🗓️ Day 23: 0/1 Knapsack Intro

📘 What You’ll Learn

Introduction to the classic 0/1 Knapsack problem
How to model choices using dynamic programming
Recursive, memoized, and tabulated approaches
Building bottom-up solutions
Thinking in "capacity" and "items"

🧠 Concept

You are given n items, each with a weight and a value. You have a bag (knapsack) with capacity W. Each item can be taken at most once.

Your goal is to maximize the total value you can carry in your knapsack without exceeding the capacity.

Let:

dp[i][w] = max value using items 0..i with total weight w

Transition:

if (weights[i] <= w) {
  dp[i][w] = Math.max(
    dp[i - 1][w],
    values[i] + dp[i - 1][w - weights[i]]
  );
} else {
  dp[i][w] = dp[i - 1][w];
}

Base case:

dp[0][w] = weights[0] <= w ? values[0] : 0

📊 Visualization

Imagine a grid where rows are items and columns are knapsack capacities. For each cell, you decide:

❌ Don't take the current item: use the value from the row above
✅ Take it (if possible): add value and subtract weight

You fill this table row-by-row, column-by-column.

💻 TypeScript Example

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

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

⏱️ Time: O(nW)
💾 Space: O(nW) (can optimize to O(W))

🧪 LeetCode Homework

📘 416. Partition Equal Subset Sum

Can you split an array into two parts with equal sum? Very similar to knapsack!

📘 494. Target Sum

Another variant of using + or - to reach a target sum.

console.log(knapsack([60, 100, 120], [10, 20, 30], 50)); // 220

📌 Key Takeaways

0/1 Knapsack is the gateway to most DP problems
Think in terms of choices: take it or leave it
Track capacity carefully
Know how to build and fill a DP table

🔮 Up Next

▶️ Day 24: DP on Subsequences