You're packing a knapsack that can carry a total weight of cap. There are n candidate items, where item i weighs weights[i] and is worth values[i].
Choose a subset of the items so the combined weight is at most cap and the combined value is as large as possible. Each item may be used at most once — you either pack it whole or leave it behind, there's no taking a fraction of an item and no taking the same item twice.
Return the maximum total value achievable.
Example
Take the items weighing 1, 4, and 5 (total weight 10, right at capacity) for value 1 + 5 + 7 = 13 — no other subset beats it.
Constraints
- 0 <= cap <= 10^4
- 0 <= weights.length == values.length <= 200
- 1 <= weights[i] <= 10^4
- 1 <= values[i] <= 10^4
Intuition
A first pass just tries every possible subset of the items: for each one, add up its total weight and value, and if the weight fits inside the capacity, check whether its value beats the best found so far.
function knapsack(cap, weights, values) {
const n = values.length;
let best = 0;
// Every integer from 0 to 2^n - 1 encodes one subset: bit i set means item i is included.
for (let mask = 0; mask < (1 << n); mask++) {
let weight = 0;
let value = 0;
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) {
weight += weights[i];
value += values[i];
}
}
// Only a subset that still fits under the capacity is a candidate answer.
if (weight <= cap && value > best) {
best = value;
}
}
return best;
}This is O(2^n) — every subset is rebuilt and summed from scratch, even though many subsets share the exact same situation partway through: whatever's decided about items 0 and 1 already, the best way to finish depends only on which items remain and how much capacity remains — not on which earlier choices got there. Can we do better?
The key observation: "the best value achievable using items i..n-1 with capacity c" is the same question every time it comes up, so once it's answered it never needs answering again. That's the overlapping-subproblems signature dynamic programming exists to eliminate.
It's a different flavor of the pattern from Coin Change, though. There, each coin denomination can be reused any number of times — an unbounded choice — so dp[total] is one 1-D row that a later step can read after the same coin has already been used once. Here each item can be taken at most once — a 0/1 choice — so the table needs an extra dimension, one row per item: dp[i][c] only ever reads from dp[i+1][...], the row for items not yet decided, never from its own row, or an item could sneak into the same subset twice.
Fill the table bottom-up: dp[i][c] is the best value achievable using only items i..n-1 with capacity c. Work from the last item back to the first, and for each item and each capacity either skip it (dp[i+1][c]) or, if it fits, take it and add its value to the best subproblem left over (values[i] + dp[i+1][c - weights[i]]) — dp[i][c] is the max of those two choices. dp[0][cap] is the answer over every item and the full capacity.
Walking it through:
dp[i][c] = best value using items i..n-1 with capacity c, for weights = [2, 3, 4, 5], values = [3, 4, 5, 6] (rows 0-3 = items, row 4 = no items left; cols = capacity 0-5)
Row 4 means no items are left to consider, and column 0 means there's no capacity left to spend — either way nothing can be packed, so both boundaries are 0 before the fill starts.
Item 3 weighs 5 — too heavy for any capacity under 5, so c = 1 through 4 are all forced skips on this row: each one just inherits whatever the "no items left" row already had, 0.
At c = 5 item 3 finally fits, and taking it is free — there's no capacity left over to spend on anything else, so its whole value carries straight through: dp[3][5] = 6.
Item 2 (weight 4, value 5) does fit in 5 units of capacity — but taking it leaves only 1 unit over (worth 0 more), for a total of 5. Skipping it and keeping item 3's 6 is worth more: fitting isn't enough on its own, it has to beat the alternative.
Item 1 (weight 3, value 4) fills in the same way: it wins here at c = 3 (nothing to compare against yet), but by c = 4 and c = 5 skipping has already pulled back ahead — same tension as item 2's row.
Item 0 (weight 2, value 3) fits, and this time taking it pays off: it leaves 3 units of capacity, which item 1 alone already turns into 4 more value, for 7 combined — one better than skipping it and keeping the 6 from items 2 and 3 alone. dp[0][5] = 7 is the answer: pack items 0 and 1 (weights 2 + 3 = 5, values 3 + 4 = 7).
Optimization
Bottom-up 2-D DP
Let dp[i][c] be the best value achievable using only items i..n-1 with remaining capacity c. Fill the table from the last item back to the first: for each item, either skip it (dp[i+1][c]) or, if it fits, take it and add its value to the best remaining subproblem (values[i] + dp[i+1][c - weights[i]]) — dp[i][c] is the max of those two choices. dp[0][cap] is the answer over all n items and the full capacity.
Working items back-to-front (rather than front-to-back) is just a style choice — either direction of item ordering solves the same recurrence, as long as the earlier dimension has both "skip" and "take" available. O(n * cap) time, O(n * cap) space (row-reducible to O(cap) by keeping just the "next row" of the table).
function knapsack(cap, weights, values) {
const n = values.length;
// dp[i][c] = best value achievable from items i..n-1 with capacity c.
// One extra row (index n) represents "no items left", implicitly all zeros.
const dp = Array.from({ length: n + 1 }, () => new Array(cap + 1).fill(0));
for (let i = n - 1; i >= 0; i--) {
for (let c = 1; c <= cap; c++) {
if (weights[i] <= c) {
// Best of leaving item i out, or taking it and recursing on the leftover capacity.
dp[i][c] = Math.max(values[i] + dp[i + 1][c - weights[i]], dp[i + 1][c]);
} else {
// Too heavy to take at this capacity — only option is to skip it.
dp[i][c] = dp[i + 1][c];
}
}
}
return dp[0][cap];
}Complexity analysis
Time complexity: O(n · cap). Here's why:
- The fill computes exactly one value per cell of the
(n + 1) × (cap + 1)dp table. - Each cell does O(1) work — one weight comparison, then either a single lookup (skip) or an addition and a
maxover two already-known cells (take vs. skip).
So the whole fill costs (n + 1)(cap + 1) × O(1) = O(n · cap) — down from the brute force's exponential O(2^n), since each (i, c) state is now computed exactly once instead of re-derived by every subset that happens to reach it.
Space complexity: O(n · cap). Here's why:
- The stored solution keeps the full
(n + 1) × (cap + 1)dp table, sincedp[i][c]reads two cells from the next row,dp[i+1][c]anddp[i+1][c - weights[i]]. - There's no recursion, so no call stack on top of the table.
That table costs O(n · cap); since each row only ever reads the row directly below it, it's row-reducible to a single rolling row of O(cap) — the stored solution keeps the simpler full table for clarity.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| cap = 7, weights = [], values = [] | 0 | No items at all — nothing to pack regardless of capacity. |
| cap = 10, weights = [4], values = [50] | 50 | Single item lighter than the capacity — it always fits, so the answer is just its value. |
| cap = 0, weights = [2,3], values = [8,8] | 0 | Zero capacity — every item is forced out no matter what it's worth. |
| cap = 7, weights = [3,3,3], values = [4,4,4] | 8 | All items identical — each is still its own item slot, capping the count that fits (two of three, not a fractional third) rather than treating weight as infinitely divisible. |
| cap = 5, weights = [4,4], values = [9,9] | 9 | Two items sharing the same weight and value — capacity only allows one of them, so the DP mustn't secretly reuse the 'same' item twice. |
| cap = 6, weights = [2,3,6], values = [5,5,11] | 11 | A single heavy, high-value item beats combining the two lighter items that also fit (5 + 5 = 10 < 11) — the reason a greedy 'grab everything that fits' strategy fails on 0/1 knapsack. |
Try it yourself
Write your solution against the real judge before checking the reference.