The Knapsack Problem: From 0/1 to Advanced

The Knapsack problem is the “Hello World” of Dynamic Programming. But beyond the basic 0/1 version lies a world of clever optimizations and mathematical tricks. In this post, we’ll break down the three major types and the patterns that solve them.

---

1. The Foundation: 0/1 Knapsack

The Rule: You have one of each item. You either take it (1) or leave it (0).

The Logic

We define dp[i][j] as the maximum value using a subset of the first i items with a total capacity j.

The choice is simple:

1. Exclude the current item: dp[i-1][j]
2. Include the current item: dp[i-1][j - w_i] + v_i

The “Space” Pro-Tip

You don’t need a 2D array. By iterating backwards through the capacity, you can use a single 1D array.

Just update backward to avoid using the same item twice.

for item in items:
    for j in range(W, item.w - 1, -1):
        dp[j] = max(dp[j], dp[j - item.w] + item.v)

---

2. The Buffet: Complete Knapsack

The Rule: Items are infinite. Take as many as you want.

The Transformation

If you can take an item multiple times, the state $dp[j]$ should depend on the current item’s updated state, not the previous one.

The Simple Twist

The code is almost identical to 0/1 Knapsack, but we iterate forwards.

for item in items:
    for j in range(item.w, W + 1):
        dp[j] = max(dp[j], dp[j - item.w] + item.v)

---

3. The Constraint: Bounded Knapsack

The Rule: Each item $i$ has a specific limit $n_i$.

Approach A: Binary Splitting (The Clever Way)

A straightforward approach is to treat each item as $n_i$ different items, each item has the same price and value. But it significantly slows down the algorithm.

So instead of treating it as $n_i$ individual items, we split $n_i$ into powers of 2.

For example, if you have 13 items, split them into packs of 1, 2, 4, and 6. (Note that they should add up to $n_i$.) These four “new” items can combine to form any number from 1 to 13.

• Complexity: $O(W \cdot \sum \log n_i)$

Approach B: Monotonic Queue (The Ultimate Way)

For tight time limits, we use a Monotonic Queue. We group capacities by $j \pmod{w_i}$. For each group, we find the maximum value in a “sliding window” of size $n_i$.

• Complexity: $O(N \cdot W)$ — the gold standard.

Detailed implementation

1. The Core Observation

For an item with weight $w$, value $v$, and count $n$, notice that a capacity $j$ can only be updated by capacities like $j-w, j-2w, \dots, j-kw$ (where $k \le n$).

This means the capacities are partitioned into disjoint sets based on their remainder when divided by $w$.

• Set 0: $0, w, 2w, 3w, \dots$
• Set 1: $1, w+1, 2w+1, 3w+1, \dots$
• Set $r$: $r, w+r, 2w+r, \dots$

The algorithm processes each remainder $r \in [0, w-1]$ independently.

---

2. The Sliding Window Transformation

Let’s look at the transition for a specific remainder $r$. Let $j = k \cdot w + r$. The state looks like this:

$$dp[k \cdot w + r] = \max_{k-n \le i \le k-1} \{ dp[i \cdot w + r] + (k – i) \cdot v \}$$

To make this look like a standard “sliding window maximum” problem, we rearrange the terms:

$$dp[k \cdot w + r] = \max_{k-n \le i \le k-1} \{ dp[i \cdot w + r] – i \cdot v \} + k \cdot v$$

Now, as $k$ increases, we are looking for the maximum value of $(dp[i \cdot w + r] – i \cdot v)$ in a window of size $n$.

---

3. Using the Monotonic Queue

A monotonic queue is a deque (double-ended queue) that keeps elements in decreasing order.

1. Maintain the Window: As we move to the next $k$, we remove indices from the front of the queue that are “out of date” (older than $k-n$).
2. Maintain Monotonicity: Before adding the new value $(dp[k \cdot w + r] – k \cdot v)$ to the back, we remove all values smaller than it. Why? Because a newer, larger value is always a better candidate for the future than an older, smaller value.
3. Get the Max: The current maximum for the window is always at the front of the queue.

---

Summary Table

Problem Type	Core Idea	Best Complexity
0/1	Each item used once	O(NW)
Complete	Infinite items, forward loop	O(NW)
Bounded	Finite count, Binary Splitting	$O(NW \log (\max n_i))$
Bounded (Opt)	Monotonic Queue	O(NW)

---

Final Thoughts

The Knapsack problem isn’t just about bags and gold; it’s about resource allocation. Whether you’re optimizing server load or a financial portfolio, these DP patterns are your best friends.