Knapsack Problem

Prerequisite: Introduction to Dynamic Programming.

Classic packing DP: choose items under a weight limit to maximize value. This lesson follows CP-Algorithms — Knapsack (motivated by USACO Charm Bracelet).

0-1 Knapsack

n distinct items, capacity W. Item i has weight wᵢ and value vᵢ. Each item is taken at most once. Maximize total value with total weight ≤ W.

State

fᵢⱼ = max value using only the first i items with capacity j.

For item i at capacity j:

• Skip: fᵢ₋₁,ⱼ
• Take (if j ≥ wᵢ): fᵢ₋₁,ⱼ₋wᵢ + vᵢ

fᵢⱼ = max(fᵢ₋₁,ⱼ,  fᵢ₋₁,ⱼ₋wᵢ + vᵢ)

1D optimization

Only the previous layer is needed:

fⱼ ← max(fⱼ, fⱼ₋wᵢ + vᵢ)

Loop j from W down to wᵢ so that fⱼ₋wᵢ still holds the (i−1)-layer value (each item once).

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

Time / memory: O(nW) / O(W).

Invariant while processing (i,j): for k > j, fₖ is already updated for item i; for k ≤ j (before the update), fₖ is still from layer i−1.

🧪 0-1 knapsack tiny instance

Complete Knapsack

Same as 0-1, except each item may be taken unlimited times.

Naive: try count k = 0,1,2,… → O(n²W). Better recurrence:

fᵢⱼ = max(fᵢ₋₁,ⱼ,  fᵢ,ⱼ₋wᵢ + vᵢ)

Because fᵢ,ⱼ₋wᵢ already includes extra copies of item i.

1D form is the same assignment, but loop j from wᵢ up to W:

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

Still O(nW). Using the ascending loop for 0-1 is wrong — it multiplies the item.

🧪 Complete knapsack on the same items

Interactive: loop direction matters

Multiple Knapsack

Item i may be taken at most kᵢ times.

Flatten to 0-1

Treat as kᵢ identical 0-1 items → time O(W · Σ kᵢ).

Binary grouping

Split count kᵢ into bundles of sizes 1,2,4,… plus a remainder so every total ≤ kᵢ is achievable. Then run 0-1 on the bundles → O(W · Σ log kᵢ).

index = 0;
for (int i = 1; i <= n; i++) {
  int c = 1, p, h, k;
  cin >> p >> h >> k; // weight, value, count
  while (k > c) {
    k -= c;
    list[++index].w = c * p;
    list[index].v = c * h;
    c *= 2;
  }
  list[++index].w = p * k;
  list[index].v = h * k;
}
// then 0-1 knapsack on list[1..index]

Monotone queue — O(nW)

Rewrite by residue classes mod wᵢ:

gₓ,ᵧ = fᵢ(x·wᵢ + y)
Gₓ,ᵧ = g'ₓ,ᵧ − vᵢ·x
gₓ,ᵧ ← max_{k=0..kᵢ} Gₓ₋ₖ,ᵧ  + vᵢ·x

For fixed y, a sliding-window maximum (monotone deque) over x processes all capacities in O(W) per item → total O(nW).

Mixed Knapsack

Some items 0-1, some unbounded, some bounded. Dispatch by type:

for each item:
  if 0-1:     decreasing-j update
  if complete: increasing-j update
  if multiple: binary-group then 0-1 (or monotone queue)

Check: 0-1 vs complete

Quiz

0-1 and complete knapsack

1 / 4

0-1 knapsack 1D loop must run j…

Pick an answer to see if you are right.

Check: multiple & mixed

Quiz

Multiple and mixed knapsack

1 / 4

Binary grouping reduces the kᵢ copies to…

Pick an answer to see if you are right.

Practice drills

Activity: 0-1 value

First line: n W. Next n lines: w v. Print max value (0-1).

Contest problems

From CP-Algorithms:

• AtCoder DP Contest — Knapsack 1
• AtCoder DP Contest — Knapsack 2
• LeetCode 494 — Target Sum
• LeetCode 416 — Partition Equal Subset Sum
• LeetCode 474 — Ones and Zeroes
• CSES Book Shop II (multiple / binary grouping)
• DMOJ Knapsack 3
• DMOJ Knapsack 4

Cheat sheet

Variant	Extra rule	1D loop
0-1	≤ 1 copy	j = W … w
Complete	unlimited	j = w … W
Multiple	≤ kᵢ	binary groups + 0-1, or monotone queue
Mixed	per-item type	dispatch matching update
Complexity	—	usually O(nW) (or O(W Σ log kᵢ) with binary split)