Maximize value under a weight budget when each item is taken whole or skipped — a table over (items, capacity), O(n·W).
The 0/1 knapsack problem: you have a bag that holds at most W weight and a set of items, each with a weight and a value. Each item is taken whole or left behind — no fractions, no duplicates (that's the *0/1*). Maximize the total value packed. The fraction-allowed cousin yields to a simple greedy rule, but 0/1 does not — greed by value-per-weight can be badly wrong, so we need DP.
Define dp[i][w] = the best value using only the first `i` items within capacity w. For each item you face exactly one decision: skip it (keep the best from the previous i-1 items) or take it (add its value, but spend its weight). Pick whichever is larger.
dp[0][w] = 0 for every w — zero items hold zero value.i's weight > w, it can't fit: dp[i][w] = dp[i-1][w] (must skip).dp[i-1][w] vs take value[i] + dp[i-1][w - weight[i]].dp[n][W] — all items considered, full capacity available.i consumes weight[i] of the budget, so the rest of the value must come from earlier items within the *remaining* room w − weight[i] — exactly the subproblem dp[i-1][w - weight[i]].function knapsack(weight, value, W) {
const n = weight.length;
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++) {
dp[i][w] = dp[i - 1][w]; // skip item i
if (weight[i - 1] <= w) { // can it fit?
const take = value[i - 1] + dp[i - 1][w - weight[i - 1]];
if (take > dp[i][w]) dp[i][w] = take; // take if better
}
}
}
return dp[n][W];
}W, not just the number of items. A huge capacity written in few digits still blows up the table — which is why 0/1 knapsack is NP-hard despite this neat-looking DP.