Knapsack
The standard capacity-based DP pattern, with the loop directions and state choices that distinguish 0/1 from unbounded use.
Knapsack
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Knapsack is the template DP for resource allocation. The items change from problem to problem, but the state shape is stable: after considering some objects, what is the best value achievable with a given amount of capacity?
When to Use It
Use knapsack-style DP when:
choices consume some bounded resource,
items can be taken zero, one, or many times,
the resource limit is small enough for pseudo-polynomial DP.
Core Idea
Let \(\texttt{dp[w]}\) be the best value achievable with total weight exactly or at most \(w\). Each item updates this array by either using the item or skipping it.
Key Insight
The direction of the capacity loop is the entire difference between 0/1 and unbounded knapsack:
descending loop: each item used at most once,
ascending loop: the same item may contribute again in the same phase.
Operations / Main Technique
choose the state meaning carefully,
initialize impossible states correctly,
update by item transitions,
compress the first dimension when only the previous item layer is needed.
Worked example.
In 0/1 knapsack, if an item has weight \(3\) and value \(7\), then every capacity \(w \ge 3\) can try the transition \[ dp[w] = \max(dp[w], dp[w - 3] + 7), \] but only from the previous-item layer, which is why the loop goes backward.
Correctness Intuition
Every state represents the best answer among all valid subsets respecting the processed prefix of items. The transition simply partitions those subsets into two groups: ones that do not use the current item and ones that do.
Complexity Analysis
With capacity \(W\) and \(n\) items, the standard implementation is \(O(nW)\) time and \(O(W)\) memory after compression.
Implementation
The code includes:
0/1 knapsack,
unbounded knapsack.
Those two loop directions are the main thing to remember.
Common Pitfalls
Using the wrong loop direction.
Initializing impossible states as zero when they should be negative infinity.
Forcing knapsack on constraints where \(W\) is too large and another state definition is needed.
Variants / Extensions
Bounded knapsack.
Value-based knapsack.
Multiple constraints or grouped items.
Practice Problems
Standard 0/1 knapsack.
Unbounded coin change or resource allocation.
Value-based DP when weights are too large.
References
Code
Contest-ready reference implementation for the idea explained above.
long long knapsack_01(const vector<int>& weight, const vector<long long>& value, int capacity) {
vector<long long> dp(capacity + 1, 0);
for (int i = 0; i < (int)weight.size(); ++i) {
for (int w = capacity; w >= weight[i]; --w) {
dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
}
}
return *max_element(dp.begin(), dp.end());
}
long long knapsack_unbounded(const vector<int>& weight, const vector<long long>& value, int capacity) {
vector<long long> dp(capacity + 1, 0);
for (int i = 0; i < (int)weight.size(); ++i) {
for (int w = weight[i]; w <= capacity; ++w) {
dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
}
}
return *max_element(dp.begin(), dp.end());
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.