Knapsack Problems
The knapsack problem is a family of DP problems about selecting items subject to a capacity constraint. Understanding the three main variants — 0/1, unbounded, and fractional — and the subset sum variants built on top of them covers a huge swath of interview DP problems.
0/1 Knapsack — Each Item Used At Most Once
Given n items each with a weight and value, and a bag with capacity W, select items to maximize total value without exceeding the weight limit. Each item can be included at most once (0 = exclude, 1 = include).
State: dp[i][w] = maximum value using the first i items with weight capacity w Recurrence:
- If item i is too heavy: dp[i][w] = dp[i-1][w]
- Otherwise: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) Base cases: dp[0][w] = 0 for all w (no items = no value)
// 0/1 Knapsack — O(n·W) time, O(n·W) space
function knapsack01(weights, values, W) {
const n = weights.length;
// dp[i][w] = max value from first i items with capacity w
const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= W; w++) {
// Option 1: exclude item i
dp[i][w] = dp[i - 1][w];
// Option 2: include item i (if it fits)
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(
dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]
);
}
}
}
return dp[n][W];
}
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
console.log(knapsack01(weights, values, 8)); // 10 (items 0+2: weight=6, value=8? Let's see)
// Actually: items 1+2 (weight 3+4=7, value 4+5=9) or items 0+3 (2+5=7, 3+6=9)
// items 0+1+? — 2+3=5 < 8, value=7, can add item 2 (4>3 remaining) no...
// Best: items 1,2 weight=7 value=9, or 0,3 weight=7 value=91D Space Optimization for 0/1 Knapsack
Since dp[i][w] only depends on the previous row dp[i-1][...], we can compress the 2D table to a single 1D array.
Critical: iterate the weight dimension from right to left to prevent using item i more than once. Going right-to-left means when we compute dp[w], the value dp[w - weight[i]] still holds the i-1 version (not yet updated for item i).
// 0/1 Knapsack — O(n·W) time, O(W) space
function knapsack01Optimized(weights, values, W) {
const dp = new Array(W + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
// RIGHT TO LEFT — critical for 0/1 (each item used at most once)
for (let w = W; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[W];
}
console.log(knapsack01Optimized([2,3,4,5], [3,4,5,6], 8)); // 10Unbounded Knapsack — Items Can Repeat
Same setup as 0/1, but each item can be used any number of times.
State: dp[w] = maximum value achievable with capacity exactly w (or at most w) Recurrence: dp[w] = max over all items i where weight[i] ≤ w: dp[w - weight[i]] + value[i]
Because we allow reuse, iterate the weight dimension left to right — when dp[w - weight[i]] is updated with item i already included, that's fine, because item i can be used multiple times.
// Unbounded Knapsack — O(n·W) time, O(W) space
function knapsackUnbounded(weights, values, W) {
const dp = new Array(W + 1).fill(0);
for (let w = 1; w <= W; w++) {
for (let i = 0; i < weights.length; i++) {
if (weights[i] <= w) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
}
return dp[W];
}
// Coin Change is unbounded knapsack with value = 1 (count coins)
// Coin Change II (count ways) is also unbounded knapsack
function coinChangeWays(coins, amount) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1; // one way to make amount 0: use no coins
for (const coin of coins) {
for (let w = coin; w <= amount; w++) {
dp[w] += dp[w - coin]; // add number of ways that use this coin
}
}
return dp[amount];
}
console.log(coinChangeWays([1, 2, 5], 5)); // 4 ways: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1Fractional Knapsack — Greedy, Not DP
If you can take fractions of items (e.g., liquid, grain), the problem becomes trivially solvable with a greedy algorithm. Always take the item with the highest value-per-unit-weight ratio.
// Fractional Knapsack — O(n log n) greedy
function fractionalKnapsack(weights, values, W) {
const items = weights.map((w, i) => ({
weight: w,
value: values[i],
ratio: values[i] / w
}));
items.sort((a, b) => b.ratio - a.ratio); // highest ratio first
let totalValue = 0;
let remaining = W;
for (const item of items) {
if (remaining <= 0) break;
if (item.weight <= remaining) {
totalValue += item.value; // take whole item
remaining -= item.weight;
} else {
totalValue += item.ratio * remaining; // take fraction
remaining = 0;
}
}
return totalValue;
}
console.log(fractionalKnapsack([10, 20, 30], [60, 100, 120], 50));
// 240.0 (take all of item 0 and 1, take 2/3 of item 2: 60+100+80=240)Subset Sum
Given an array of integers, does any subset sum to exactly target T? This is 0/1 knapsack where value = weight and you're asking if dp[T] >= T.
State: dp[w] = true if some subset sums to exactly w Recurrence: dp[w] = dp[w] OR dp[w - nums[i]] Direction: right to left (0/1: each element used at most once)
// Subset Sum — O(n·T) time, O(T) space
function subsetSum(nums, target) {
const dp = new Array(target + 1).fill(false);
dp[0] = true; // empty subset sums to 0
for (const num of nums) {
for (let w = target; w >= num; w--) { // right to left (0/1)
dp[w] = dp[w] || dp[w - num];
}
}
return dp[target];
}
console.log(subsetSum([3, 1, 1, 2, 2, 1], 4)); // true (3+1 or 2+2 or 1+1+2)
console.log(subsetSum([1, 5, 11, 5], 11)); // true ([11] or [1,5,5])Partition Equal Subset Sum
Can you split an array into two subsets with equal sum? This is subset sum where the target is totalSum / 2. If totalSum is odd, answer is immediately false.
// Partition Equal Subset Sum — O(n · sum/2) time
function canPartition(nums) {
const total = nums.reduce((a, b) => a + b, 0);
// Odd total → can never split evenly
if (total % 2 !== 0) return false;
const target = total / 2;
const dp = new Array(target + 1).fill(false);
dp[0] = true;
for (const num of nums) {
for (let w = target; w >= num; w--) {
dp[w] = dp[w] || dp[w - num];
}
}
return dp[target];
}
console.log(canPartition([1, 5, 11, 5])); // true → {1,5,5} and {11}
console.log(canPartition([1, 2, 3, 5])); // falseTarget Sum — Count Ways
Assign + or − to each element such that the expression evaluates to target. Count the number of ways.
Transform: Let P = sum of elements with +, N = sum with −. Then P - N = target and P + N = totalSum. So P = (target + totalSum) / 2.
This reduces to counting subsets that sum to P — an unbounded-style count DP.
// Target Sum — O(n · sum) time, O(sum) space
function findTargetSumWays(nums, target) {
const total = nums.reduce((a, b) => a + b, 0);
// Must be same parity and reachable
if ((total + target) % 2 !== 0) return 0;
if (Math.abs(target) > total) return 0;
const t = (total + target) / 2;
// Count subsets summing to t
const dp = new Array(t + 1).fill(0);
dp[0] = 1; // one way to sum to 0: empty subset
for (const num of nums) {
for (let w = t; w >= num; w--) {
dp[w] += dp[w - num];
}
}
return dp[t];
}
console.log(findTargetSumWays([1, 1, 1, 1, 1], 3)); // 5
console.log(findTargetSumWays([1], 1)); // 1All Knapsack Variants at a Glance
Problem | Items | Objective | Inner Loop Direction | Time |
|---|---|---|---|---|
0/1 Knapsack | At most once | Max value | Right to left | O(n·W) |
Unbounded Knapsack | Unlimited | Max value | Left to right | O(n·W) |
Fractional Knapsack | Fractions OK | Max value | Greedy (sort) | O(n log n) |
Subset Sum | At most once | Exists? | Right to left | O(n·T) |
Partition Equal Subset | At most once | Equal halves? | Right to left | O(n·S/2) |
Coin Change (min) | Unlimited | Min coins | Left to right | O(n·W) |
Coin Change (count) | Unlimited | Count ways | Left to right | O(n·W) |
Target Sum | At most once | Count ways | Right to left | O(n·S) |
Choosing the Right Variant
"At most once" → 0/1 knapsack → right-to-left inner loop
"Any number of times" → unbounded knapsack → left-to-right inner loop
"Fraction allowed" → fractional knapsack → greedy, not DP
"Exists?" → boolean DP with OR
"Count ways?" → integer DP with addition
"Minimum count?" → integer DP with min
"Maximum value?" → integer DP with max