Knapsack¶

In one sentence

Knapsack DP answers "which items should I pick so they fit and are worth the most?" It does this by solving the question for every capacity from \(0\) to \(W\), one item at a time.

1. What problem does it solve?¶

Example — AtCoder EDU DP D · Knapsack 1

There are \(N\) items. Item \(i\) has weight \(w_i\) and value \(v_i\). Choose some items with total weight at most \(W\) so that the total value is as large as possible. Each item can be taken at most once.

Limits: \(N \le 100\), \(W \le 10^5\), \(v_i \le 10^9\).

Input        Output
3 8
3 30
4 50
5 60         90

Take items 1 and 3: weight \(3 + 5 = 8 \le 8\), value \(30 + 60 = 90\).

Why not greedy? "Best value per weight first" fails. With \(W = 4\) and items \((w, v) = (3, 5), (2, 3), (2, 3)\), greedy takes the first item (ratio \(1.67\)) and then nothing else fits: value \(5\). Taking the two small items gives \(6\).

Why not brute force? Each item is in or out, which gives \(2^N\) choices. For \(N = 100\) that is about \(10^{30}\).

2. The math¶

2.1 State¶

Decide items one at a time, and remember only what matters for the future: how much capacity is used.

\[ f_{i,j} = \text{the best total value using only the first } i \text{ items, with total weight at most } j . \]

The answer is \(f_{N,W}\). The base case is \(f_{0,j} = 0\) (no items, no value).

2.2 Transition¶

For item \(i\) there are only two choices:

\[ f_{i,j} = \max\Big(\underbrace{f_{i-1,\,j}}_{\text{skip item } i},\;\; \underbrace{f_{i-1,\,j-w_i} + v_i}_{\text{take item } i \text{ (only if } j \ge w_i)}\Big) \]

If we take item \(i\), it uses \(w_i\) of the capacity, so the first \(i - 1\) items must fit into \(j - w_i\), and we want the best value for that. That is \(f_{i-1,\,j-w_i}\) by definition.

2.3 Filling the table by hand¶

\(W = 5\), items \((w, v)\): \((2, 3)\), \((3, 4)\), \((4, 5)\).

\(f_{i,j}\)	\(2\)	\(3\)	\(4\)	\(5\)
\(i=0\) (no items)	0	0	0	0
\(i=1\): \((2,3)\)	3	3	3	3
\(i=2\): \((3,4)\)	3	4	4	7
\(i=3\): \((4,5)\)	3	4	5	7

Two cells, worked out:

\(f_{2,5} = \max(f_{1,5},\ f_{1,2} + 4) = \max(3,\ 3 + 4) = 7\): take item 2 on top of the best way to fill capacity \(2\).
\(f_{3,4} = \max(f_{2,4},\ f_{2,0} + 5) = \max(4,\ 5) = 5\): item 3 alone beats the old best.

The answer is \(f_{3,5} = 7\) (items 1 and 2).

2.4 From a 2D table to one array¶

Row \(i\) only reads row \(i - 1\). So keep one array dp[j] and overwrite it row by row. The catch is the loop direction.

dp[j] = max(dp[j], dp[j - w] + v) must read the old dp[j - w] (from row \(i - 1\)).

Going right to left (\(j = W \to w\)): dp[j - w] is to the left of j, so it has not been overwritten yet. It still holds row \(i - 1\). ✅ Each item is used at most once.
Going left to right: dp[j - w] was already updated in this pass, so it may already include item \(i\). The item gets used again.

See it happen with one item \((w, v) = (2, 3)\) and \(W = 5\), loop left to right:

step	`dp` after the step
start	`[0, 0, 0, 0, 0, 0]`
`j = 2`: `dp[0] + 3`	`[0, 0, 3, 0, 0, 0]`
`j = 3`: `dp[1] + 3`	`[0, 0, 3, 3, 0, 0]`
`j = 4`: `dp[2] + 3`	`[0, 0, 3, 3, 6, 0]` ← item used twice

That "bug" is exactly what unbounded knapsack wants, which is why the only difference between the two is the loop direction.

2.5 Cost¶

\(O(N \cdot W)\) time and \(O(W)\) memory. For Knapsack 1 that is \(100 \cdot 10^5 = 10^7\) updates.

3. Templates¶

These are the templates we use in class. Use them exactly as written.

Knapsack DP – Core Idea¶

Let dp[j] be the maximum total value we can obtain using a knapsack of capacity exactly j (or at most j – we'll use "at most" by initialising everything to 0).

We process items one by one. For each item with weight w and value v, we consider two choices:
- skip it – dp[j] stays unchanged,
- take it – we can add v to the best solution for capacity j-w.

So the basic transition is:

dp[j] = max(dp[j], dp[j-w] + v)

The only difference between the three problems is how many times we may take the same item.

1. 0/1 Knapsack – each item at most once¶

We must not use the same item more than once. If we update dp from small j to large j, we might reuse the same item multiple times in one pass (because dp[j-w] could already include the current item).
To prevent that, we iterate capacity from high to low (j = W … w).
Then dp[j-w] still comes from the previous item (not updated yet), so each item is considered at most once.

Two-array version (conceptual):
Keep prev (before processing current item) and cur (after).
For each item:

cur = prev.copy()
for j in range(w, W+1):
    cur[j] = max(prev[j], prev[j-w] + v)
prev = cur

The backward loop in the one-array version achieves exactly the same effect without extra memory.

One-array (final):

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

2. Unbounded Knapsack – unlimited copies¶

Now we can take the same item many times.
So we want dp[j-w] to already reflect the possibility of taking the current item.
Hence we iterate capacity from low to high (j = w … W).
That allows the item to be added repeatedly within the same pass.

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

Note that this is the only change from the 0/1 case.

3. Bounded Knapsack – each kind has a limited supply `c`¶

The simplest approach: expand every copy into a separate item, then run the 0/1 algorithm. If the total number of copies is M (given ≤ 1000), the complexity is O(M · W), which is fine for W ≤ 2000.

items = []
for each kind (w, v, c):
    repeat c times: items.append((w, v))

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

This is called the naïve (or expanded) method. It works because each physical copy is unique, exactly like the 0/1 problem.

Why the answer fits in a 64-bit integer¶

Values can be up to 10⁹ and we may take up to 1000 items (or unlimited up to capacity 2000), so the total can be 2·10¹² – hence Python’s int is fine; in other languages you’d use long long.

Complete template (generic)¶

You can adapt the inner loop based on the problem type:

import sys
input = sys.stdin.readline

def solve():
    n, W = map(int, input().split())
    dp = [0] * (W + 1)

    for _ in range(n):
        w, v = map(int, input().split())
        # For 0/1: use range(W, w-1, -1)
        # For unbounded: use range(w, W+1)
        for j in range(W, w-1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)

    print(dp[W])

For bounded, first build the expanded items list and then run the 0/1 loop exactly as above.

4. Worked solution — Knapsack 1¶

The generic template above solves it directly: 0/1 knapsack, so the inner loop goes from W down to w.

import sys
input = sys.stdin.readline

def solve():
    n, W = map(int, input().split())
    dp = [0] * (W + 1)

    for _ in range(n):
        w, v = map(int, input().split())
        # For 0/1: use range(W, w-1, -1)
        # For unbounded: use range(w, W+1)
        for j in range(W, w-1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)

    print(dp[W])

solve()

Trace the sample (\(W = 8\)):

after item	`dp[0..8]`
start	`0 0 0 0 0 0 0 0 0`
\((3, 30)\)	`0 0 0 30 30 30 30 30 30`
\((4, 50)\)	`0 0 0 30 50 50 50 80 80`
\((5, 60)\)	`0 0 0 30 50 60 60 80 90`

Speed in Python

\(10^7\) max calls take a few seconds in CPython. Submit with PyPy, as we do on Codeforces and AtCoder.

5. Recognising a knapsack¶

Ask these three questions:

Do I choose a subset of things?
Is there a budget, such as weight, cost, or time, that is a small integer?
Do I maximise or minimise a total, or count the ways?

If the answer to all three is yes, the budget becomes the j in dp[j].

variant	loop over `j`	example
each item at most once (0/1)	`W → w`	EDU DP D · Knapsack 1
unlimited copies	`w → W`	189A · Cut Ribbon
limited copies \(c\)	expand into \(c\) items, then `W → w`	Set 9 · C
\(W\) huge but values small	swap roles: `dp[value] = min weight`	EDU DP E · Knapsack 2

6. Common mistakes¶

Wrong loop direction

Left to right in 0/1 knapsack silently reuses items (see §2.4). Right to left in unbounded knapsack forbids reuse.

range(W, w, -1) instead of range(W, w - 1, -1)

That stops before j = w, so the item can never fill capacity exactly w.

dp[j] vs. dp[W] meaning

With everything initialised to 0, dp[j] means weight at most j, so the answer is dp[W]. If you initialise with -inf except dp[0] = 0, it means exactly j, and the answer is max(dp).

Using weight as the index when \(W\) is \(10^9\)

Then dp cannot be allocated. Look at the other small quantity (total value, count) and index by that, as in Knapsack 2.

7. Practice¶

Problem	Where	Idea
0/1 Knapsack	Set 9 · A	the template
Unbounded Knapsack	Set 9 · B	loop left to right
Bounded Knapsack	Set 9 · C	expand copies
EDU DP D · Knapsack 1	AtCoder	this page
EDU DP E · Knapsack 2	AtCoder	index by value, minimise weight
189A · Cut Ribbon	Codeforces · 1300	unbounded: maximise the number of pieces, `-inf` for "exactly"
577B · Modulo Sum	Codeforces · 1900	0/1 knapsack over remainders mod \(m\)

Credits & licenses

State definition and the "wrong loop direction" explanation (§2.1–2.4): adapted and translated from OI Wiki — Knapsack DP by hydingsy, Link-cute, Ir1d, greyqz, LuoshuiTianyi, odeinjul, xyf007, GoodCoder666, paigeman, shenshuaijie, oldoldtea and other OI Wiki contributors, licensed CC BY-SA 4.0. The worked tables are ours.
Section structure: follows USACO Guide — Knapsack DP by Nathan Chen, Michael Cao and Benjamin Qi, licensed CC BY-NC-SA 4.0.
Everything else (the greedy counterexample, recognition checklist, common mistakes) is ours. The templates in §3 are from our lessons.