You have n items. Item i has weight w[i] and value v[i]. The knapsack holds at most W. 0/1 means each item is used at most once: take it or leave it. Return the maximum value of a legal subset.
Greedy by density (v/w) fails. Classic counterexample: (w,v) = (2,3), (3,4) and W = 3. Density prefers the first item (value 3) and is stuck; taking only the second scores 4. You need DP.
// dp[c] after processing item i.
function knapsack(weights, values, cap) {
const dp = Array(cap + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
const wt = weights[i];
const val = values[i];
// Walk capacity downward so each item is used at most once.
for (let c = cap; c >= wt; c--) {
dp[c] = Math.max(dp[c], dp[c - wt] + val);
}
}
return dp[cap];
}Transition, item i with weight wt and value val:
- Skip: dp[i][c] = dp[i-1][c]
- Take (if c ≥ wt): dp[i][c] = dp[i-1][c - wt] + val
You want the max of those. Base: dp[0][*] = 0 (no items) and dp[*][0] = 0 (no capacity).
Rolling array: dp[c] stores the previous row. Iterate c from W down to wt. Then dp[c - wt] is still the *previous item's* value, because the current item has not yet written smaller capacities. Walk c upward and you accidentally reuse the item — that is unbounded knapsack, the next lesson.
Complexity is O(nW) time and O(W) extra memory after rolling. That is legal when W is a few thousand and n is a few hundred — the usual contest envelope. If W is 10⁹, this table does not exist; you need a different state (often 'best weight for a given value', or meet-in-the-middle when n ≤ 40).
Initialize with 0, not -∞, when leftover capacity is allowed (the usual statement). Use -∞ only if you must fill *exactly* W.
Checks 0/2