Knapsack

The Knapsack pattern transforms complex optimization problems into tractable dynamic programming solutions. It helps us maximize value while respecting capacity constraints, turning

Real-World Analogy

Imagine you are packing for a trip with a backpack that can hold only 15 kg. You have several items:

• Camera (2 kg, $300 value)
• Laptop (5 kg, $2000 value)
• Jacket (4 kg, $400 value)
• Shoes (3 kg, $500 value)

Without a strategy, you might randomly grab items and either exceed the weight limit or miss high-value combinations. The knapsack algorithm helps you:

• Calculate the optimal combination mathematically
• Consider every possible combination efficiently
• Find the maximum value without exceeding capacity

Types of Knapsack Problems

1. 0/1 Knapsack

Each item can be used at most once (take it or leave it).

Problem: Given n items with weights w[i] and values v[i], and capacity W, maximize value without exceeding capacity.

2. Unbounded Knapsack

Each item can be used unlimited times.

Problem: Same as 0/1, but each item can be chosen multiple times.

3. Fractional Knapsack

Items can be taken in fractions.

Problem: Same as 0/1, but items can be divided (usually solved with greedy).

Visual Explanation: 0/1 Knapsack DP Table

Let’s trace through a small example with items (weight, value): (2, 3), (3, 4), (4, 5) and capacity W=5.

  graph TD
    subgraph DP_Table["DP Table (items x capacity)"]
        direction TB
        Row0["Row 0: [0, 0, 0, 0, 0, 0]"]
        Row1["Row 1: [0, 0, 3, 3, 3, 3]"]
        Row2["Row 2: [0, 0, 3, 4, 4, 7]"]
        Row3["Row 3: [0, 0, 3, 4, 5, 7]"]
    end

    Item1["Item 1 (2kg, $3)"]
    Item2["Item 2 (3kg, $4)"]
    Item3["Item 3 (4kg, $5)"]

    Item1 -->|Update DP| Row1
    Item2 -->|Update DP| Row2
    Item3 -->|Update DP| Row3

    style Item1 fill:#f9d,stroke:#333
    style Item2 fill:#f9d,stroke:#333
    style Item3 fill:#f9d,stroke:#333

How it works:

• Row 0: Empty set, no items available - all zeros
• Row 1: Only item 1 available. At capacity >= 2, value is 3
• Row 2: Items 1 and 2. At capacity 5, we take both: 3 + 4 = 7
• Row 3: All items. At capacity 5, optimal is items 1+2 = 7 (or item 3 = 5)

Cell formula: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1])

• dp[i-1][w]: Don’t take item i
• dp[i-1][w-weight[i-1]] + value[i-1]: Take item i

When to Use This Pattern

Use this pattern when you see these characteristics:

• Need to maximize value or minimize cost with constraints
• Items have weights and values
• Must choose whether to include or exclude each item
• Looking for subset or combination problems

Common interview patterns:

• 0/1 Knapsack: Partition Equal Subset Sum, Target Sum, Ones and Zeroes
• Unbounded: Coin Change, Word Break
• Fractional: Maximum Units on a Truck, IPO

Complexity Analysis

Derivation:

• Time: For 0/1 and unbounded, we iterate through N items and W capacities:
  O(N*W)
• Space: 0/1 needs N+1 rows of W+1 columns:
  O(N*W)
  (can be optimized to
  O(W)
  )
• Greedy: Sorting items by value/weight ratio:
  O(N log N)

Common Mistakes

1. Wrong Iteration Order: Forward iteration in 0/1 leads to using item multiple times (unbounded behavior)
2. Off-by-One Errors: Incorrect array indexing in DP table, especially with the +1 size padding
3. Missing Constraints: Not checking weight/volume limits before including items
4. Overflow Issues: Large sums exceeding integer limits in some languages

Next Steps

Ready to practice? Check out our Code Templates to see memorizable implementations, then head to Practice Problems to solve real LeetCode challenges.