The 0/1 Knapsack & Unbounded Knapsack Pattern

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. The Classic Resource Constraint Problem

Given $N$ items where each item has a weight and a value, determine the maximum value you can carry in a knapsack of maximum weight capacity $W$.

• 0/1 Knapsack: Each item can either be taken 0 times (leave) or 1 time (take).
• Unbounded Knapsack: Each item can be taken infinitely many times (e.g. Coin Change).

2. 0/1 Knapsack State Transition

For item $i$ with weight $w$ and value $v$ at capacity $c$: $$ ext[i][c] = max( ext[i - 1][c], ext[i - 1][c - w] + v)$$

function knapsack01(weights, values, capacity) {
  const n = weights.length;
  // 1D Array Space Optimization (Iterate backwards to prevent reusing same item!)
  const dp = new Array(capacity + 1).fill(0);

  for (let i = 0; i < n; i++) {
    const w = weights[i];
    const v = values[i];

    // Must iterate backwards from capacity down to w!
    for (let c = capacity; c >= w; c--) {
      dp[c] = Math.max(dp[c], dp[c - w] + v);
    }
  }

  return dp[capacity];
}

const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
console.log(knapsack01(weights, values, 5)); // Output: 7 (Items with weights 2 and 3)

3. Unbounded Knapsack: Coin Change Problem

Find the fewest coins needed to make up a given target amount (infinite coin reuse):

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // Base case: 0 amount requires 0 coins

  for (const coin of coins) {
    // Iterate forward because coins can be reused!
    for (let a = coin; a <= amount; a++) {
      dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1, 2, 5], 11)); // Output: 3 (5 + 5 + 1)

4. Key Takeaway: Direction of Iteration

• 0/1 Knapsack (No Reuse): Iterate capacity backwards (c = capacity down to w).
• Unbounded Knapsack (Infinite Reuse): Iterate capacity forwards (c = w up to capacity).

5. Common Mistakes

• Forward Iteration in 0/1 Knapsack: Iterating forwards causes the same item to be added multiple times, turning a 0/1 knapsack into an unbounded knapsack!

6. Next Steps

Use knapsack patterns for subset partition problems. Next, let's explore Longest Common Subsequence (LCS)!