These are the notes for Competitive Programming episode 33, part two of the dynamic programming section. Priya packs a trek backpack that can hold W kg; every item is either packed whole or left behind. An original problem, Trek Backpack, asks for the most valuable bag. Greedy by value per kg prints 30 instead of 48; trying all 2^n subsets is right but gets TLE at 40 items. The future only needs how many items we've decided on and how much weight we've used, so the state is dp[i][c], with two transitions: skip or take. One row is enough if c runs downwards; running it upwards lets an item be reused, which is exactly the unbounded knapsack. Replacing max with + gives the third variant: counting subsets with a given sum, mod 10^9 + 7. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
Priya is going on a three-day trek with one backpack that holds 10 kg. Tent, stove, first-aid kit, power bank: each has a weight and a usefulness score. She can't pack half a tent. Which items make the most useful bag? The word knapsack is just an old word for backpack, and this exact situation (whole items, one weight limit) is the most famous DP family in contests.
Problem J · Trek Backpack
(Written for this course, in the style of an AtCoder Beginner Contest problem.)
There are n items. Item i weighs wi kg and is worth vi. Choose some items, each at most once, with total weight at most W. Print the maximum total value.
- Input: n and W (1 ≤ n ≤ 100, 1 ≤ W ≤ 10^5), then n lines wi vi (1 ≤ wi ≤ W, 0 ≤ vi ≤ 10^9).
- Output: the maximum total value.
| Input | Output |
|---|---|
3 10 / 6 30 / 5 24 / 5 24 |
48 (the two 5 kg items) |
3 9 / 3 10 / 5 14 / 4 12 |
26 (5 kg + 4 kg) |
3 7 / 3 4 / 4 5 / 2 3 |
9 (3 kg + 4 kg) |
1 5 / 7 100 |
0 (nothing fits) |
Attempt 1: greedy by value per kg (wrong)
Sort by vi / wi, best first (the comparator cross-multiplies, v[a] * w[b] > v[b] * w[a], so there is no floating-point division), and pack whatever still fits.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, W;
cin >> n >> W;
vector<int> w(n);
vector<ll> v(n);
for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int a, int b) { // best value per kg first
return v[a] * w[b] > v[b] * w[a];
});
ll total = 0;
int left = W;
for (int i : id)
if (w[i] <= left) { left -= w[i]; total += v[i]; }
cout << total << "\n";
return 0;
}
Sample 1 prints 30 (expected 48). The 6 kg item has the best ratio (5 per kg), greedy grabs it, and then neither 5 kg item fits in the 4 kg left. Value per kg is the correct greedy only for the fractional knapsack, where items can be cut (rice, sugar). With whole items, one choice can block better ones.
Attempt 2: all 2^n subsets (Time Limit Exceeded)
Bit i of the mask says whether item i is packed (episode 17).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, W;
cin >> n >> W;
vector<int> w(n);
vector<ll> v(n);
for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
ll best = 0;
for (ll m = 0; m < (1LL << n); m++) { // bit i: take item i
ll weight = 0, value = 0;
for (int i = 0; i < n; i++)
if (m >> i & 1) { weight += w[i]; value += v[i]; }
if (weight <= W) best = max(best, value);
}
cout << best << "\n";
return 0;
}
Samples: 48, 26, 9, all correct. With 40 items it prints Time Limit Exceeded: 2^40 ≈ 1.1 · 10^12 subsets, and n can be 100.
The key question: what does the future need to know?
Standing at item i, two bags that both weigh 7 kg are interchangeable: whatever is left, there are 3 kg of space either way. So the future only needs how many items have been decided and how much weight is used.
State: dp[i][c] = the best value using only the first i items, with total weight at most c.
Transitions for item i (weight wi, value vi):
| Choice | Value |
|---|---|
| skip item i | dp[i−1][c] |
| take item i (if c ≥ wi) | dp[i−1][c − wi] + vi |
dp[i][c] = max of the two. Base: dp[0][c] = 0 for every c (no items, no value). Answer: dp[n][W]. There are (n + 1)(W + 1) ≈ 10^7 states, O(1) work each.
The table on sample 3
W = 7, items (3 kg, 4), (4 kg, 5), (2 kg, 3):
| weight ≤ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| no items | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| + (3 kg, 4) | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 |
| + (4 kg, 5) | 0 | 0 | 0 | 4 | 5 | 5 | 5 | 9 |
| + (2 kg, 3) | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 |
For example dp[2][7] = max(dp[1][7], dp[1][3] + 5) = max(4, 9) = 9, and dp[3][5] = max(dp[2][5], dp[2][3] + 3) = max(5, 7) = 7.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, W;
cin >> n >> W;
vector<int> w(n);
vector<ll> v(n);
for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
// dp[i][c] = best value using the first i items, weight <= c
vector<vector<ll>> dp(n + 1, vector<ll>(W + 1, 0));
for (int i = 1; i <= n; i++)
for (int c = 0; c <= W; c++) {
dp[i][c] = dp[i - 1][c]; // skip item i
if (c >= w[i - 1])
dp[i][c] = max(dp[i][c], dp[i - 1][c - w[i - 1]] + v[i - 1]); // take it
}
cout << dp[n][W] << "\n";
return 0;
}
Sample 1 prints 48. It works, but the full table at n = 100, W = 10^5 is 101 × 100001 long longs ≈ 80 MB.
One row is enough, if c runs downwards
Row i only reads row i − 1. Keep one row dp[c] and update it in place for each item:
dp[c] = max(dp[c], dp[c − wi] + vi)
The value read at dp[c − wi] must still be the old value (item i not used yet). If c runs from W down to wi, every smaller cell is still old when it is read. Memory drops from 80 MB to under 1 MB.
The accepted solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> w(n);
vector<ll> v(n);
for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
vector<ll> dp(W + 1, 0); // dp[c] = best value, weight <= c
for (int i = 0; i < n; i++)
for (int c = W; c >= w[i]; c--) // DOWN: each item once
dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
cout << dp[W] << "\n";
return 0;
}
| Input | Output |
|---|---|
| sample 1 | 48 |
| sample 2 | 26 |
| sample 3 | 9 |
1 5 / 7 100 (too heavy) |
0 |
| the 40-item test that timed out | 993 (instant) |
The worst case, built inside main (n = 100, W = 10^5, item i weighs 1000 + 37i and is worth 10^9 − i):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 100, W = 100000; // worst case, built here
vector<int> w(n);
vector<ll> v(n);
for (int i = 0; i < n; i++) { w[i] = 1000 + 37 * i; v[i] = 1000000000 - i; }
vector<ll> dp(W + 1, 0); // dp[c] = best value, weight <= c
for (int i = 0; i < n; i++)
for (int c = W; c >= w[i]; c--) // DOWN: each item once
dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
cout << dp[W] << "\n";
return 0;
}
Output: 50999998725. Fifty-one items fit (1000·51 + 37·1275 = 98175 kg), worth almost 5.1 · 10^10, far past an int, and the 10^7-step loop runs in a blink.
A stress test
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll brute(vector<int>& w, vector<ll>& v, int W) {
int n = w.size();
ll best = 0;
for (int m = 0; m < (1 << n); m++) {
ll wt = 0, val = 0;
for (int i = 0; i < n; i++) if (m >> i & 1) { wt += w[i]; val += v[i]; }
if (wt <= W) best = max(best, val);
}
return best;
}
ll fast(vector<int>& w, vector<ll>& v, int W) {
vector<ll> dp(W + 1, 0);
for (int i = 0; i < (int)w.size(); i++)
for (int c = W; c >= w[i]; c--) dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
return dp[W];
}
int main() {
mt19937 rng(33);
for (int t = 1; t <= 1000; t++) {
int n = rng() % 12 + 1, W = rng() % 50 + 1;
vector<int> w(n);
vector<ll> v(n);
for (int i = 0; i < n; i++) { w[i] = rng() % 20 + 1; v[i] = rng() % 100; }
if (brute(w, v, W) != fast(w, v, W)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 1000 tests passed";
}
Output: all 1000 tests passed.
Variant 2: the unbounded knapsack
Write the one-row loop with c going up and run sample 2:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> w(n);
vector<ll> v(n);
for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
vector<ll> dp(W + 1, 0); // dp[c] = best value, weight <= c
for (int i = 0; i < n; i++)
for (int c = w[i]; c <= W; c++) // up?
dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
cout << dp[W] << "\n";
return 0;
}
Output: 30 (expected 26): three copies of the 3 kg item worth 10. Going up, dp[c − wi] has already been updated for this same item, so the item is packed again and again.
That "bug" is the correct answer to a different problem: unlimited copies of each item (coins of each value, bricks, packets). This is called the unbounded knapsack.
| Loop direction | Meaning |
|---|---|
| c from W down to wi | each item at most once (0/1 knapsack) |
| c from wi up to W | unlimited copies (unbounded knapsack) |
Same state, same transition; only the order of one loop changes the meaning.
Variant 3: counting ways (mod 10^9 + 7)
n coins, each used at most once. How many subsets sum to exactly S? Coins 1 2 3 4 and S = 5: {1, 4} and {2, 3}, so 2.
- max(skip, take) becomes skip + take.
- Base: ways[0] = 1 (the empty subset).
- Counts explode (100 coins of value 1, S = 50: C(100, 50) ≈ 10^29), so print them mod 10^9 + 7 (episode 21).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
int main() {
int n, S;
cin >> n >> S;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<ll> ways(S + 1, 0); // ways[s] = subsets with sum s
ways[0] = 1; // the empty subset
for (int x : a)
for (int s = S; s >= x; s--) // down: each coin once
ways[s] = (ways[s] + ways[s - x]) % MOD; // skip + take
cout << ways[S] << "\n";
return 0;
}
| Input | Output |
|---|---|
4 5 / 1 2 3 4 |
2 |
| 100 coins of value 1, S = 50 | 538992043 (= C(100, 50) mod 10^9 + 7) |
Complexity vs the constraints
| Approach | Time | Memory | Verdict |
|---|---|---|---|
| all subsets | O(2^n · n) | O(n) | TLE at n = 40 |
| greedy by ratio | O(n log n) | O(n) | wrong (30 vs 48) |
| dp[i][c] table | O(n · W) ≈ 10^7 | O(n · W) ≈ 80 MB | accepted, but heavy |
| one row, c down | O(n · W) ≈ 10^7 | O(W) < 1 MB | accepted |
Common mistakes (and the real outputs)
Bug 1: the upward loop in a 0/1 knapsack
Shown above: sample 2 prints 30 instead of 26 because an item is reused. In a 0/1 knapsack, c must go down.
Bug 2: "exactly c" read as "at most c"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> w(n);
vector<ll> v(n);
for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
vector<ll> dp(W + 1, LLONG_MIN / 2); // weight exactly c?
dp[0] = 0;
for (int i = 0; i < n; i++)
for (int c = W; c >= w[i]; c--) // DOWN: each item once
dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
cout << dp[W] << "\n";
return 0;
}
On the too-heavy edge case it prints -4611686018427387904. With every cell except dp[0] set to −∞, dp[c] means "weight exactly c"; no subset weighs exactly 5, so the cell is still −∞. Either start every cell at 0 (meaning "at most c"), or keep exact weights and print the max over all c.
Summary table
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| greedy by value per kg | 30 instead of 48 |
whole items can't be split | DP over (i, c) |
for (c = w[i]; c <= W; c++) in 0/1 |
30 instead of 26 |
the item is reused | c from W down to wi |
dp(W + 1, LLONG_MIN / 2), print dp[W] |
-4611686018427387904 |
weight exactly W unreachable | start at 0, or max over c |
| full 2D table at tight memory limits | 80 MB, may get MLE | keeps every row | one row |
int values |
overflow past 2.1 · 10^9 | the sum of values is up to 10^11 | long long |
Mini project
Write a "packing assistant": read items and a capacity, solve the 0/1 knapsack with the one-row DP, then reconstruct the chosen items (keep the full 2D table, or a bool take[i][c] table, and walk back from dp[n][W]: if dp[i][c] ≠ dp[i−1][c], item i was taken, so c −= wi). Print the packed items and their total weight. Add a flag that switches to unlimited copies (the upward loop), and compare both answers on the samples.
Practice
-
Capacity up to 10^9, but every value is at most 1000 (n ≤ 100).
Answer
n · W is now 10^11: too big. Swap the roles: minW[x] = the smallest weight that reaches total value exactly x (x ≤ 100 · 1000 = 10^5), with minW[0] = 0, others +∞, and the same downward loop over x. The answer is the largest x with minW[x] ≤ W. O(n · Σv) = 10^7. On sample 1 it also prints <b>48</b>. -
Print which items to pack for sample 1.
Answer
Walk back from dp[3][10] = 48: item 3 was taken (dp[3][10] ≠ dp[2][10]), then item 2. Items <b>2 and 3</b>, 10 kg, value 48. -
Count the ordered ways to pay S with unlimited coins (order matters: 2+3 and 3+2 are different).
Answer
Put the sum loop outside and the coin loop inside: for s = 1 … S, for each coin c ≤ s, ways[s] += ways[s − c]. Coins {2, 3}, S = 7: <b>3</b> ordered ways (2+2+3, 2+3+2, 3+2+2), but only <b>1</b> unordered way (coins outside, s going up). -
Two backpacks, capacities A and B, each item in at most one bag.
Answer
State dp[a][b] = best value with a kg used in bag 1 and b kg in bag 2; for each item, loop a and b downwards and try: skip, put in bag 1, put in bag 2. O(n · A · B). Sample 1 items with A = 5, B = 6: <b>54</b> (a 5 kg item in bag 1, the 6 kg item in bag 2).
Quick quiz
Coins of value 2 and 3, unlimited. To count the ways to make S (order not counted), with the coin loop outside, which way should s go?
A) s from S down to x · B) s from x up to S · C) either works · D) neither works
Answer
B. Going up lets ways[s − x] already include coin x, so the same coin can be used again, which is what "unlimited" means.
Interview questions
- 0/1 vs unbounded vs fractional knapsack? 0/1: each item once (DP, c down). Unbounded: unlimited copies (DP, c up). Fractional: items can be cut (greedy by value per weight is optimal).
- Why is the 0/1 knapsack O(n · W) not polynomial? W is a number in the input, written in about log W bits, so O(n · W) is exponential in the input size. It's called pseudo-polynomial.
- How do you save memory in a knapsack DP? Each row only reads the previous row, so keep one row and choose the loop direction carefully.
- How do you reconstruct the chosen items? Keep the full table (or a choice table) and walk back from dp[n][W].
- What changes when you count instead of optimise? max becomes +, the base becomes ways[0] = 1, and you work modulo a prime.
- When would you index the DP by value instead of weight? When W is huge but the total value is small.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Knapsack | Choose items under a capacity to maximise value | Trek Backpack |
| 0/1 knapsack | Each item taken at most once | c loop goes down |
| Unbounded knapsack | Unlimited copies of each item | c loop goes up |
| Fractional knapsack | Items can be cut; greedy by ratio works | rice, sugar |
| State | What the future needs to know | (items decided i, capacity c) |
| Transition | How a state is built from others | skip / take |
| Base case | The starting values | dp[0][c] = 0, ways[0] = 1 |
| Rolling array (one row) | Reusing one row instead of a full table | vector<ll> dp(W + 1) |
| Pseudo-polynomial | Polynomial in the value W, not in its digit count | O(n · W) |
| Subset sum count | Number of subsets with a given sum | coins 1 2 3 4, S = 5 → 2 |
| Modulo 10^9 + 7 | Keeping huge counts small with a prime | 538992043 |
| Greedy | Take the locally best choice | best value per kg first |
| Stress test | Fast vs brute force on random small tests | all 1000 tests passed |
| −∞ sentinel | A value meaning "impossible" | LLONG_MIN / 2 |
Summary
- Whole items break greedy by ratio (
30vs48); all 2^n subsets TLE at n = 40. - State dp[i][c]: items decided, capacity used. Transitions: skip or take. Base: 0. Answer: dp[n][W]. O(n · W).
- One row: c down = each item once (0/1); c up = unlimited copies (unbounded).
- Counting: max → +, ways[0] = 1, mod 10^9 + 7.
- Real bugs: the upward loop (
30vs26), the exact-weight trap (-4611686018427387904).
Solutions in C++, Java and Python
Problem J · Trek Backpack
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> w(n);
vector<ll> v(n);
for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
vector<ll> dp(W + 1, 0); // dp[c] = best value, weight <= c
for (int i = 0; i < n; i++)
for (int c = W; c >= w[i]; c--) // DOWN: each item once
dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
cout << dp[W] << "\n";
return 0;
}
Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken(); int n = (int) in.nval;
in.nextToken(); int W = (int) in.nval;
long[] dp = new long[W + 1]; // dp[c] = best value, weight <= c
for (int i = 0; i < n; i++) {
in.nextToken(); int w = (int) in.nval;
in.nextToken(); long v = (long) in.nval;
for (int c = W; c >= w; c--) // down: each item once
dp[c] = Math.max(dp[c], dp[c - w] + v);
}
System.out.println(dp[W]);
}
}
Python (fine for the samples; for n · W = 10^7 in Python, use NumPy or C++)
import sys
def main():
data = sys.stdin.buffer.read().split()
n, W = int(data[0]), int(data[1])
dp = [0] * (W + 1) # dp[c] = best value, weight <= c
for i in range(n):
w, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
for c in range(W, w - 1, -1): # down: each item once
if dp[c - w] + v > dp[c]:
dp[c] = dp[c - w] + v
print(dp[W])
main()
Next episode: DP 3: DP on subsequences and strings (LCS and edit distance).