Given $N$ items, each with a weight and a value, determine the maximum value you can fit into a knapsack of limited capacity. You can either take an item (1) or leave it (0). You cannot take a fraction of an item.

Think of a Jewelry Thief:

1. You have a bag that can hold 10kg.
2. You see a 6kg Diamond worth $10k and a 5kg Rolex worth $6k.
3. You also see a 5kg Gold bar worth $6k.
4. If you grab the Diamond (The most valuable item), you only have 4kg left. You can't take anything else! Total: $10k.
5. If you skip the Diamond and grab the Rolex + Gold bar, you carry 10kg. Total: $12k.
6. The Moral: Sometimes the "best" item isn't part of the "best" team. DP helps you pick the best team.

---

The Recursive State

solve(index, remainingCapacity) For every item, you have two choices:

1. Exclude: solve(index - 1, remainingCapacity)
2. Include: value[index] + solve(index - 1, remainingCapacity - weight[index]) (Only if weight allows).

Complexity

• Brute Force: $O(2^n)$
• With DP: $O(n \times \text{Capacity})$
• Space: $O(n \times \text{Capacity})$ or $O(\text{Capacity})$ with space optimization.

---

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

  for (let i = 1; i <= n; i++) {
    for (let currentCap = 1; currentCap <= capacity; currentCap++) {
      const weight = weights[i - 1];
      const value = values[i - 1];

      if (weight <= currentCap) {
        // Choice: Max of (Exclude OR Include)
        dp[i][currentCap] = Math.max(
          dp[i - 1][currentCap],
          value + dp[i - 1][currentCap - weight]
        );
      } else {
        // Must exclude
        dp[i][currentCap] = dp[i - 1][currentCap];
      }
    }
  }

  return dp[n][capacity];
}

---

Space Optimization Trick

Look at the code: we only ever reference the previous row (i - 1). This means we don't need a full 2D table! We can solve this with a single 1D array by iterating backwards.

Common Questions

• Explain the Difference between fractional and 0-1 knapsack. (Answer: Greedy for fractional, DP for 0-1).
• What if the capacity is very large? (Answer: DP might become too slow/memory-intensive, use a different approach).
• Partition Equal Subset Sum: This is actually just a variation of the 0-1 knapsack problem! 💎