DP -- Knapsack

AL-27 | Choose items with weights and values to maximize total value under a capacity constraint -- the archetypal DP problem and a building block for dozens of CF patterns.

Difficulty: [Intermediate]Prerequisites: DP -- 1D IntroductionCF Rating Range: 1300 -- 1700

Quick Revisit

• USE WHEN: select items to maximize/minimize value subject to a capacity constraint
• INVARIANT: dp[w] = best value achievable with capacity at most w
• TIME: O(n*W) | SPACE: O(W) with 1D rolling
• CLASSIC BUG: wrong loop direction -- backward for 0/1, forward for unbounded
• PRACTICE: DP Practice Ladder

Contents

• Intuition
  • What the Code Won't Teach You
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
  • Mental Traps
• Self-Test
• Practice Problems
• Further Reading

---

Intuition

You have 4 items and a knapsack with capacity $W=7$.

  Item | Weight | Value
  -----+--------+------
    A  |   2    |   3
    B  |   3    |   4
    C  |   4    |   5
    D  |   5    |   7

Every item is either in the bag or not. How many subsets must you check? Each item has 2 choices (take / skip), so $2^4=16$ subsets:

  {}           -> w=0  v=0
  {A}          -> w=2  v=3
  {B}          -> w=3  v=4
  {C}          -> w=4  v=5
  {D}          -> w=5  v=7
  {A,B}        -> w=5  v=7
  {A,C}        -> w=6  v=8
  {A,D}        -> w=7  v=10  <-- fits! best so far
  {B,C}        -> w=7  v=9
  {B,D}        -> w=8  v=11  X  over capacity
  {C,D}        -> w=9  v=12  X  over capacity
  {A,B,C}      -> w=9  v=12  X  over capacity
  {A,B,D}      -> w=10 v=14  X  over capacity
  {A,C,D}      -> w=11 v=15  X  over capacity
  {B,C,D}      -> w=12 v=16  X  over capacity
  {A,B,C,D}    -> w=14 v=19  X  over capacity

Best feasible: $\{A,D\}$ with value $10$. But we checked all 16 subsets. With $n=40$ items that is $2^{40}\approx {10}^{12}$ subsets -- hopeless.

For each item, you make a binary choice (take it or skip it); the optimal answer for a given remaining capacity depends only on that capacity and which items you still have left to consider -- not on the specific combination you already picked.

So define $dp[j]$ = best value achievable with capacity $j$. When you process item $i$ you ask: "Is it better to skip this item (keep $dp[j]$) or take it (grab $dp[j-w_i]+v_i$)?"

Think of it like packing a suitcase with a weight limit. You lay out every item on the bed, then pick them up one at a time. For each item you hold it up and ask, "Does adding this to the suitcase beat what I already have at this weight?" You never need to remember which specific shirts you packed -- only the total weight consumed so far matters.

Visual Walkthrough

Same items: $A(2,3)$, $B(3,4)$, $C(4,5)$, $D(5,7)$. Capacity $W=7$.

Step 0 -- Initialize. All capacities start at value 0.

  dp[]:  [ 0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 ]
           0    1    2    3    4    5    6    7

Step 1 -- Process item A (w=2, v=3). Scan j = 7 down to 2.

  j=7: dp[7] = max(dp[7], dp[5]+3) = max(0, 0+3) = 3
  j=6: dp[6] = max(dp[6], dp[4]+3) = max(0, 0+3) = 3
  j=5: dp[5] = max(dp[5], dp[3]+3) = max(0, 0+3) = 3
  j=4: dp[4] = max(dp[4], dp[2]+3) = max(0, 0+3) = 3
  j=3: dp[3] = max(dp[3], dp[1]+3) = max(0, 0+3) = 3
  j=2: dp[2] = max(dp[2], dp[0]+3) = max(0, 0+3) = 3

  dp[]:  [ 0 |  0 |  3 |  3 |  3 |  3 |  3 |  3 ]
           0    1    2    3    4    5    6    7

Step 2 -- Process item B (w=3, v=4). Scan j = 7 down to 3.

  j=7: dp[7] = max(dp[7], dp[4]+4) = max(3, 3+4) = 7
  j=6: dp[6] = max(dp[6], dp[3]+4) = max(3, 3+4) = 7
  j=5: dp[5] = max(dp[5], dp[2]+4) = max(3, 3+4) = 7
  j=4: dp[4] = max(dp[4], dp[1]+4) = max(3, 0+4) = 4
  j=3: dp[3] = max(dp[3], dp[0]+4) = max(3, 0+4) = 4

  dp[]:  [ 0 |  0 |  3 |  4 |  4 |  7 |  7 |  7 ]
           0    1    2    3    4    5    6    7

Step 3 -- Process item C (w=4, v=5). Scan j = 7 down to 4.

  j=7: dp[7] = max(dp[7], dp[3]+5) = max(7, 4+5) = 9
  j=6: dp[6] = max(dp[6], dp[2]+5) = max(7, 3+5) = 8
  j=5: dp[5] = max(dp[5], dp[1]+5) = max(7, 0+5) = 7
  j=4: dp[4] = max(dp[4], dp[0]+5) = max(4, 0+5) = 5

  dp[]:  [ 0 |  0 |  3 |  4 |  5 |  7 |  8 |  9 ]
           0    1    2    3    4    5    6    7

Step 4 -- Process item D (w=5, v=7). Scan j = 7 down to 5.

  j=7: dp[7] = max(dp[7], dp[2]+7) = max(9, 3+7) = 10
  j=6: dp[6] = max(dp[6], dp[1]+7) = max(8, 0+7) = 8
  j=5: dp[5] = max(dp[5], dp[0]+7) = max(7, 0+7) = 7

  dp[]:  [ 0 |  0 |  3 |  4 |  5 |  7 |  8 | 10 ]
           0    1    2    3    4    5    6    7
                                              ^^
                                         answer = 10
                                    (items A+D, weight 2+5=7)

Why reverse? We scan $j$ from $W$ down to $w_i$. When we update $dp[j]$, the value $dp[j-w_i]$ has NOT been touched yet in this round, so it still reflects the world without item $i$. This guarantees each item is used at most once -- the 0-1 property. If we scanned forward instead, $dp[j-w_i]$ might already include item $i$, silently turning 0-1 knapsack into unbounded knapsack.

The Invariant

+----------------------------------------------------------------+
|  dp[j] after processing items 0..i                             |
|    = maximum total value using a subset of items 0..i          |
|      whose total weight is <= j.                               |
|                                                                |
|  The reverse inner loop (j from W down to w[i]) ensures each   |
|  item is counted at most once (0-1 knapsack).                  |
+----------------------------------------------------------------+

When knapsack DP applies. The problem gives you a set of items (or choices), each with a cost or weight, and a budget or capacity constraint. You must select a subset (or multiset) that optimizes some value while staying within the constraint.

Recognize the variant by its reuse rule:

Variant	Reuse rule	Loop direction	Typical phrasing
0-1 knapsack	each item at most once	$j$ high to low	"pick a subset"
Unbounded	unlimited copies	$j$ low to high	"coins", "unlimited supply"
Bounded	at most $c_i$ copies	binary-split then 0-1	"limited stock"
Subset sum	value = weight	reverse (0-1)	"reach exact sum $S$?"

🤔 Checkpoint: In 0/1 knapsack, why must the inner loop run capacity j from W down to w[i]? What happens if you loop from w[i] up to W?

Think first, then click

Looping forward lets `dp[j - w[i]]` read a value that was *already updated* in the same iteration of item `i`. That means item `i`'s value gets added multiple times -- effectively treating it as an unlimited-supply item (unbounded knapsack). Looping backward ensures `dp[j - w[i]]` still holds the value from *before* item `i` was considered, guaranteeing each item is used at most once.

What the Code Won't Teach You

Why the iteration direction matters -- really. The templates say "reverse for 0/1, forward for unbounded," but the reason is what sticks: in the 1D optimization, dp[j - w[i]] is read when computing dp[j]. In reverse order, that cell hasn't been updated yet in this pass -- it reflects the world before item $i$. In forward order, that cell has been updated -- it may already include item $i$, allowing reuse. The direction is not a convention; it is the mechanism that enforces the reuse constraint.

  2D DP TABLE -- 0/1 KNAPSACK (Diagram A)
  Items: A(w=2,v=3), B(w=3,v=4).  Capacity W=5.

  dp[i][j] = best value using items 0..i with capacity <= j

               j=0    j=1    j=2    j=3    j=4    j=5
             +------+------+------+------+------+------+
   no items  |   0  |   0  |   0  |   0  |   0  |   0  |
             +------+------+------+------+------+------+
   + item A  |   0  |   0  |   3  |   3  |   3  |   3  |
   (w=2,v=3) |      |      |   ↑  |   ↑  |   ↑  |   ↑  |
             +------+------+---+--+---+--+---+--+---+--+
   + item B  |   0  |   0  |   3  |   4  |   4  |   7  |
   (w=3,v=4) |      |      |      |   ↑  |   ↑  |   ↑  |
             +------+------+------+---+--+---+--+---+--+

  Each cell: dp[i][j] = max(SKIP, TAKE)
    SKIP item i:  dp[i-1][j]            <- look UP (↑)
    TAKE item i:  dp[i-1][j-w[i]] + v[i] <- look UP-LEFT by w[i] cols (↖)

  Example -- computing dp[B][5]:
    SKIP B: dp[A][5] = 3                                   (↑ straight up)
    TAKE B: dp[A][5-3] + 4 = dp[A][2] + 4 = 3 + 4 = 7    (↖ up-left by 3)
    dp[B][5] = max(3, 7) = 7  OK   (took A+B, weight 2+3=5)

  KEY: In the 1D optimization, "up" = "same array, previous pass."
       Reverse iteration keeps dp[j-w[i]] from the previous pass.

The "take or skip" decision framework. At each item, you either include it or you don't -- this binary choice is what makes brute force exponential ($2^n$ subsets). DP collapses the exponential tree because many branches lead to the same (capacity, items-remaining) state. The key insight: you don't need to remember which items you picked, only the total weight consumed. This is optimal substructure over the capacity dimension.

When knapsack DP is the wrong approach:

• If $W$ is huge (${10}^9$) but $n$ is small ($n\le 40$), the DP table doesn't fit. Use meet-in-the-middle: split items into two halves, enumerate all $2^{n/2}$ subset sums per half, sort one, binary search for the complement.
• If items have special structure (e.g., all values equal, or value proportional to weight), greedy or sorting may suffice -- no DP needed.
• If items are fractional (you can take 0.37 of an item), sort by value/weight ratio and take greedily. This is fractional knapsack, not 0/1.

The subset sum special case. Subset sum is knapsack where value = weight. You're asking "can I reach exactly sum $S$?" instead of "what's the max value at capacity $W$?" The DP array becomes boolean (dp[j] = can I reach sum $j$?), and the transition is dp[j] |= dp[j - x] instead of dp[j] = max(dp[j], dp[j - w] + v). Recognizing this simplification avoids carrying unnecessary value arrays.

When to Reach for This

Trigger phrases in problem statements:

• "weight limit", "capacity constraint", "budget of $W$"
• "pick items with total cost $\le W$"
• "subset sum", "partition into equal halves"
• "minimum coins to make change"
• "maximize profit without exceeding weight"

Counter-examples -- knapsack is NOT the right tool when:

• There is no capacity / budget constraint at all. A simple greedy or sorting-based approach may work instead.
• Items are fractional (you can take 0.37 of an item). The greedy strategy of sorting by value-per-weight and taking greedily is optimal (fractional knapsack).
• $W$ is astronomically large (e.g. ${10}^{18}$) but $n$ is small ($n\le 40$). Use meet-in-the-middle instead of DP.

🤔 Checkpoint: You have n = 30 items and capacity W = 10^{18}. Standard knapsack DP is O(nW) -- way too slow. What alternative approach handles small n with huge W?

Think first, then click

Meet-in-the-middle: split the items into two halves of ~15 each, enumerate all `2^{15}` subsets for each half (storing weight and value), sort one half by weight, then for each subset in the other half, binary search for the best complement that fits within `W`. Total time: `O(2^{n/2} * n)`, which is feasible for `n <= 40`.

---

C++ STL Reference

Function / Class	Header	What it does	Time
vector<int> dp(W+1, 0)	<vector>	Allocate and zero-init DP array	$O(W)$
vector<long long> dp(W+1, -1)	<vector>	Init with sentinel for infeasible states	$O(W)$
fill(dp.begin(), dp.end(), 0)	<algorithm>	Reset DP array between test cases	$O(W)$
max(a, b)	<algorithm>	Pick the better of skip/take	$O(1)$
min(a, b)	<algorithm>	Used in min-cost knapsack variants	$O(1)$
bitset<MAXW> bs	<bitset>	Fast subset-sum via shift-OR	--
bs <<= k	<bitset>	Shift reachable sums by weight $k$	$O(W/64)$
bs.test(S)	<bitset>	Check if sum $S$ is reachable	$O(1)$
accumulate(w.begin(), w.end(), 0LL)	<numeric>	Compute total weight (for bounds)	$O(n)$

---

Implementation (Contest-Ready)

Version 1: 0/1 Knapsack -- Minimal Template

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];

    vector<long long> dp(W + 1, 0);
    for (int i = 0; i < n; i++)
        for (int j = W; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << *max_element(dp.begin(), dp.end()) << "\n";
}

Why Loop Direction Matters in 1D Knapsack Optimization

0/1 knapsack (each item used at most once): iterate capacity right to left.

for (int j = W; j >= w[i]; j--)
    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

Right-to-left ensures dp[j - w[i]] is from the PREVIOUS row (item i not yet used). If you go left-to-right, dp[j - w[i]] was already updated in THIS row, meaning item i was used again -- you've accidentally solved unbounded knapsack.

Unbounded knapsack (each item used unlimited times): iterate capacity left to right.

for (int j = w[i]; j <= W; j++)
    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

Left-to-right deliberately reads the CURRENT row, allowing item i to be used multiple times.

Memory trick: This is the 2D -> 1D space optimization. The loop direction controls whether you read "previous row" or "current row" values.

Version 1b: 0/1 Knapsack -- Explained

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];

    // dp[j] = max value achievable with total weight exactly <= j.
    // Initialize to 0: with zero items, every capacity has value 0.
    vector<long long> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        // Iterate capacity from W DOWN TO w[i].
        // Reverse order guarantees dp[j - w[i]] still reflects
        // the state WITHOUT item i (previous row in 2D formulation).
        for (int j = W; j >= w[i]; j--) {
            // skip item i: dp[j] stays as-is
            // take item i: dp[j - w[i]] + v[i]
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    // Answer is max over all capacities (or just dp[W] if we want
    // exactly capacity W, but typically we want the global max).
    cout << *max_element(dp.begin(), dp.end()) << "\n";
}

Version 2: Unbounded Knapsack -- Minimal Template

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];

    vector<long long> dp(W + 1, 0);
    for (int i = 0; i < n; i++)
        for (int j = w[i]; j <= W; j++)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << *max_element(dp.begin(), dp.end()) << "\n";
}

Version 2b: Unbounded Knapsack -- Explained

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];

    // dp[j] = max value with capacity j, items reusable.
    vector<long long> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        // Iterate capacity from w[i] UP TO W.
        // Forward order means dp[j - w[i]] may already include item i
        // from this round -- that's exactly what we want for unlimited reuse.
        for (int j = w[i]; j <= W; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << *max_element(dp.begin(), dp.end()) << "\n";
}

---

Operations Reference

Choosing the right variant determines whether your solution fits in the time limit. Use this table to match your problem's constraints to the best algorithm.

Variant	Time	Space
0/1 Knapsack (2D)	$O(n\cdot W)$	$O(n\cdot W)$
0/1 Knapsack (1D optimized)	$O(n\cdot W)$	$O(W)$
Unbounded Knapsack	$O(n\cdot W)$	$O(W)$
Bounded Knapsack (binary splitting)	$O(n\cdot W\cdot \log c_{max})$	$O(W)$
Subset Sum (boolean)	$O(n\cdot W)$	$O(W)$
Subset Sum (bitset)	$O(n\cdot W/64)$	$O(W/64)$
Meet-in-the-middle (when $n\le 40$, $W$ huge)	$O(2^{n/2}\cdot n)$	$O(2^{n/2})$

---

Problem Patterns & Tricks

Pattern 1: Classic 0/1 Knapsack

Given items with weight and value, maximize value within capacity. Direct application of the 1D DP.

for (int i = 0; i < n; i++)
    for (int j = W; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

Examples: CF 687C -- The Values You Can Make, AtCoder DP-D -- Knapsack 1

---

Pattern 2: Coin Change (Unbounded Knapsack)

"Minimum number of coins to make sum $S$" or "number of ways to make sum $S$." This is unbounded knapsack where the "value" is 1 (count) or the optimization target changes.

// Minimum coins
vector<int> dp(S + 1, INT_MAX);
dp[0] = 0;
for (int c : coins)
    for (int j = c; j <= S; j++)
        if (dp[j - c] != INT_MAX)
            dp[j] = min(dp[j], dp[j - c] + 1);

Examples: CF 1003C -- Intense Heat, CSES -- Coin Combinations I

---

Pattern 3: Subset Sum / Partition Equal Subset

"Can we split an array into two subsets with equal sum?" Compute total sum $S$; if $S$ is odd, answer is NO. Otherwise, run subset-sum DP for target $S/2$.

int S = accumulate(a.begin(), a.end(), 0);
if (S % 2 != 0) { cout << "NO\n"; return 0; }
int half = S / 2;
vector<bool> dp(half + 1, false);
dp[0] = true;
for (int x : a)
    for (int j = half; j >= x; j--)
        dp[j] = dp[j] || dp[j - x];
cout << (dp[half] ? "YES" : "NO") << "\n";

Examples: CF 1516C -- Baby Ehab Partitions Again, CSES -- Two Sets

---

Pattern 4: Counting the Number of Ways

Instead of maximizing value, count how many subsets sum to exactly $S$. Replace max with +=.

vector<long long> dp(S + 1, 0);
dp[0] = 1;
for (int x : a)
    for (int j = S; j >= x; j--)  // 0/1: reverse
        dp[j] += dp[j - x];
// dp[S] = number of subsets summing to S

Examples: CF 1433F -- Zero Remainder Sum, CSES -- Coin Combinations II

---

Pattern 5: Knapsack with Large Values, Small Weights

When $W$ is huge but $v_{max}\cdot n$ is small, invert the DP: $dp[v]$ = minimum weight to achieve value exactly $v$. Binary search or scan for the largest achievable value within weight $W$.

int V = n * max_v;
vector<long long> dp(V + 1, LLONG_MAX);
dp[0] = 0;
for (int i = 0; i < n; i++)
    for (int j = V; j >= v[i]; j--)
        if (dp[j - v[i]] != LLONG_MAX)
            dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
long long ans = 0;
for (int j = 0; j <= V; j++)
    if (dp[j] <= W) ans = j;

Examples: AtCoder DP-E -- Knapsack 2

---

Pattern 6: Bitset Subset Sum

When $n$ and $W$ are both large but fit in a bitset, use shift-OR for $O(n\cdot W/64)$.

bitset<100001> bs;
bs[0] = 1;
for (int x : a)
    bs |= (bs << x);
// bs[S] == 1 iff sum S is reachable

Examples: CF 1516C -- Baby Ehab Partitions Again, CF 755F -- PolandBall and Gifts

---

Pattern 7: Bounded Knapsack via Binary Splitting

Each item has count $c_i$. Split $c_i$ into powers of 2 and a remainder, then run 0/1 knapsack on the expanded list.

vector<pair<int,int>> items; // (weight, value) after expansion
for (int i = 0; i < n; i++) {
    int rem = c[i], k = 1;
    while (rem > 0) {
        int take = min(k, rem);
        items.push_back({w[i] * take, v[i] * take});
        rem -= take;
        k *= 2;
    }
}
// Run standard 0/1 knapsack on 'items'

Examples: CF 106C -- Buns

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|                    DP KNAPSACK CHEAT SHEET                        |
+------------------------------------------------------------------+
| WHEN TO USE:                                                     |
|   - "Pick subset, maximize value under weight limit"             |
|   - "Can we reach exact sum S?"  (subset sum)                   |
|   - "Min coins to make change"   (unbounded)                    |
|   - "Count ways to partition"    (counting variant)              |
+------------------------------------------------------------------+
| 0/1 KNAPSACK (each item once):                                   |
|   for (int i = 0; i < n; i++)                                   |
|     for (int j = W; j >= w[i]; j--)       // REVERSE            |
|       dp[j] = max(dp[j], dp[j-w[i]] + v[i]);                   |
+------------------------------------------------------------------+
| UNBOUNDED KNAPSACK (unlimited reuse):                            |
|   for (int i = 0; i < n; i++)                                   |
|     for (int j = w[i]; j <= W; j++)       // FORWARD            |
|       dp[j] = max(dp[j], dp[j-w[i]] + v[i]);                   |
+------------------------------------------------------------------+
| SUBSET SUM (boolean):                                            |
|   dp[0] = true;                                                  |
|   for (x : a) for (j = S; j >= x; j--) dp[j] |= dp[j-x];     |
+------------------------------------------------------------------+
| TIME: O(n * W)     SPACE: O(W)     BITSET: O(n * W / 64)       |
| REVERSE = 0/1      FORWARD = unbounded      WATCH: long long   |
+------------------------------------------------------------------+

---

Gotchas & Debugging

Reverse loop for 0/1, forward for unbounded

The single most common knapsack bug. If you iterate $j$ from small to large in a 0/1 problem, each item gets used multiple times -- your code silently becomes unbounded knapsack. The result is wrong but compiles and runs fine, so it's hard to catch.

Rule: 0/1 = reverse. Unbounded = forward. Tattoo this on your arm.

Integer overflow

With $n=100$ items and $v_i={10}^9$, the maximum value is ${10}^{11}$, which overflows int. Use long long for the DP array whenever values or counts can multiply beyond $2\times {10}^9$.

Capacity vs exact sum

Two different problems:

• "Total weight $\le W$, maximize value" -> init dp[j] = 0 for all $j$, answer is *max_element(dp, dp+W+1) (or just dp[W] since it's non-decreasing for max-value).
• "Total weight $=W$ exactly" -> init dp[0] = 0, dp[j] = -INF for $j>0$. Only dp[W] is the answer.

Getting the initialization wrong silently produces incorrect results.

Weight = 0 items

If some $w_i=0$, the inner loop for (j = W; j >= 0; j--) processes every capacity and can be taken "for free." Handle $w_i=0$ items separately: just add their value unconditionally (for 0/1) or get infinite value (for unbounded -- likely a degenerate input).

Large $W$ with small $n$

If $W$ up to ${10}^9$ but $n\le 40$, the $O(n\cdot W)$ DP is far too slow. Use meet-in-the-middle: split items into two halves, enumerate all $2^{n/2}$ subsets for each half, sort one half, and binary search for the complement. Total: $O(2^{n/2}\cdot n)$.

Multiple test cases

If there are $T$ test cases, either re-declare dp each time (simpler, auto-zeroes), or fill(dp.begin(), dp.end(), 0) before each case. Forgetting to reset is a classic WA.

Debug checklist

1. Print the full dp[] array after processing each item.
2. Verify the loop direction matches the variant (0/1 vs unbounded).
3. Check that dp is long long if values can exceed $2\times {10}^9$.
4. Test with a single item: answer should be its value if it fits, 0 otherwise.
5. Test with capacity 0: answer should be 0.

Mental Traps

"0/1 knapsack and unbounded knapsack use the same loop direction."

NO! This is the #1 knapsack misconception. 0/1 iterates capacity backwards (j from W down to w[i]) to avoid using an item twice. Unbounded iterates forwards (j from w[i] up to W) to deliberately allow reuse. One character difference in the loop -- completely different semantics. The diagram below shows exactly how forward iteration lets a single item sneak in multiple times.

  FORWARD vs BACKWARD -- WHY DIRECTION MATTERS (Diagram B)

  Single item: X(w=3, v=5).  Capacity W=9.  Correct 0/1 answer: 5.

  ▸ BACKWARD (correct for 0/1):
    Start: dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
                 0  1  2  3  4  5  6  7  8  9

    j=9: dp[9] = max(dp[9], dp[6]+5) = max(0, 0+5) = 5
    j=8: dp[8] = max(dp[8], dp[5]+5) = max(0, 0+5) = 5
    j=7: dp[7] = max(dp[7], dp[4]+5) = max(0, 0+5) = 5
    j=6: dp[6] = max(dp[6], dp[3]+5) = max(0, 0+5) = 5
                              ^^^^^
                              still 0 -- not yet touched this pass!
    j=5: dp[5] = max(0, 0+5) = 5
    j=4: dp[4] = max(0, 0+5) = 5
    j=3: dp[3] = max(0, 0+5) = 5

    Result: [0, 0, 0, 5, 5, 5, 5, 5, 5, 5]
    dp[9] = 5  OK  Item X used exactly once.

  ▸ FORWARD (WRONG for 0/1 -- silently becomes unbounded):
    Start: dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

    j=3: dp[3] = max(dp[3], dp[0]+5) = 5        <- X used once
    j=4: dp[4] = max(dp[4], dp[1]+5) = 5
    j=5: dp[5] = max(dp[5], dp[2]+5) = 5
    j=6: dp[6] = max(dp[6], dp[3]+5) = max(0, 5+5) = 10
                              ^^^^^
                              ALREADY 5 -- X was counted again!  <- BUG
    j=7: dp[7] = max(dp[7], dp[4]+5) = max(0, 5+5) = 10
    j=8: dp[8] = max(dp[8], dp[5]+5) = max(0, 5+5) = 10
    j=9: dp[9] = max(dp[9], dp[6]+5) = max(0, 10+5) = 15
                              ^^^^^^
                              10 means X used twice, +5 = three times!

    Result: [0, 0, 0, 5, 5, 5, 10, 10, 10, 15]
    dp[9] = 15  X  Item X used 3 times! (9 / 3 = 3)

  +----------------------------------------------------------+
  |  BACKWARD: dp[j-w] is UNTOUCHED -> previous pass -> 0/1   |
  |  FORWARD:  dp[j-w] is UPDATED  -> current pass  -> reuse  |
  +----------------------------------------------------------+

"The DP value at capacity W is always the answer."

Not necessarily. If the problem asks "maximize value with total weight at most W," then yes, dp[W] works (the DP is non-decreasing for max-value). But if it asks for exactly capacity W -- e.g., "can you fill the knapsack to exactly W?" -- you need sentinel initialization (dp[0] = 0, dp[j] = -INF for j > 0) and only dp[W] is valid. Mixing these up produces silent wrong answers because the "at most" version initialized with zeros will always return something.

"I can always reduce to standard knapsack."

Bounded knapsack (at most $k_i$ copies of item $i$) tempts you to just add $k_i$ copies and run 0/1. This works logically but the item list explodes to $\sum k_i$ entries -- if $k_i$ can be ${10}^5$, you've just created ${10}^7$ items. Binary decomposition reduces each item to $O(\log k_i)$ virtual items, preserving correctness while keeping the problem tractable.

  BINARY DECOMPOSITION -- BOUNDED KNAPSACK (Diagram C)

  Item X(w=4, v=7) with k=13 copies.
  Naive: add 13 separate copies to item list -> O(k) items, too slow.

  Decompose 13 into powers of 2 + remainder:
    13 = 1 + 2 + 4 + 6
         ^   ^   ^   ^
         2⁰  2¹  2²  remainder (13 - 1 - 2 - 4 = 6)

  Create 4 virtual items instead of 13:
  +---------+-----------+-----------+----------------------------+
  | Virtual |  Weight   |   Value   | Represents                 |
  +---------+-----------+-----------+----------------------------+
  |   V1    |  1 x 4=4  |  1 x 7=7  | 1 copy of X                |
  |   V2    |  2 x 4=8  |  2 x 7=14 | 2 copies of X              |
  |   V3    |  4 x 4=16 |  4 x 7=28 | 4 copies of X              |
  |   V4    |  6 x 4=24 |  6 x 7=42 | 6 copies of X (remainder)  |
  +---------+-----------+-----------+----------------------------+

  Any count from 0 to 13 is reachable by a subset of {1, 2, 4, 6}:
    0  = {}            5  = {1,4}        10 = {4,6}
    1  = {1}           6  = {6}          11 = {1,4,6}
    2  = {2}           7  = {1,6}        12 = {2,4,6}
    3  = {1,2}         8  = {2,6}        13 = {1,2,4,6}
    4  = {4}           9  = {1,2,6}

  Run standard 0/1 knapsack on 4 virtual items -> O(log k) per item.
  Total items across all originals: O(n * log c_max) instead of O(n * c_max).

---

Common Mistakes

1. Wrong loop direction for 0/1 knapsack. Iterate capacity backward. A forward loop silently turns 0/1 into unbounded -- it compiles, runs, and gives wrong answers.
2. Integer overflow. With n=100 items and value 10^9, total value overflows int. Use long long for the dp array.
3. "At most W" vs "exactly W" confusion. Standard knapsack initializes all dp to 0. Exact-capacity variant initializes to -INF with only dp[0] = 0.
4. Forgetting the reachability check. In exact-capacity mode, adding value to an unreachable state (dp[c] == -INF) produces garbage.
5. Bounded knapsack treated as unbounded. When each item has count c_i, use binary grouping (split into powers of 2) to reduce to 0/1.
6. Sample passes, test 5 fails -- items get used multiple times. You wrote a left-to-right capacity loop that compiled and ran. You accidentally solved unbounded knapsack instead of 0/1. Loop direction encodes whether items are reusable; it is not a stylistic choice.

Debug Drills

Drill 1. 0/1 knapsack gives values higher than expected.

for (int i = 0; i < n; i++)
    for (int w = wt[i]; w <= W; w++)
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

What's wrong?

Inner loop goes left-to-right, so item i can be picked multiple times (this is unbounded knapsack). For 0/1 knapsack, reverse the inner loop: for (int w = W; w >= wt[i]; w--).

Drill 2. Subset sum returns true for sum 0 even when no items are selected.

vector<bool> dp(S + 1, false);
for (int i = 0; i < n; i++)
    for (int s = S; s >= a[i]; s--)
        dp[s] = dp[s] || dp[s - a[i]];
cout << (dp[S] ? "Yes" : "No");

What's wrong?

dp[0] is never set to true. The empty subset has sum 0, so dp[0] = true is the base case. Without it, no state is ever reachable.

Drill 3. Bounded knapsack (each item available $c_i$ times) with binary splitting gives WA.

// Binary splitting for item i with count c
for (int k = 1; k <= c; k *= 2) {
    // add item with weight k*w[i], value k*v[i]
    for (int j = W; j >= k * w[i]; j--)
        dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);
}

What's wrong?

The loop k *= 2 doesn't subtract used copies from c. After powers of 2, there's a leftover c - (2^t - 1) that must be added as a final group. Fix: track int rem = c; int k = 1; while (k <= rem) { /* process k */ rem -= k; k *= 2; } if (rem > 0) { /* process rem */ }.

---

Self-Test

• [ ] Implement 0/1 knapsack with backward iteration and explain why direction matters
• [ ] Implement unbounded knapsack with forward iteration
• [ ] Convert bounded knapsack (at most $k_i$ copies) to 0/1 using binary decomposition
• [ ] Explain the difference between "maximize value with capacity $\le W$" vs "exactly $W$"
• [ ] Recover which items were selected (not just the optimal value)
• [ ] State when knapsack DP is too slow and what alternatives exist (meet-in-the-middle, greedy)
• [ ] Handle the case where weights or values can be zero

Socratic Checkpoints

🤔 Checkpoint: In 0/1 knapsack with a 1D DP array, why must we iterate weights backwards (from W down to w[i])?

Think, then click

If we iterate forwards (j = w[i] to W), then when we compute dp[j] = max(dp[j], dp[j - w[i]] + v[i]), the value dp[j - w[i]] may have already been updated in the current iteration -- meaning item i was already "picked" at a smaller capacity. This effectively allows using item i multiple times (unbounded knapsack). Iterating backwards ensures dp[j - w[i]] still holds the value from the previous item's iteration, guaranteeing each item is used at most once.

🤔 Checkpoint: What changes when converting 0/1 knapsack to unbounded knapsack?

Think, then click

Exactly one change: iterate the capacity forwards instead of backwards. In 0/1 knapsack we go for (j = W; j >= w[i]; j--) to prevent reusing items. In unbounded knapsack, we want to reuse items, so we go for (j = w[i]; j <= W; j++). Now dp[j - w[i]] reflects the current iteration, allowing item i to be picked again. Alternatively, the unbounded variant can be written without the outer item loop: for (j = 0..W) try all items at each capacity.

Self-Test

Q1: Why can't we use the space-optimized 1D array for 0/1 knapsack if we iterate forward?

Answer

We'd use updated values from the current row, effectively counting items multiple times -- turning 0/1 knapsack into unbounded knapsack. Iterating backward ensures dp[j - w[i]] still holds the previous item's value, guaranteeing each item is used at most once.

Q2: Knapsack has n=40 items and W=10¹⁸. Standard DP is way too slow. What technique applies?

Answer

Meet-in-the-middle. Split items into two halves of ~20, enumerate all 2²⁰ subsets of each half, then combine. This runs in O(2^(n/2) * n) ~= 10⁶ * 20, which is feasible.

Q3: What's the difference between "maximize value with capacity <= W" and "maximize value with capacity exactly W" in terms of DP initialization?

Answer

For "<= W": initialize dp[j] = 0 for all j (any capacity is valid). For "exactly W": initialize dp[0] = 0 and dp[j] = -inf for j > 0 (only capacity 0 is reachable initially). The recurrence is the same; only the base case differs.

Q4: You have items where each item i can be used up to k_i times. How do you reduce this to 0/1 knapsack efficiently?

Answer

Binary decomposition. Represent k_i copies as items of size 1, 2, 4, ..., 2^p, remainder. This creates O(log k_i) virtual items per original item instead of k_i, reducing the total item count from Σk_i to Σlog(k_i).

Q5: In coin change (minimum coins to make amount X), why does greedy (largest denomination first) fail for denominations {1, 3, 4} and target 6?

Answer

Greedy picks 4+1+1 = 3 coins, but the optimal is 3+3 = 2 coins. The greedy choice of taking the largest coin forecloses the better combination. Coin change with arbitrary denominations requires DP because earlier choices constrain later ones.

---

Practice Problems

CF Rating	How Knapsack Appears
1200	Basic 0/1 knapsack, subset sum, coin change (unbounded)
1500	Bounded knapsack with binary splitting, knapsack with item groups
1800	Knapsack + modular constraints, tracking reachable sub-values
2100	Bitset-optimized knapsack, knapsack on trees, meet-in-the-middle for large $n$ small $W$

#	Problem	Source	Difficulty	Key Idea
1	Knapsack 1	AtCoder DP-D	1300	Classic 0/1 knapsack, direct application
2	Knapsack 2	AtCoder DP-E	1400	Large $W$, small values -- invert DP axis
3	Coin Combinations I	CSES	1300	Unbounded: count ways (order matters)
4	Coin Combinations II	CSES	1400	Unbounded: count ways (order doesn't matter)
5	Two Sets	CSES	1400	Subset sum: partition $1..n$ into equal halves
6	Baby Ehab Partitions Again	CF 1516C	1500	Subset sum + make partition impossible by removing one element
7	Buns	CF 106C	1500	Bounded knapsack with binary splitting
8	Zero Remainder Sum	CF 1433F	1600	Knapsack with modular constraint on rows
9	The Values You Can Make	CF 687C	1800	0/1 knapsack tracking reachable sub-values
10	Yet Another Knapsack Problem	CF 1132E	1900	Bounded knapsack with tight constraints

---

Designing Test Cases

Knapsack DP has a deceptive simplicity -- the recurrence is easy to write, easy to get subtly wrong. These tests catch the common mistakes.

Minimal cases:

• Single item: One item with weight w and value v, capacity W. If w <= W, answer is v. If w > W, answer is 0. This tests your base case.
• Item heavier than capacity: w[0] = 10, W = 5. Answer must be 0, not negative or garbage.

Edge cases:

• All items fit: Total weight of all items <= W. Answer is just the sum of all values. If you get less, your iteration direction is probably wrong (using items multiple times or skipping them).
• Zero value items: Items with v = 0. They should never change the answer -- catches bugs where you add items unconditionally.
• Zero weight items: Items with w = 0 and positive value. In 0/1 knapsack, each should be taken exactly once. In unbounded knapsack, this causes infinite value -- your code should handle it or the problem guarantees w >= 1.
• Capacity = 0: No items can be taken. Answer must be 0.
• Iteration direction: For 0/1 knapsack with 1D DP, iterate j from W down to w[i]. If you go forward, you'll use items multiple times (unbounded knapsack behavior). This is the #1 knapsack bug.

Stress test (run locally before submitting):

// Brute force: try all 2^n subsets.
mt19937 rng(42);
for (int iter = 0; iter < 50000; iter++) {
    int n = rng() % 15 + 1;  // small enough for 2^n
    int W = rng() % 50 + 1;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; i++) {
        w[i] = rng() % 20 + 1;
        v[i] = rng() % 100;
    }
    int dp_ans = knapsack_dp(n, W, w, v);
    int bf_ans = knapsack_brute(n, W, w, v);  // enumerate all 2^n subsets
    assert(dp_ans == bf_ans);
}

Keep n <= 15 so 2^n = 32768 subsets is instant. Run 50k+ iterations. This reliably catches forward-vs-backward iteration bugs and off-by-one capacity issues.

---

Further Reading

• cp-algorithms: 0-1 Knapsack -- formal treatment with proofs.
• AtCoder DP Contest -- Editorial -- tasks D and E cover knapsack variants with clean solutions.
• CF Blog: Knapsack optimization techniques -- bounded knapsack, bitset tricks, and advanced optimizations.
• CSES Problem Set -- Dynamic Programming -- coin and knapsack problems with test cases.
• Prerequisite: DP -- 1D Introduction
• Next: DP on Trees, DP -- Bitmask

---

Level-Up Chain

Four levels of knapsack mastery -- each level introduces a harder variant and a new optimization idea.

Level	Pattern	Problem / Description	Key Idea
1	Standard 0/1 knapsack	Knapsack 1 (AtCoder DP-D)	Classic "take or skip" DP. Iterate capacity backwards in 1D.
2	Unbounded knapsack	Coin Combinations I (CSES)	Each item can be used unlimited times. Iterate capacity forwards instead of backwards.
3	Bounded knapsack with binary grouping	Buns (CF 106C, 1500)	Each item has a count limit $c_i$. Split into $1,2,4,\dots$ copies to reduce to $O(nW\log c)$ 0/1 knapsack.
4	Knapsack + bitset optimization	Yet Another Knapsack Problem (CF 1132E, 1900)	Use bitset to represent reachable sums; shifts and ORs replace the inner loop, giving $O(nW/64)$.

---

How to Practice This

⏱️ Speed Drill -- 0/1 Knapsack (Space-Optimized)

Set a timer and implement the 1D-array space-optimized 0/1 knapsack (iterate items, iterate capacity backwards) from scratch. No references.

Attempt	Target	Notes
1st	< 8 min	Focus on correctness -- especially the reverse iteration order.
2nd	< 6 min	Eliminate pauses -- the outer/inner loop structure should be automatic.
3rd+	< 4 min	Competition-ready. Knapsack is a core DP pattern -- it must flow naturally.

🔀 Variation Drills

Once 0/1 knapsack is automatic, drill these essential variants:

Variation	Key change	Practice problem
Unbounded knapsack	Iterate capacity forwards (each item reusable)	CSES Coin Combinations I
Bounded knapsack (binary grouping)	Split count $c_i$ into powers of 2, reduce to 0/1	CF 106C - Buns

For each: implement, verify on the linked problem, then time yourself.

🧠 Practice Strategy

1. Week 1: Drill space-optimized 0/1 knapsack daily until you hit 4 min consistently.
2. Week 2: Alternate between unbounded and bounded variants -- one per day. Pay close attention to loop direction.
3. Week 3: Practice knapsack reconstruction (backtracking which items were chosen) and knapsack with multiple constraints (2D DP).
4. Ongoing: When you see "select subset, maximize/minimize value, subject to capacity" -- it's knapsack. Identify the variant (0/1, unbounded, bounded) and apply the right loop direction.

---

Recap

• 0/1 knapsack: iterate capacity backward. Unbounded: iterate forward. This is the single most important rule.
• Space-optimize from dp[i][w] to dp[w] by processing items in the outer loop, capacity in the inner loop.
• Exact capacity variant: initialize to -INF, only dp[0] = 0. Check reachability before using dp values.
• Bounded knapsack with item counts: use binary grouping to reduce to O(n * W * log c_max).

---

Cross-Links

• DP -- 1D Introduction -- foundation for the knapsack recurrence
• DP -- Bitmask -- when items interact and you need subset tracking
• DP vs Greedy Guide -- knapsack fails greedy; this guide explains why
• DP Practice Ladder -- graded problem set