Pattern Reference
Knapsack DP
"0/1 knapsack, unbounded knapsack, bounded knapsack, subset sum, coin change II."
Loading...
Deep Dive Tutorial
Knapsack problems ask: given items with weights and values, pick a subset to maximize total value without exceeding capacity W. The brute force tries 2^n subsets. DP reduces this to O(n×W). The critical insight: whether each item can be used once (0/1) or multiple times (unbounded) changes the iteration direction.
The Direction Rule
key
The single most important rule:
- Iterate weight backwards (from W down to weight[i]): each item used AT MOST ONCE (0/1 knapsack). A capacity seen earlier in this pass hasn't yet included item i.
- Iterate weight forwards (from weight[i] up to W): each item used UNLIMITED TIMES (unbounded knapsack). The same item can be added multiple times because we look at dp[j-weight[i]] which may already contain item i.
This is the ONLY difference between the two templates.
- Iterate weight backwards (from W down to weight[i]): each item used AT MOST ONCE (0/1 knapsack). A capacity seen earlier in this pass hasn't yet included item i.
- Iterate weight forwards (from weight[i] up to W): each item used UNLIMITED TIMES (unbounded knapsack). The same item can be added multiple times because we look at dp[j-weight[i]] which may already contain item i.
This is the ONLY difference between the two templates.
0/1 Knapsack vs Unbounded Knapsack
// ======== 0/1 KNAPSACK ========
// Each item used at most once
// Iterate backwards to prevent reuse
function knapsack01(weights, values, W) {
const dp = new Array(W + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let j = W; j >= weights[i]; j--) { // ← BACKWARDS
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[W];
}
// ======== UNBOUNDED KNAPSACK ========
// Each item can be used unlimited times
// Iterate forwards to allow reuse
function unboundedKnapsack(weights, values, W) {
const dp = new Array(W + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let j = weights[i]; j <= W; j++) { // ← FORWARDS
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[W];
}
// ======== COUNT VARIANTS ========
// Replace max with + to count number of ways
// 0/1 count: backwards
function countSubsets(nums, target) {
const dp = new Array(target + 1).fill(0);
dp[0] = 1;
for (const n of nums)
for (let j = target; j >= n; j--) // backwards = each used once
dp[j] += dp[j - n];
return dp[target];
}
// Unbounded count (coin change II): forwards
function countWays(coins, amount) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const c of coins)
for (let j = c; j <= amount; j++) // forwards = each used multiple times
dp[j] += dp[j - c];
return dp[amount];
}Worked Problems
brain
Knapsack variant decision guide:
- Each item used ONCE → iterate capacity backwards (0/1 knapsack)
- Each item used UNLIMITED times → iterate capacity forwards (unbounded)
- Count COMBINATIONS → outer loop = items, inner loop = capacity
- Count PERMUTATIONS → outer loop = capacity, inner loop = items
- Multiple capacities → 2D dp (iterate all capacity dimensions backwards for 0/1)
- Minimize instead of maximize → same template, replace max with min
Recognition signals:
- "Subset sum / partition" → 0/1 with boolean dp or value dp
- "Coin change" → unbounded (coins reusable)
- "Coin change II (ways)" → unbounded count, combinations order
- "Bounded: each item limited k times" → binary splitting or deque optimization
- Each item used ONCE → iterate capacity backwards (0/1 knapsack)
- Each item used UNLIMITED times → iterate capacity forwards (unbounded)
- Count COMBINATIONS → outer loop = items, inner loop = capacity
- Count PERMUTATIONS → outer loop = capacity, inner loop = items
- Multiple capacities → 2D dp (iterate all capacity dimensions backwards for 0/1)
- Minimize instead of maximize → same template, replace max with min
Recognition signals:
- "Subset sum / partition" → 0/1 with boolean dp or value dp
- "Coin change" → unbounded (coins reusable)
- "Coin change II (ways)" → unbounded count, combinations order
- "Bounded: each item limited k times" → binary splitting or deque optimization