2Brute2Best
🔥0

DP — Knapsack Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

Items with weights; decide for each item whether to take it. dp[capacity] stores the best you can do with that much room.

4 sub-patterns · 14 questions

Remember this · DP — Knapsack
Trigger
Pick a subset to hit a target sum / capacity, partition into two groups, count the ways to reach an amount.
Think
Is this "choose some items so their total is X"?
Key question
Can each item be used once (loop capacity backwards) or many times (loop forwards)?
A

What is this pattern?

Knapsack: you have items (each with a weight, and maybe a value) and a capacity or target. For each item you decide to take it or not. The state is (items considered so far, capacity used):

  • dp[i][c] = the best value using only the first i items with capacity c.
  • Skip item i: dp[i − 1][c]. Take it: dp[i − 1][c − w] + v (if it fits).
  • dp[i][c] = max(skip, take).

Row i reads only row i − 1, so the table shrinks to one row dp[c]. Then the direction of the capacity loop is the whole lesson:

  • 0/1 (each item once): c goes high → low, so dp[c − w] is still the old row (item not used yet).
  • Unbounded (items repeat): c goes low → high, so dp[c − w] may already include this item — that's exactly the repeat we want.

Change the combine step and the same table answers other questions: || for "is it reachable", + for "how many ways", min for "fewest items".

Packing a bag for a trip with a weight limit. For each thing on the bed you ask one question: pack it or leave it? Your notebook has one line per weight limit (1 kg, 2 kg, …) holding the best bag found so far for that limit, and each new item updates the lines from the heaviest limit down, so nothing gets packed twice.

B

See it move

Purple = the cells the rule reads (skip = above, take = above and w to the left). Green = taking the item won.

0/1 knapsack: table, then one roww = [1, 3, 4], v = [15, 20, 30], W = 4step 1/25
dp[i][c]: rows = items used, columns = capacity
0
1
2
3
4
0
0
0
0
0
0
1
2
3
w/v
0
1
2
1/15
3/20
4/30
Row 0 = no items

dp[i][c] = the best value using only the first i items with capacity c. Row 0 has no items, so every value is 0.

Purple = the cell being read. Orange = a value that already contains the item, so the item is used again.

Loop direction decides reuseone item: weight 2, value 3; W = 6step 1/12
0/1: high → low
0
1
2
3
4
5
6
0
0
0
0
0
0
0
unbounded: low → high
0
1
2
3
4
5
6
0
0
0
0
0
0
0
Item
weight
2
value
3
Same line, two directions

One item (weight 2, value 3). Both rows run dp[c] = max(dp[c], dp[c − 2] + 3); only the order of c differs.

C

How do I recognise it?

  • "Choose a subset of items so that the total weight / sum is ≤ W or exactly T" and maximise the value or check it's possible.

  • "Partition the array into two groups with equal sum / the smallest difference" (→ one group's sum near total / 2).

  • "Number of ways to reach an amount / target" with coins or numbers.

  • "Fewest coins / items to make an amount", items usable many times.

  • Assign + or − to each number to reach a target (→ two groups → subset sum).

  • Small sums or capacities (≤ ~10⁴) but too many items for 2ᴺ.

Looks like DP — Knapsack, but isn't

Fractional knapsack (you may take part of an item)
→ Greedy

When items can be cut, sort by value per kg and take the best first. Only whole items need DP — greedy by ratio fails there.

List every subset / combination that hits the target
→ Backtracking

Knapsack DP counts or optimises; listing all answers needs generating them. Combination Sum is backtracking, Coin Change II is knapsack.

Huge target (10⁹) with few items (≤ 20–40)
→ Bitmask / meet in the middle

The table has one cell per capacity, so a huge capacity makes it too big. With few items, enumerate subsets instead.

Contiguous subarray with the best sum
→ DP — Kadane

Knapsack picks any items in any order; a subarray must be contiguous.

D

How would I discover it from scratch?

Don't memorise “use dp — knapsack”. Ask these questions in order — the pattern falls out.

Recurse on items: for item i, either skip it or take it (if it fits), then go to i + 1. Every item doubles the calls → O(2^N).

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

0/1 knapsack

3 questions

Each item is taken at most once. dp[c] = max(dp[c], dp[c − w] + v) with c from high to low.

02

Count ways

3 questions

Same 0/1 table, but cells hold counts and the combine step is +: the subsets that skip the item plus the subsets that take it.

03

Unbounded

4 questions

Items can be used any number of times. The capacity loop goes low → high so a cell can build on itself.

04

Partition into groups

4 questions

Split the items into groups. For two groups, fixing one group's sum fixes the other's, so it becomes subset sum up to total / 2. For k groups, the state is the set of items used (bitmask).

F

Don't mix these up

0/1 knapsack vs Unbounded knapsack

Same line of code, opposite loop direction. High → low = each item once; low → high = items repeat. Check the statement for "unlimited" / "infinite supply".

Coin Change II (combinations) vs Combination Sum IV (orders)

Both count, both unbounded. Coins in the outer loop → combinations. Amount in the outer loop → orders. On amount 4 with [1, 2, 3]: 4 combinations vs 7 orders.

Knapsack DP vs Backtracking (Combination Sum)

Asked for a number (count, max, min, yes/no)? Knapsack. Asked for the list of combinations? Backtracking.

Two-group partition vs k-group partition

Two groups → one subset sum to total / 2, a 1D table. k groups → finding one group at a time can pick the wrong group; track which items are used (bitmask DP) or backtrack.

G

Code templates (C++)

0/1 knapsack (one row)

Capacity loop high → low, stopping at w. Swap max for || (subset sum) or keep two capacities (Ones and Zeroes) — the direction rule stays.

zero-one-template.cpp
// 0/1 knapsack in one row: dp[c] = best value with capacity c.
// c goes HIGH -> LOW so dp[c - w] still belongs to the previous items (each item once).
int knapsack01(int W, const vector<int>& wt, const vector<int>& val) {
    vector<int> dp(W + 1, 0);
    for (size_t i = 0; i < wt.size(); i++)
        for (int c = W; c >= wt[i]; c--)
            dp[c] = max(dp[c], dp[c - wt[i]] + val[i]);   // skip vs take
    return dp[W];
}

Count ways (0/1)

dp[0] = 1 (the empty subset), then dp[s] += dp[s − x]. Apply the problem's modulo inside the loop. Target Sum first turns ± signs into a subset sum.

count-ways-template.cpp
// Count subsets with sum = target: same 0/1 row, but add counts.
// dp[s] = number of subsets of the items so far with sum s.
int countSubsets(const vector<int>& a, int target) {
    const int MOD = 1e9 + 7;
    vector<long long> dp(target + 1, 0);
    dp[0] = 1;                                     // the empty subset
    for (int x : a)
        for (int s = target; s >= x; s--)          // high -> low: each item once
            dp[s] = (dp[s] + dp[s - x]) % MOD;     // without x + with x
    return (int)dp[target];
}

Unbounded knapsack

Capacity loop low → high. For min coins start with "infinity" and use min(dp[a], dp[a − c] + 1). For counting, the outer loop decides combinations vs orders.

unbounded-template.cpp
// Unbounded: items can repeat, so the amount goes LOW -> HIGH
// (dp[a - c] may already use coin c, which lets it be used again).

// Fewest coins to make the amount (-1 if impossible).
int minCoins(const vector<int>& coins, int amount) {
    const int INF = amount + 1;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int c : coins)
        for (int a = c; a <= amount; a++)
            dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[amount] >= INF ? -1 : dp[amount];
}

// Count ways. Coins outer -> combinations; amount outer -> ordered sequences.
long long countCombinations(const vector<int>& coins, int amount) {
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins)
        for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
    return dp[amount];
}

Partition (subset sum near total / 2)

Mark every reachable sum up to total / 2, then take the largest reachable s: difference = total − 2s. Equal partition = s reaches exactly total / 2.

partition-template.cpp
// Two groups: mark every reachable subset sum up to total / 2 (0/1, high -> low).
// The other group gets total - s, so the difference is total - 2s.
int minPartitionDiff(const vector<int>& a) {
    int total = 0;
    for (int x : a) total += x;
    int half = total / 2;
    vector<bool> can(half + 1, false);
    can[0] = true;
    for (int x : a)
        for (int s = half; s >= x; s--)
            if (can[s - x]) can[s] = true;
    for (int s = half; s >= 0; s--)
        if (can[s]) return total - 2 * s;          // largest reachable s <= total / 2
    return total;
}
// Equal split: total must be even and can[total / 2] must be true.
Next
Start with 0/1 knapsack