The 0/1 knapsack problem asks you to pack the most valuable subset of items into a bag with a fixed weight limit, where each item is taken whole or left behind — never split, never taken twice (that is the "0/1"). Each item i has a weight weights[i] and a value values[i], given as two parallel arrays. You return the maximum total value you can carry without the combined weight exceeding capacity. It is the textbook example of dynamic programming — see Knapsack problem for background.
knapsack01(weights, values, capacity)
// weights[i], values[i]: the weight and value of item i (parallel arrays, same length)
// capacity: the weight budget of the knapsack
// -> number: the maximum total value that fits within the budget// Items (weight, value): (1,1) (3,4) (4,5) (5,7); budget 7.
// Best pick: the (3,4) and (4,5) items — weight 3 + 4 = 7, value 4 + 5 = 9.
knapsack01([1, 3, 4, 5], [1, 4, 5, 7], 7); // 9// A bag with no room can hold nothing.
knapsack01([1, 3, 4, 5], [1, 4, 5, 7], 0); // 0// Every item fits at once, so the answer is the sum of all values.
knapsack01([1, 2, 3], [6, 10, 12], 6); // 28weights and values have the same length; weights[i] and values[i] describe the same item i.capacity are non-negative integers; values are non-negative too.capacity exactly is allowed.We are choosing a subset of items to pack into a weight-limited bag so the total value is as large as possible, with each item taken at most once.
You are standing in front of a shelf of loot with a bag that can carry only so much weight. Each item has a weight and a resale value. You want to walk out with the most valuable haul the bag can hold — but you cannot saw an item in half or grab the same item twice, so every item is a clean yes-or-no. That yes-or-no is the "0/1" in the name: item taken (1) or left behind (0). Given the weights, the values, and the bag's capacity, return the largest total value you can carry.
Forget clever formulas for a moment. For each item you face exactly one decision: take it or skip it. Take it and you gain its value but spend some of your weight budget; skip it and the budget is untouched. The best haul is whichever of those two choices leads to more total value — asked for every item in turn. So the whole problem is a stack of take-or-skip decisions, and we want the combination that maximizes value without blowing the weight limit.
The tempting shortcut is greed: sort items by value per unit of weight and grab the densest ones first, since they look like the best deal.
function knapsackGreedy(weights, values, capacity) {
// Order the item indices by value-per-weight, densest first.
const order = weights
.map((w, i) => i)
.sort((a, b) => values[b] / weights[b] - values[a] / weights[a]);
let total = 0;
let room = capacity;
for (const i of order) {
if (weights[i] <= room) { // take the whole item if it still fits
total += values[i];
room -= weights[i];
}
}
return total;
}This is fast and it feels right, but it is wrong for 0/1 knapsack. Take weights [10, 20, 30], values [60, 100, 120], capacity 50. The value-per-weight ratios are 6, 5, 4, so greed grabs the first two items for weight 30 and value 160 — and then the third item (weight 30) no longer fits. But the best haul is the last two items: weight 20 + 30 = 50 fills the bag exactly for value 220. Greed loses by 60, because committing to the densest item locked it out of a better combination.
Since you cannot trust a shortcut, the only sure way is to actually try both choices — take or skip — for every item and keep whichever wins:
function knapsack01Naive(weights, values, capacity, i = 0) {
// Considered every item: nothing more to gain.
if (i === weights.length) return 0;
// Skip item i: budget unchanged, move on to the next item.
const skip = knapsack01Naive(weights, values, capacity, i + 1);
// Take item i, but only if it fits: its value plus the best of the rest.
let take = 0;
if (weights[i] <= capacity) {
take = values[i] + knapsack01Naive(weights, values, capacity - weights[i], i + 1);
}
return Math.max(skip, take);
}This is correct — it explores every subset — but it is exponential. Each item doubles the number of branches, so n items cost about 2^n calls, and many of those calls re-solve the same subproblem: "the best value for items i onward with budget w" comes up again and again. That overlap is the signal to switch to dynamic programming — solve each (item, budget) subproblem once and store its answer in a table.
function knapsack01(weights, values, capacity) {
const n = weights.length;
// dp[i][w] = the best value using the first i items with a weight budget of w.
// Row 0 means "no items yet", so it is all zeros — the base case.
const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
const weight = weights[i - 1]; // item i lives at index i - 1 (dp rows lead by one)
const value = values[i - 1];
for (let w = 0; w <= capacity; w++) {
if (weight > w) {
// Item i cannot fit in a budget of w — carry the best-without-it down.
dp[i][w] = dp[i - 1][w];
} else {
// Better of SKIP (dp[i-1][w]) and TAKE (this value plus the best of the
// leftover budget from the PREVIOUS row, so item i is used at most once).
dp[i][w] = Math.max(dp[i - 1][w], value + dp[i - 1][w - weight]);
}
}
}
return dp[n][capacity];
}
module.exports = { knapsack01 };dp[i][w] answers one focused question: using only the first i items and a bag that holds weight w, what is the most value you can carry? The base row dp[0] is all zeros because zero items carry zero value. Every later cell makes the same take-or-skip choice as the recursion — but because the rows below it are already filled in, each cell is a single Math.max instead of two more recursive calls. There are (n + 1) × (capacity + 1) cells and each costs constant work, so the whole thing is O(n × capacity) in time and space, and the answer — all n items with the full budget — sits in dp[n][capacity].
Take knapsack01([1, 3, 4, 5], [1, 4, 5, 7], 7) — four items with (weight, value) of (1,1), (3,4), (4,5), (5,7), and a budget of 7. We fill the table one row per item, left to right:
item1 (weight 1, value 1): the item fits in every budget from 1 up, so every cell past w=0 becomes 1.item2 (weight 3, value 4): at w=3, taking it gives 4 + dp[1][0] = 4, which beats skipping (dp[1][3] = 1), so the cell is 4. That 4 carries rightward.item3 (weight 4, value 5): at w=7, skipping gives dp[2][7] = 5, but taking gives 5 + dp[2][3] = 5 + 4 = 9. Nine wins — this is the weight-4 item joining the weight-3 item to fill the bag exactly.item4 (weight 5, value 7): at w=7, taking gives 7 + dp[3][2] = 7 + 1 = 8, which loses to skipping (dp[3][7] = 9). So the answer stays 9.Read the bottom-right cell, dp[4][7] = 9 — the most value you can carry is 9, exactly the two-item pick we spotted at the very start.
take reads the previous row. The take branch adds dp[i-1][w - weight], the best without item i yet, so item i is counted at most once. Reading the current row dp[i][w - weight] would let you take the same item again and again — that is a different problem (unbounded knapsack).[10, 20, 30] / [60, 100, 120] case settles for 160 instead of 220. Only trying both choices, via the recursion or the table, is guaranteed correct.i accounts for the first i items, so item i's own weight and value live at weights[i - 1] and values[i - 1]. An off-by-one here reads the wrong item and silently returns a wrong number.weight > w you cannot take item i, but the cell is not 0 — it is dp[i-1][w], the best the earlier items already achieved for that budget. Forgetting to copy it leaves a 0 that poisons every cell below.capacity + 1 suffices — but you must iterate w from capacity down to weight. Going downward keeps each dp[w - weight] referring to the previous item's values; going upward would let one item be taken several times, quietly turning it into unbounded knapsack.dp[n][capacity]: at each row, if dp[i][w] differs from dp[i-1][w] then item i was taken — record it and drop w by its weight — otherwise move straight up.dp[i][w - weight]) instead of the previous one, so an item can be reused; the one-row version then iterates w upward.W?" and you have subset-sum — the same table with booleans instead of values. Splitting an array into two equal-sum halves (the partition problem) is subset-sum for W = total / 2.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
The 0/1 knapsack problem asks you to pack the most valuable subset of items into a bag with a fixed weight limit, where each item is taken whole or left behind — never split, never taken twice (that is the "0/1"). Each item i has a weight weights[i] and a value values[i], given as two parallel arrays. You return the maximum total value you can carry without the combined weight exceeding capacity. It is the textbook example of dynamic programming — see Knapsack problem for background.
knapsack01(weights, values, capacity)
// weights[i], values[i]: the weight and value of item i (parallel arrays, same length)
// capacity: the weight budget of the knapsack
// -> number: the maximum total value that fits within the budget// Items (weight, value): (1,1) (3,4) (4,5) (5,7); budget 7.
// Best pick: the (3,4) and (4,5) items — weight 3 + 4 = 7, value 4 + 5 = 9.
knapsack01([1, 3, 4, 5], [1, 4, 5, 7], 7); // 9// A bag with no room can hold nothing.
knapsack01([1, 3, 4, 5], [1, 4, 5, 7], 0); // 0// Every item fits at once, so the answer is the sum of all values.
knapsack01([1, 2, 3], [6, 10, 12], 6); // 28weights and values have the same length; weights[i] and values[i] describe the same item i.capacity are non-negative integers; values are non-negative too.capacity exactly is allowed.We are choosing a subset of items to pack into a weight-limited bag so the total value is as large as possible, with each item taken at most once.
You are standing in front of a shelf of loot with a bag that can carry only so much weight. Each item has a weight and a resale value. You want to walk out with the most valuable haul the bag can hold — but you cannot saw an item in half or grab the same item twice, so every item is a clean yes-or-no. That yes-or-no is the "0/1" in the name: item taken (1) or left behind (0). Given the weights, the values, and the bag's capacity, return the largest total value you can carry.
Forget clever formulas for a moment. For each item you face exactly one decision: take it or skip it. Take it and you gain its value but spend some of your weight budget; skip it and the budget is untouched. The best haul is whichever of those two choices leads to more total value — asked for every item in turn. So the whole problem is a stack of take-or-skip decisions, and we want the combination that maximizes value without blowing the weight limit.
The tempting shortcut is greed: sort items by value per unit of weight and grab the densest ones first, since they look like the best deal.
function knapsackGreedy(weights, values, capacity) {
// Order the item indices by value-per-weight, densest first.
const order = weights
.map((w, i) => i)
.sort((a, b) => values[b] / weights[b] - values[a] / weights[a]);
let total = 0;
let room = capacity;
for (const i of order) {
if (weights[i] <= room) { // take the whole item if it still fits
total += values[i];
room -= weights[i];
}
}
return total;
}This is fast and it feels right, but it is wrong for 0/1 knapsack. Take weights [10, 20, 30], values [60, 100, 120], capacity 50. The value-per-weight ratios are 6, 5, 4, so greed grabs the first two items for weight 30 and value 160 — and then the third item (weight 30) no longer fits. But the best haul is the last two items: weight 20 + 30 = 50 fills the bag exactly for value 220. Greed loses by 60, because committing to the densest item locked it out of a better combination.
Since you cannot trust a shortcut, the only sure way is to actually try both choices — take or skip — for every item and keep whichever wins:
function knapsack01Naive(weights, values, capacity, i = 0) {
// Considered every item: nothing more to gain.
if (i === weights.length) return 0;
// Skip item i: budget unchanged, move on to the next item.
const skip = knapsack01Naive(weights, values, capacity, i + 1);
// Take item i, but only if it fits: its value plus the best of the rest.
let take = 0;
if (weights[i] <= capacity) {
take = values[i] + knapsack01Naive(weights, values, capacity - weights[i], i + 1);
}
return Math.max(skip, take);
}This is correct — it explores every subset — but it is exponential. Each item doubles the number of branches, so n items cost about 2^n calls, and many of those calls re-solve the same subproblem: "the best value for items i onward with budget w" comes up again and again. That overlap is the signal to switch to dynamic programming — solve each (item, budget) subproblem once and store its answer in a table.
function knapsack01(weights, values, capacity) {
const n = weights.length;
// dp[i][w] = the best value using the first i items with a weight budget of w.
// Row 0 means "no items yet", so it is all zeros — the base case.
const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
const weight = weights[i - 1]; // item i lives at index i - 1 (dp rows lead by one)
const value = values[i - 1];
for (let w = 0; w <= capacity; w++) {
if (weight > w) {
// Item i cannot fit in a budget of w — carry the best-without-it down.
dp[i][w] = dp[i - 1][w];
} else {
// Better of SKIP (dp[i-1][w]) and TAKE (this value plus the best of the
// leftover budget from the PREVIOUS row, so item i is used at most once).
dp[i][w] = Math.max(dp[i - 1][w], value + dp[i - 1][w - weight]);
}
}
}
return dp[n][capacity];
}
module.exports = { knapsack01 };dp[i][w] answers one focused question: using only the first i items and a bag that holds weight w, what is the most value you can carry? The base row dp[0] is all zeros because zero items carry zero value. Every later cell makes the same take-or-skip choice as the recursion — but because the rows below it are already filled in, each cell is a single Math.max instead of two more recursive calls. There are (n + 1) × (capacity + 1) cells and each costs constant work, so the whole thing is O(n × capacity) in time and space, and the answer — all n items with the full budget — sits in dp[n][capacity].
Take knapsack01([1, 3, 4, 5], [1, 4, 5, 7], 7) — four items with (weight, value) of (1,1), (3,4), (4,5), (5,7), and a budget of 7. We fill the table one row per item, left to right:
item1 (weight 1, value 1): the item fits in every budget from 1 up, so every cell past w=0 becomes 1.item2 (weight 3, value 4): at w=3, taking it gives 4 + dp[1][0] = 4, which beats skipping (dp[1][3] = 1), so the cell is 4. That 4 carries rightward.item3 (weight 4, value 5): at w=7, skipping gives dp[2][7] = 5, but taking gives 5 + dp[2][3] = 5 + 4 = 9. Nine wins — this is the weight-4 item joining the weight-3 item to fill the bag exactly.item4 (weight 5, value 7): at w=7, taking gives 7 + dp[3][2] = 7 + 1 = 8, which loses to skipping (dp[3][7] = 9). So the answer stays 9.Read the bottom-right cell, dp[4][7] = 9 — the most value you can carry is 9, exactly the two-item pick we spotted at the very start.
take reads the previous row. The take branch adds dp[i-1][w - weight], the best without item i yet, so item i is counted at most once. Reading the current row dp[i][w - weight] would let you take the same item again and again — that is a different problem (unbounded knapsack).[10, 20, 30] / [60, 100, 120] case settles for 160 instead of 220. Only trying both choices, via the recursion or the table, is guaranteed correct.i accounts for the first i items, so item i's own weight and value live at weights[i - 1] and values[i - 1]. An off-by-one here reads the wrong item and silently returns a wrong number.weight > w you cannot take item i, but the cell is not 0 — it is dp[i-1][w], the best the earlier items already achieved for that budget. Forgetting to copy it leaves a 0 that poisons every cell below.capacity + 1 suffices — but you must iterate w from capacity down to weight. Going downward keeps each dp[w - weight] referring to the previous item's values; going upward would let one item be taken several times, quietly turning it into unbounded knapsack.dp[n][capacity]: at each row, if dp[i][w] differs from dp[i-1][w] then item i was taken — record it and drop w by its weight — otherwise move straight up.dp[i][w - weight]) instead of the previous one, so an item can be reused; the one-row version then iterates w upward.W?" and you have subset-sum — the same table with booleans instead of values. Splitting an array into two equal-sum halves (the partition problem) is subset-sum for W = total / 2.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.