0/1 Knapsack
Maximize value of items in a knapsack with weight limit.
How it works
The 0/1 Knapsack problem asks: given n items each with a weight and a value, and a knapsack with maximum capacity W, choose a subset of items (each used at most once) that maximises total value without exceeding total weight.
The algorithm builds an (n+1) × (W+1) table where dp[i][j] stores the maximum value achievable using the first i items with a capacity of j.
Recurrence: - If weights[i-1] > j: dp[i][j] = dp[i-1][j] (item is too heavy — skip it) - Otherwise: dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j − weights[i-1]]) (skip or take)
Base case: dp[0][j] = 0 — no items means zero value.
The answer sits at dp[n][W]. To recover which items were selected, backtrack through the table: if dp[i][j] ≠ dp[i-1][j] then item i was included.
The "0/1" refers to the binary choice — each item is either taken (1) or left (0). The unbounded variant allows taking each item multiple times.
Complexity
Visualizer
Where it's used in the real world
Cloud computing — resource scheduler (AWS Batch, GKE)
Packing workloads onto available VM instancesSchedulers model each pending job as an item with a CPU/memory weight and a priority-based value, and each worker node as a knapsack with finite capacity. A 0/1 knapsack solve (or LP relaxation for large n) maximises throughput while respecting per-node resource limits.
Quantitative finance — portfolio construction
Selecting assets under budget or position-size constraintsPortfolio optimisers can model each asset as an item whose weight is its capital requirement and whose value is its risk-adjusted expected return. Knapsack DP finds the allocation that maximises expected return without exceeding capital or regulatory exposure limits.
Logistics — cargo loading optimisation
Maximising revenue-per-flight for air freight or shipping containersAirlines and freight companies must select which shipments to load given strict weight and volume limits. A knapsack formulation — with shipment revenue as value and shipment weight as weight — directly models this decision, and is used as a sub-problem in column-generation algorithms for larger fleet-scheduling problems.
Implementation
function knapsack(
weights: number[],
values: number[],
capacity: number
): number {
const n = weights.length;
const dp: number[][] = Array.from({ length: n + 1 }, () =>
Array(capacity + 1).fill(0)
);
for (let i = 1; i <= n; i++) {
for (let j = 0; j <= capacity; j++) {
if (weights[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(
dp[i - 1][j],
values[i - 1] + dp[i - 1][j - weights[i - 1]]
);
}
}
}
return dp[n][capacity];
}
// Usage
console.log(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8)); // 10