0/1 Knapsack
O(n·W)Pick a subset of items with weights and values so total weight stays within W and value is maximal. One 1-D array suffices: iterate weights DOWNWARDS so each item is used at most once; iterating upwards silently turns it into the unbounded knapsack (items reusable), which is the single most common knapsack bug. The same loop shape covers subset-sum (dp of booleans) and counting variants (dp of counts).
// use it on
CSES: Book Shop ↗
Prices are weights, pages are values, x is the capacity. Straight 0/1 knapsack: if you get double the expected pages, you iterated upwards.
// the code
// weights w[i], values v[i], capacity W
long long knapsack(vector<int>& w, vector<int>& v, int W) {
vector<long long> dp(W + 1, 0); // dp[c] = best value with capacity c
for (int i = 0; i < (int)w.size(); i++)
for (int c = W; c >= w[i]; c--) // downwards: each item once
dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
return dp[W];
}
// unbounded variant (unlimited copies): loop c upwards instead.// more classics