Knapsack
Rows are items considered so far, columns are capacities, and each cell is the best value for that pair. Every cell is a two-way choice: skip the item and keep the cell above, or take it and add its value to the best answer for the capacity left over. Where that leftover answer comes from, the previous row or the same row, is the only difference between taking each item once and taking it as often as you like.
Items: i1 weighs 1 and is worth 1, i2 weighs 3 and is worth 4, i3 weighs 4 and is worth 5, i4 weighs 5 and is worth 7. Capacity 7. Cell (i, w) is the best value from the first i items within weight w. Row 0 has no items, so it is all zeros. Unbounded: any item may be taken more than once.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 19, with their answers.
Item 1 weighs 1 and is worth 1, capacity 1. Skip gives 0, take gives 1. Which?
Answer: Take it, value plus the leftover. 1 beats 0. The leftover capacity 0 was already solved on this row, so the item can appear again.
Item 1 weighs 1 and is worth 1, capacity 2. Skip gives 0, take gives 2. Which?
Answer: Take it, value plus the leftover. 2 beats 0. The leftover capacity 1 was already solved on this row, so the item can appear again.
Item 1 weighs 1 and is worth 1, capacity 3. Skip gives 0, take gives 3. Which?
Answer: Take it, value plus the leftover. 3 beats 0. The leftover capacity 2 was already solved on this row, so the item can appear again.
Item 1 weighs 1 and is worth 1, capacity 4. Skip gives 0, take gives 4. Which?
Answer: Take it, value plus the leftover. 4 beats 0. The leftover capacity 3 was already solved on this row, so the item can appear again.
Item 1 weighs 1 and is worth 1, capacity 5. Skip gives 0, take gives 5. Which?
Answer: Take it, value plus the leftover. 5 beats 0. The leftover capacity 4 was already solved on this row, so the item can appear again.
Item 1 weighs 1 and is worth 1, capacity 6. Skip gives 0, take gives 6. Which?
Answer: Take it, value plus the leftover. 6 beats 0. The leftover capacity 5 was already solved on this row, so the item can appear again.
Item 1 weighs 1 and is worth 1, capacity 7. Skip gives 0, take gives 7. Which?
Answer: Take it, value plus the leftover. 7 beats 0. The leftover capacity 6 was already solved on this row, so the item can appear again.
Item 2 weighs 3 and is worth 4, capacity 3. Skip gives 3, take gives 4. Which?
Answer: Take it, value plus the leftover. 4 beats 3. The leftover capacity 0 was already solved on this row, so the item can appear again.
Item 2 weighs 3 and is worth 4, capacity 4. Skip gives 4, take gives 5. Which?
Answer: Take it, value plus the leftover. 5 beats 4. The leftover capacity 1 was already solved on this row, so the item can appear again.
Item 2 weighs 3 and is worth 4, capacity 5. Skip gives 5, take gives 6. Which?
Answer: Take it, value plus the leftover. 6 beats 5. The leftover capacity 2 was already solved on this row, so the item can appear again.
Item 2 weighs 3 and is worth 4, capacity 6. Skip gives 6, take gives 8. Which?
Answer: Take it, value plus the leftover. 8 beats 6. The leftover capacity 3 was already solved on this row, so the item can appear again.
Item 2 weighs 3 and is worth 4, capacity 7. Skip gives 7, take gives 9. Which?
Answer: Take it, value plus the leftover. 9 beats 7. The leftover capacity 4 was already solved on this row, so the item can appear again.
Item 3 weighs 4 and is worth 5, capacity 4. Skip gives 5, take gives 5. Which?
Answer: Skip it, keep the cell above. 5 is at least 5, so the item is not worth its weight here.
Item 3 weighs 4 and is worth 5, capacity 5. Skip gives 6, take gives 6. Which?
Answer: Skip it, keep the cell above. 6 is at least 6, so the item is not worth its weight here.
Item 3 weighs 4 and is worth 5, capacity 6. Skip gives 8, take gives 7. Which?
Answer: Skip it, keep the cell above. 8 is at least 7, so the item is not worth its weight here.
Item 3 weighs 4 and is worth 5, capacity 7. Skip gives 9, take gives 9. Which?
Answer: Skip it, keep the cell above. 9 is at least 9, so the item is not worth its weight here.
Item 4 weighs 5 and is worth 7, capacity 5. Skip gives 6, take gives 7. Which?
Answer: Take it, value plus the leftover. 7 beats 6. The leftover capacity 0 was already solved on this row, so the item can appear again.
Item 4 weighs 5 and is worth 7, capacity 6. Skip gives 8, take gives 8. Which?
Answer: Skip it, keep the cell above. 8 is at least 8, so the item is not worth its weight here.
Item 4 weighs 5 and is worth 7, capacity 7. Skip gives 9, take gives 9. Which?
Answer: Skip it, keep the cell above. 9 is at least 9, so the item is not worth its weight here.
How it runs, step by step
Items: i1 weighs 1 and is worth 1, i2 weighs 3 and is worth 4, i3 weighs 4 and is worth 5, i4 weighs 5 and is worth 7. Capacity 7. Cell (i, w) is the best value from the first i items within weight w. Row 0 has no items, so it is all zeros. Unbounded: any item may be taken more than once.
Building the unbounded knapsack table for 4 items and capacity 7.
Item 1 (weight 1, value 1) at capacity 0. It does not fit, so only skipping is possible: copy the cell above, 0.
Item 1 at capacity 0: too heavy, so 0 from above.
Item 1 (weight 1, value 1) at capacity 1. Skip: 0 from above. Take: 1 + 0 from this row at capacity 0 = 1. Best: 1, take.
Item 1 at capacity 1: best of skip 0 and take 1 is 1.
Item 1 (weight 1, value 1) at capacity 2. Skip: 0 from above. Take: 1 + 1 from this row at capacity 1 = 2. Best: 2, take.
Item 1 at capacity 2: best of skip 0 and take 2 is 2.
Item 1 (weight 1, value 1) at capacity 3. Skip: 0 from above. Take: 1 + 2 from this row at capacity 2 = 3. Best: 3, take.
Item 1 at capacity 3: best of skip 0 and take 3 is 3.
Item 1 (weight 1, value 1) at capacity 4. Skip: 0 from above. Take: 1 + 3 from this row at capacity 3 = 4. Best: 4, take.
Item 1 at capacity 4: best of skip 0 and take 4 is 4.
Item 1 (weight 1, value 1) at capacity 5. Skip: 0 from above. Take: 1 + 4 from this row at capacity 4 = 5. Best: 5, take.
Item 1 at capacity 5: best of skip 0 and take 5 is 5.
Item 1 (weight 1, value 1) at capacity 6. Skip: 0 from above. Take: 1 + 5 from this row at capacity 5 = 6. Best: 6, take.
Item 1 at capacity 6: best of skip 0 and take 6 is 6.
Item 1 (weight 1, value 1) at capacity 7. Skip: 0 from above. Take: 1 + 6 from this row at capacity 6 = 7. Best: 7, take.
Item 1 at capacity 7: best of skip 0 and take 7 is 7.
Item 2 (weight 3, value 4) at capacity 0. It does not fit, so only skipping is possible: copy the cell above, 0.
Item 2 at capacity 0: too heavy, so 0 from above.
Item 2 (weight 3, value 4) at capacity 1. It does not fit, so only skipping is possible: copy the cell above, 1.
Item 2 at capacity 1: too heavy, so 1 from above.
Item 2 (weight 3, value 4) at capacity 2. It does not fit, so only skipping is possible: copy the cell above, 2.
Item 2 at capacity 2: too heavy, so 2 from above.
Item 2 (weight 3, value 4) at capacity 3. Skip: 3 from above. Take: 4 + 0 from this row at capacity 0 = 4. Best: 4, take.
Item 2 at capacity 3: best of skip 3 and take 4 is 4.
Item 2 (weight 3, value 4) at capacity 4. Skip: 4 from above. Take: 4 + 1 from this row at capacity 1 = 5. Best: 5, take.
Item 2 at capacity 4: best of skip 4 and take 5 is 5.
Item 2 (weight 3, value 4) at capacity 5. Skip: 5 from above. Take: 4 + 2 from this row at capacity 2 = 6. Best: 6, take.
Item 2 at capacity 5: best of skip 5 and take 6 is 6.
Item 2 (weight 3, value 4) at capacity 6. Skip: 6 from above. Take: 4 + 4 from this row at capacity 3 = 8. Best: 8, take.
Item 2 at capacity 6: best of skip 6 and take 8 is 8.
Item 2 (weight 3, value 4) at capacity 7. Skip: 7 from above. Take: 4 + 5 from this row at capacity 4 = 9. Best: 9, take.
Item 2 at capacity 7: best of skip 7 and take 9 is 9.
Item 3 (weight 4, value 5) at capacity 0. It does not fit, so only skipping is possible: copy the cell above, 0.
Item 3 at capacity 0: too heavy, so 0 from above.
Item 3 (weight 4, value 5) at capacity 1. It does not fit, so only skipping is possible: copy the cell above, 1.
Item 3 at capacity 1: too heavy, so 1 from above.
Item 3 (weight 4, value 5) at capacity 2. It does not fit, so only skipping is possible: copy the cell above, 2.
Item 3 at capacity 2: too heavy, so 2 from above.
Item 3 (weight 4, value 5) at capacity 3. It does not fit, so only skipping is possible: copy the cell above, 4.
Item 3 at capacity 3: too heavy, so 4 from above.
Item 3 (weight 4, value 5) at capacity 4. Skip: 5 from above. Take: 5 + 0 from this row at capacity 0 = 5. Best: 5, skip.
Item 3 at capacity 4: best of skip 5 and take 5 is 5.
Item 3 (weight 4, value 5) at capacity 5. Skip: 6 from above. Take: 5 + 1 from this row at capacity 1 = 6. Best: 6, skip.
Item 3 at capacity 5: best of skip 6 and take 6 is 6.
Item 3 (weight 4, value 5) at capacity 6. Skip: 8 from above. Take: 5 + 2 from this row at capacity 2 = 7. Best: 8, skip.
Item 3 at capacity 6: best of skip 8 and take 7 is 8.
Item 3 (weight 4, value 5) at capacity 7. Skip: 9 from above. Take: 5 + 4 from this row at capacity 3 = 9. Best: 9, skip.
Item 3 at capacity 7: best of skip 9 and take 9 is 9.
Item 4 (weight 5, value 7) at capacity 0. It does not fit, so only skipping is possible: copy the cell above, 0.
Item 4 at capacity 0: too heavy, so 0 from above.
Item 4 (weight 5, value 7) at capacity 1. It does not fit, so only skipping is possible: copy the cell above, 1.
Item 4 at capacity 1: too heavy, so 1 from above.
Item 4 (weight 5, value 7) at capacity 2. It does not fit, so only skipping is possible: copy the cell above, 2.
Item 4 at capacity 2: too heavy, so 2 from above.
Item 4 (weight 5, value 7) at capacity 3. It does not fit, so only skipping is possible: copy the cell above, 4.
Item 4 at capacity 3: too heavy, so 4 from above.
Item 4 (weight 5, value 7) at capacity 4. It does not fit, so only skipping is possible: copy the cell above, 5.
Item 4 at capacity 4: too heavy, so 5 from above.
Item 4 (weight 5, value 7) at capacity 5. Skip: 6 from above. Take: 7 + 0 from this row at capacity 0 = 7. Best: 7, take.
Item 4 at capacity 5: best of skip 6 and take 7 is 7.
Item 4 (weight 5, value 7) at capacity 6. Skip: 8 from above. Take: 7 + 1 from this row at capacity 1 = 8. Best: 8, skip.
Item 4 at capacity 6: best of skip 8 and take 8 is 8.
Item 4 (weight 5, value 7) at capacity 7. Skip: 9 from above. Take: 7 + 2 from this row at capacity 2 = 9. Best: 9, skip.
Item 4 at capacity 7: best of skip 9 and take 9 is 9.
Best value 9 with items i1, i2, i2. 32 cells, each one comparison: O(items x capacity), which is fast when the capacity is small even though the subsets number 2 to the 4.
The best value is 9.
Write it yourself
Define knapsack(weights, values, capacity) and return the greatest value that fits, taking each item at most once. It runs in your browser against this lesson's own 2 examples.
// Decide item by item: the best for this capacity is either without the item, or its value plus the best for what is left.function knapsack(weights, values, capacity) { return 0;}
Remember
- dp[i][w] = max(skip, take) with skip = dp[i-1][w] and take = value + dp[?][w - weight].
- 0/1: the leftover reads the previous row, so an item is used at most once. Unbounded: the same row, so it can repeat.
- The cost is items x capacity, a pseudo-polynomial bound: cheap for small capacities, useless for huge ones.
Topics covered
Where this is used
CryptocurrencyBitcoin block assembly
A miner choosing which transactions go in a block is solving this exact shape: the four million weight unit block limit is the capacity, each transaction's weight is its weight and its fee is its value. Bitcoin Core does not build the table. A capacity in the millions would make it enormous, and a transaction can depend on an unconfirmed parent, which a plain knapsack has no way to express. Its block assembler instead takes the best fee rate group of transactions still available and adds it if it fits, trading a slightly smaller fee total for an answer in milliseconds.
ManufacturingCutting stock in paper and board mills
Cutting fixed-width rolls or boards into ordered sizes with the least waste is solved one cutting pattern at a time. In the one dimensional case, finding the next pattern worth adding is an unbounded knapsack: the stock width is the capacity, the ordered pieces are the items that can repeat, and their values are the dual prices from the current linear program. This is the Gilmore and Gomory column generation method that industrial nesting and optimisation software still runs.
CryptographyThe Merkle-Hellman cipher
One of the earliest public key schemes put its trapdoor on subset sum, the knapsack where each item's value equals its weight. The private key is a superincreasing set of weights, where the answer falls out greedily in one pass; multiplying that set by a secret number modulo another scrambles it into a public set that looks hard. Shamir published a polynomial time break in 1984, which is the standing reminder that a problem being hard in general says nothing about the particular instances a system hands out.
Operations researchGoogle OR-Tools knapsack solver
OR-Tools ships a solver for this one shape, separate from its general mixed integer programming solver. With exactly one capacity constraint it can use the table and a branch and bound tuned around it instead of a generic search, which is much faster on the same instance. Teams reach for it to load cargo under a weight limit or to spend a fixed budget across candidate projects.
Why it works this way
Why sorting by value per unit of weight does not work
That greedy rule is optimal for the fractional version, where you can cut an item in half and top the bag up exactly. Here you cannot, so the densest items can leave a gap that nothing fills. Take this lesson's own example, capacity 7 with items (weight 1, value 1), (3, 4), (4, 5), (5, 7): density picks (5, 7) first, after which only (1, 1) still fits, for 8. The table finds (3, 4) plus (4, 5), which fills the bag exactly, for 9.
The one-array version has to run capacities backwards
You can drop the row index and keep a single array of size capacity + 1. For 0/1 the inner loop must count down from capacity to the item's weight, so that dp[w - weight] still holds the previous row's value and the item is used at most once. Run it upwards and dp[w - weight] has already been updated with this item, which silently turns the code into the unbounded version. Same loop body, same shape of answer, different problem.
Getting the items back, not just the number
The table tells you the best value, not what to pack. Start at dp[n][capacity] and walk up: if dp[i][w] equals dp[i-1][w] the item was skipped, so move to row i-1 at the same w; otherwise it was taken, so record it and move to dp[i-1][w - wt[i-1]]. That walk is the reason to keep the full table, because the one-array version above overwrites exactly the history it reads.
NP-hard, yet the work is a plain rectangle
Both are true, and the catch is how the input is measured. The capacity is written down in a handful of digits, so a capacity of a billion is a tiny input with an enormous table, and the rectangle grows exponentially in the size of what you typed. When the capacity is huge but the values are small, flip the axes: let dp[i][v] be the smallest weight that reaches value v, then read off the largest v whose weight still fits.
Read more
- Knapsack problemWikipedia
- Knapsack Problemcp-algorithms
- Knapsack DPUSACO Guide
- Pseudo-polynomial timeWikipedia
- The Knapsack ProblemGoogle OR-Tools · developers.google.com
Next up
- Bitmask DPA bitmask encodes which elements are used; classic for TSP on small n.
- Decode Waysways[i] adds ways[i-1] when the digit is not 0 and ways[i-2] when the pair before it lies in 10..26.
- Interval DPFill a triangular table by range length; each range takes the cheapest split into two shorter ranges.