The knapsack problem
A hiker is packing a bag that can carry at most 5 kg. Three things are laid out, and each has a weight and a value that says how useful it would be on the trip:
| Item | Weight | Value |
|---|---|---|
| Tent | 2 kg | 4 |
| Stove | 3 kg | 5 |
| Camera | 4 kg | 7 |
The hiker wants the largest total value that fits in the bag. The camera is worth the most, but it weighs 4 kg and neither of the others fits beside it, so that choice is worth 7. The tent and the stove weigh exactly 5 kg together and are worth , which is the best that fits.
This is the knapsack problem. There are items, each with a weight and a value, and a bag with a weight limit called its capacity. We want the largest total value of a set of items whose total weight is at most the capacity. In the version called 0/1 knapsack, there is one of each item, and it is taken whole or left behind.
Taking the most valuable item first gave 7 where the answer is 9. A program that tries every selection is always right, but each item is either in or out, so items have selections. That is 8 for the hiker, 1,048,576 for 20 items, and a number 31 digits long for 100 items.
Take or skip each item
House Robber also took or skipped each house, and its state was the number of houses considered so far. We start the same way: take the items in the order they are listed, and try "the best value from the first items" as the state.
For the tent and the stove that value is 9, and packing both of them fills the bag. When the camera comes next, the 9 is no help. The camera needs 4 kg, so the question is what the first two items are worth in the 1 kg left beside it, and the answer, 0, is not recorded anywhere. A state that holds only the best value records what a selection is worth and not how much room it leaves, so it cannot tell whether the next item fits.
So the room goes into the state. Let dp[i][c] be the largest total value of a selection from the first items whose total weight is at most . A state is a pair, a number of items from 0 to and a capacity from 0 to , where is the capacity of the bag. The answer is dp[n][C].
For the transition, look at the last of those items, item , with weight and value . There are two things to do with it:
- Skip it. The selection is then made from the first items with the same capacity, and the best one is worth
dp[i - 1][c]. - Take it, which is possible only when . The item uses of the capacity, so the rest of the selection is made from the first items with capacity . The total is
dp[i - 1][c - w] + v.
The base cases are the states with no items: dp[0][c] is 0 for every capacity. Each row of the table reads only the row above it, so the rows are filled from top to bottom. Within a row the capacities can go in any order.
Here is the table for the hiker's first two items, with the stove's row being filled at capacity 5:
Skipping the stove leaves the tent with all 5 kg, which is worth 4. Taking the stove leaves kg for the tent, which is still worth 4, and adds the stove's 5:
The finished table has one more row, for the camera:
The camera's row ends in 9 as well, the answer we found by hand: taking the camera at capacity 5 would leave 1 kg for the other two items and give only 7.
Fill the table with two loops
In the program, row of the table belongs to weights[i - 1] and values[i - 1], because lists are numbered from 0 and row 0 stands for no items. Each entry starts as the skip candidate and is raised to the take candidate when the item fits and taking it is better.
def knapsack_table(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i - 1], values[i - 1]
for c in range(capacity + 1):
dp[i][c] = dp[i - 1][c]
if w <= c:
dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)
return dp[n][capacity]
print(knapsack_table([2, 3, 4], [4, 5, 7], 5))Prints 9 for the hiker's three items.
Both candidates come from row , which was filled before item was considered. An item therefore cannot be added to a selection that already contains it, which will matter when we shrink the table.
Worked example
Predict each row yourself
The trace fills the table one row at a time and shows the row each entry reads from. Switch on Predict the next step to work out each row before it appears. In the input "One item, room for two", a single item of weight 2 and value 3 has a capacity of 4 to fill. Its row ends at 3 and not 6: both candidates read the row for no items, so the item is packed once.
dp[i][c] means the best value using the first i items with capacity at most c. Row 0 is all zero.
Change the example input
Current result: 9
Find which items were taken
The table gives the best value and not the selection. As with the grid, the selection can be read back from the finished table. Start at dp[n][C], and at each entry dp[i][c] look at the entry directly above it. If the two are equal, item was not needed, so move up one row. Otherwise the entry came from taking item : record the item, then move up one row and left by its weight. Stop at row 0.
For the hiker the walk starts at the camera's 9. The entry above it is also 9, so the camera is skipped. In the stove's row, the 9 differs from the 4 above it, so the stove is taken, and the walk moves to capacity in the tent's row. That entry is 4 and the one above it is 0, so the tent is taken too.
This second widget fills the table one entry at a time, like the trace, and adds the walk back as its last step. Its items 1, 2 and 3 are the tent, the stove and the camera. The weights and values can be edited: with a value of 10, the camera alone becomes the best choice.
Keep one row of the table
The hiker's table has 4 rows and 6 columns. The next problem is the same question with limits where the table has about a hundred million entries.
A book shop sells different books, and you know the price and the number of pages of each. You can spend at most in total and buy each book at most once. What is the largest total number of pages you can buy?
The first input line holds and . The second line holds the prices and the third the page counts. Print the largest number of pages.
Constraints
- Every price and page count is between 1 and 1,000
- Time limit 1 second, memory limit 512 MB
Sample · Input
4 10 4 8 5 3 5 12 8 1
Output
13
This is 0/1 knapsack under other names: a book's price is its weight, its number of pages is its value, and the budget is the capacity. In the sample, the books priced 4 and 5 cost 9 together and have pages, the most the budget can buy.
At the limits there are 1,000 books and a budget of 100,000, so the full table has
A Python list needs 8 bytes for every entry it refers to, so the table would take more than 800 MB, and the limit is 512 MB.
The transition shows how to use less. Row reads only row , so once a row is complete, the rows above it are never read again. When the problem asks only for the best value, as this one does, the program can keep a single array dp with one entry per capacity. At the start of item 's turn the array holds row , and the loop over the capacities overwrites it with row :
dp[c] = max(dp[c], dp[c - w] + v)On the right-hand side, dp[c] is the skip candidate. It has not been overwritten yet, so it still belongs to row . The take candidate needs dp[c - w] to belong to row as well, and that depends on the order of the loop. The entry dp[c - w] lies to the left of dp[c]. If the capacities go from high to low, the loop reaches that entry later, and it still holds its old value when it is read. If they go from low to high, the entry has already been overwritten with a value that may include item , and the item is then added to a selection that already contains it.
Here is the tent's turn, with weight 2 and value 4, on a row of 0s for the capacities 0 to 6, done in both orders:
dp[4] reads dp[2] after the tent has been stored there and becomes 8, the value of two tents. dp[6] becomes 12, the value of three.Step through both orders
The widget runs both orders on the hiker's three items with capacity 6, where high to low is right to left in the row. It flags every step that reads an entry the same item has already updated.
From right to left the row ends at 11, the tent and the camera, which is the best selection for 6 kg. From left to right it ends at 12, three tents.
Book Shop with one row
The program is the table-filling loop from before with the item index dropped from dp and the capacities reversed.
range(capacity, w - 1, -1) counts down from the capacity and ends at . A capacity below cannot hold the item, so those entries keep their values.
def knapsack(weights, values, capacity):
dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
for c in range(capacity, w - 1, -1):
dp[c] = max(dp[c], dp[c - w] + v)
return dp[capacity]
n, x = map(int, input().split())
prices = list(map(int, input().split()))
pages = list(map(int, input().split()))
print(knapsack(prices, pages, x))On the sample input the program prints 13.
The array has 100,001 entries at the limits, and the two loops make at most updates.
On our machine, with Python 3.14, the largest input took about 3.4 seconds against a limit of 1. The same loops written in C++ finished it in well under a second.
Deeper read: the same program with two rows
A version with two arrays is easier to get right, at twice the memory. previous holds row , and current is built from it. Both candidates read previous, which the loop never changes, so the capacities can go in either order:
def knapsack_two_rows(weights, values, capacity):
previous = [0] * (capacity + 1)
for w, v in zip(weights, values):
current = previous.copy()
for c in range(w, capacity + 1):
current[c] = max(previous[c], previous[c - w] + v)
previous = current
return previous[capacity]
print(knapsack_two_rows([2, 3, 4], [4, 5, 7], 5))
print(knapsack_two_rows([4, 8, 5, 3], [5, 12, 8, 1], 10))Prints 9 for the hiker and 13 for the Book Shop sample.
The one-row program saves the copy because it reads every old value before overwriting it.
Deeper read: a bag with two limits
Some problems limit two quantities at once, as this one does:
Given an array strs of binary strings and two integers and , choose as many strings as possible so that together they contain at most zeros and at most ones.
Return the number of strings chosen.
Constraints
-
strs.length - Each string has 1 to 100 characters
Sample 1 · Input
strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output
4
Sample 2 · Input
strs = ["10","0","1"], m = 1, n = 1
Output
2
In this problem and are the two limits, on 0s and on 1s. In the first sample they are 5 and 3. The string "111001" has four 1s, more than the limit of 3, so it cannot be chosen. The other four strings contain exactly five 0s and three 1s between them, so all four fit.
Each string is an item whose value is 1 and whose weight has two parts, its number of 0s and its number of 1s. One capacity no longer describes the room that is left, so the state holds both: dp[z][o] is the largest number of strings, among those considered so far, that can be chosen with at most zeros and at most ones.
This is the Book Shop program with a pair of limits in place of the capacity: dp keeps one entry for each pair, and each string overwrites it in place, as each book overwrote the row. Both loops run from high to low for the same reason as before: the entry that is read, dp[z - zeros][o - ones], must not include the current string yet.
def find_max_form(strs, m, n):
dp = [[0] * (n + 1) for _ in range(m + 1)]
for s in strs:
zeros, ones = s.count("0"), s.count("1")
for z in range(m, zeros - 1, -1):
for o in range(n, ones - 1, -1):
dp[z][o] = max(dp[z][o], dp[z - zeros][o - ones] + 1)
return dp[m][n]
print(find_max_form(["10", "0001", "111001", "1", "0"], 5, 3))
print(find_max_form(["10", "0", "1"], 1, 1))Prints 4 and 2, the two samples.
At the limits there are 600 strings and states, so the loops make at most
The sums a subset can reach
The items so far had a weight and a value, and we asked for the best value. A second kind of knapsack question has weights only. It asks which totals can be made by adding up some of the given numbers.
Given an array nums of positive integers, return true if it can be split into two groups with equal sums, and false otherwise.
Constraints
-
nums.length -
nums[i]
Sample 1 · Input
nums = [1,5,11,5]
Output
true
Sample 2 · Input
nums = [1,2,3,5]
Output
false
In the first sample, and the number left over is 11, so the answer is true. In the second the total is 11, an odd number, so no split into two equal groups exists. When the total is even, a split exists exactly when some subset adds up to half the total, because the numbers outside that subset then add up to the other half.
So the question is whether one particular sum can be reached. Take the numbers one at a time, as we took the items. Let reach[s] be true when some subset of the numbers seen so far adds up to exactly . Before any number is seen, only reach[0] is true, from the empty subset. When the next number arrives, a sum can be made without if it could be made before, and with if could be made before:
reach[s] = reach[s] or reach[s - x]This is the knapsack transition with "at least one of the two" where the maximum was, which is how Word Break combined its candidates. As in Book Shop, it is kept in one row and the sums go from high to low, so that each number is used at most once.
For the first sample, half the total is 11. The rows below show reach at the start and after each number, with a mark on every sum that can be made:
The first 5 adds the sums 5 and . The 11 can only be added to the empty subset, because every other sum would go past 11, the largest sum the row holds. The second 5 adds .
def can_partition(nums):
total = sum(nums)
if total % 2:
return False
half = total // 2
reach = [True] + [False] * half
for x in nums:
for s in range(half, x - 1, -1):
if reach[s - x]:
reach[s] = True
return reach[half]
print(can_partition([1, 5, 11, 5]))
print(can_partition([1, 2, 3, 5]))Prints True and False, the two samples.
At the limits there are 200 numbers of at most 100 each, so the total is at most 20,000 and half of it at most 10,000. The loops make at most
Deeper read: the closest split into two groups
The same reach row solves the next problem, once the problem is restated as a split of the stones into two groups.
You have stones with weights stones[i]. Each turn, pick any two stones with weights and smash them together. If both are destroyed; otherwise the stone of weight is destroyed and the other now weighs . Play until at most one stone is left.
Return the smallest possible weight of the last stone, or 0 if none is left.
Constraints
-
stones.length -
stones[i]
Sample 1 · Input
stones = [2,7,4,1,8,1]
Output
1
Sample 2 · Input
stones = [31,26,33,21,40]
Output
5
Each smash replaces two stones of weights by one stone of weight : the heavier weight with a plus sign and the lighter with a minus sign. On the first sample, if the 7 and the 8 are smashed first, they leave a stone of weight . If that stone is then smashed against the 4, what is left weighs , which is . The new stone was the lighter one, so the signs inside it flipped, and had it been the heavier one they would have stayed as they were. Either way every original weight still appears once, with a plus or a minus sign.
So the weight of the last stone is the sum of the original weights with a plus or a minus sign on each. If the stones with a plus sign form group and the rest form group , the last stone weighs the sum of minus the sum of . A weight is never negative, so this is the larger of the two sums minus the smaller, the difference between them. The last stone therefore cannot weigh less than the smallest difference that any split of the stones into two groups has.
That smallest difference can also be reached. Start from a split that has it. While both groups still have stones, smash a stone of against a stone of and put what is left, if anything, in the group the heavier stone came from. Both sums drop by the weight of the lighter stone, so the difference between them does not change. When one group runs out, the stones in the other add up to exactly that difference. Smashing them against each other leaves at most their sum, and by the argument above it cannot leave less than the smallest difference, so the last stone weighs exactly that.
If the lighter group adds up to and the total is , the difference is . It is smallest when is the largest reachable sum that is at most , and the reach row of Partition Equal Subset Sum holds every reachable sum up to there:
def last_stone_weight_ii(stones):
total = sum(stones)
half = total // 2
reach = [True] + [False] * half
for x in stones:
for s in range(half, x - 1, -1):
if reach[s - x]:
reach[s] = True
best = max(s for s in range(half + 1) if reach[s])
return total - 2 * best
print(last_stone_weight_ii([2, 7, 4, 1, 8, 1]))
print(last_stone_weight_ii([31, 26, 33, 21, 40]))Prints 1 and 5, the two samples.
In the first sample the total is 23, and the sum 11 can be reached as , so the answer is . In the second the total is 151, and the largest reachable sum up to 75 is , which gives . Smashing the two heaviest stones on every turn is not a way to find it: on the second sample that rule ends with a stone of weight 9.
Count the subsets that reach a sum
The third kind of question asks in how many ways a sum can be made. The row stays the same, and its entries become counts.
Given an integer array nums and an integer target, put a + or a - sign in front of every number.
Return how many sign choices make the signed sum equal target.
Constraints
-
nums.length -
nums[i]andsum(nums) -
target
Sample 1 · Input
nums = [1,1,1,1,1], target = 3
Output
5
Sample 2 · Input
nums = [1], target = 1
Output
1
In the first sample exactly one of the five 1s gets a minus sign, and there are five ways to pick which.
A choice of signs is a choice of which numbers get the plus sign, so we can count subsets. Let be the sum of the numbers with a plus sign, the total of all the numbers and the target. The numbers with a minus sign add up to , so the signed sum is . Setting it equal to gives
So the answer is the number of subsets that add up to exactly , which is in the first sample. has to be a whole number from 0 to . When is odd, or lies outside the range from to , no choice of signs works and the answer is 0.
Let ways[s] be the number of subsets of the numbers seen so far that add up to . After a new number , the subsets that make are the ones that made before, which leave out, together with the ones that made before, with added to each. No subset is in both groups, so the counts are added:
ways[s] = ways[s] + ways[s - x]The base case is ways[0] = 1, for the empty subset, and the sums again go from high to low.
def find_target_sum_ways(nums, target):
total = sum(nums)
if abs(target) > total or (total + target) % 2:
return 0
plus = (total + target) // 2
ways = [1] + [0] * plus
for x in nums:
for s in range(plus, x - 1, -1):
ways[s] += ways[s - x]
return ways[plus]
print(find_target_sum_ways([1, 1, 1, 1, 1], 3))
print(find_target_sum_ways([1], 1))
print(find_target_sum_ways([0, 0, 1], 1))Prints 5 and 1 for the samples, then 4 for [0, 0, 1] with target 1.
For the first sample, the row after all five 1s is
and ways[4] is 5. Equal numbers in different positions are different items, which is why the five 1s give five subsets and not one.
A 0 in the input doubles every count, because ways[s] += ways[s - 0] adds each entry to itself. That matches the two signs, and , which both leave the sum unchanged. The third call in the listing has two 0s and prints .
Unlimited copies of each item
In every problem so far, an item could be used at most once. When each item may be used any number of times, the problem is called the unbounded knapsack, and one of the transition's two reads changes.
Given an array coins of distinct coin values and an integer amount, with an unlimited number of each coin, return the number of combinations of coins that add up to amount, or 0 if none does.
A combination ignores order: and are the same combination.
Constraints
-
coins.length -
coins[i] -
amount - The answer fits in a signed 32-bit integer
Sample 1 · Input
amount = 5, coins = [1,2,5]
Output
4
Sample 2 · Input
amount = 3, coins = [2]
Output
0
Sample 3 · Input
amount = 10, coins = [10]
Output
1
The four combinations in the first sample are , , and .
Take the coin values one at a time, and let ways[k][x] be the number of combinations that make the amount from the first coin values only. Look at the last of those values, . A combination either contains no coin of value , or it contains at least one:
- With no coin of value , it is a combination of the first values, and there are
ways[k - 1][x]of those. - With at least one, remove one coin of value . What is left makes and may still contain coins of value , so it is counted by
ways[k][x - d], in the same row.
The second term is left out when . Row 0 has no coin values: ways[0][0] is 1, for the empty combination, and the rest of the row is 0.
Compare this with counting subsets in the previous part, where each number could be used once. There both reads came from the row before the current number. Here the second read comes from row itself. Kept in one row, that read has to see a value this coin has already updated, so the amounts go from low to high. The read that was a bug in Book Shop is the correct one here, because an item may now be added to a selection that already contains it.
def count_combinations(amount, coins):
ways = [1] + [0] * amount
for coin in coins:
for x in range(coin, amount + 1):
ways[x] += ways[x - coin]
return ways[amount]
print(count_combinations(5, [1, 2, 5]))
print(count_combinations(3, [2]))
print(count_combinations(10, [10]))
print(count_combinations(4999, list(range(2, 601, 2))))Prints 4, 0 and 1, the three samples, then 0 for the amount 4,999 with the 300 even coins from 2 to 600.
For the first sample the row starts as a 1 followed by 0s and changes like this:
With 1s alone there is one way to make each amount. Allowing 2s raises ways[4] to 3: four 1s, a 2 with two 1s, or two 2s. The 5 adds one more way to make 5, and the row ends in 4, the expected output.
Combinations and ordered sequences
Coin Change II counts and as one combination because it takes the coin values one at a time. By the time the 2s are considered, every combination already has all of its 1s. Each combination is therefore built in one fixed order, its 1s first and then its 2s, and is counted once.
Swap the two loops, so that the amounts are outside and the coins inside, and every entry tries every coin as the last one added. The program then counts ordered sequences, in which and are different. The Deeper read below works through this on Dice Combinations.
That makes three ways to arrange the loops over a row of capacities or amounts:
- Items outside, capacities from high to low: each item is used at most once.
- Items outside, capacities from low to high: each item is used any number of times, and a count is a count of combinations.
- Capacities outside, items inside: each item is used any number of times, and a count is a count of ordered sequences.
Deeper read: counting ordered sequences
Dice Combinations counts ordered sequences:
Count the ways to make a sum by throwing a die one or more times. Each throw shows a number from 1 to 6, and the order of the throws matters.
Print the count modulo .
Constraints
Sample · Input
3
Output
4
Here and are different. The state is the sum alone, ways[x], and the transition looks at the last throw: it showed some face , and the throws before it add up to , so ways[x] is the sum of ways[x - f] over the six faces. Nothing in the state says which faces were used before, so the same faces in another order are counted again. In the program the amounts are outside and the items inside:
MOD = 10**9 + 7
def count_orders(amount, coins):
ways = [1] + [0] * amount
for x in range(1, amount + 1):
for coin in coins:
if coin <= x:
ways[x] = (ways[x] + ways[x - coin]) % MOD
return ways[amount]
print(count_orders(5, [1, 2, 5]))
print(count_orders(3, [1, 2, 3, 4, 5, 6]))
print(count_orders(50, [1, 2, 3, 4, 5, 6]))Prints 9, then 4, the sample output of Dice Combinations, then 660,641,036.
With the coins 1, 2 and 5, the amount 5 has 9 ordered sequences where it had 4 combinations: now counts three times and four times. The second call uses the six faces of a die as the coins. The third asks for the sum 50, which has 389,043,663,364,337 sequences; the program prints the remainder of that count, because it takes the remainder modulo after every addition, as the problem asks. Without that step the counts for larger sums would overflow a 64-bit integer in C++.
Time and space of knapsack tables
- 0/1 knapsack, full table
time and space - One state per item count and capacity, two candidates each. Needed to walk back to the chosen items.
- 0/1 knapsack, one row
time, space - The same updates in an array of entries: updates and 100,001 entries for the largest Book Shop input.
- Reachable sums and subset counts
time, space - One update per number and per sum up to the target sum .
- Coin Change II
time, space - Each of the coin values sweeps the amounts up to once: updates at the limits.
Every one of these costs contains the capacity or the target itself, so the limits decide whether the table can be used. Before choosing a table over capacities, multiply the number of items by the capacity. Book Shop's fits the time limit in C++. A capacity of does not: a single row would have a billion entries.
With a capacity that large and only a few items, the table is slower than trying every selection. Twenty items have 1,048,576 selections, and the table for them makes updates. With many items and a large capacity, the problem needs different states. Knapsack 2 in the reading list has a capacity of and values of at most 1,000, and its states are total values, each storing the least weight that reaches it.
Common mistakes
Looping the capacities from low to high in a one-row 0/1 knapsack.
- Where it breaks
- One item of weight 2 and value 3 with capacity 4 returns
6:dp[4]readsdp[2], which already holds the item, and packs it twice. The answer is3. - The fix
- Loop the capacities from down to the item's weight. Low to high is right only when items are unlimited, as in Coin Change II.
Putting the amount loop outside the coin loop in Coin Change II.
- Where it breaks
- Coins
[1, 2]and amount 3 return3: and are counted separately, beside . The answer is2. - The fix
- Loop over the coins outside and the amounts inside, so that every combination is built in one order of coin values.
Leaving out the check on the target in Target Sum.
- Where it breaks
- With
nums = [1]and target 2,(1 + 2) // 2rounds down to 1, the program counts the subsets that add up to 1 and returns1. No choice of signs gives 2, so the answer is0. - The fix
- Return 0 when the total plus the target is odd, or when the target lies outside the range from minus the total to the total.
Recall Why not take the items with the best value per kilogram first?
That rule is right when items can be cut into pieces, and it can fail when they cannot. Take a capacity of 4 and three items: one of weight 3 and value 5, and two of weight 2 and value 3 each. The first has the best value per kilogram, against . After it is taken nothing else fits, and the bag is worth 5. The two lighter items together fill the bag and are worth 6.
The table does not commit to an item early. At every capacity it compares taking the item with skipping it, and keeps the better.
Recall Suppose the book shop has unlimited copies of every book. What changes in the Book Shop program, and what does it print for the sample?
Only the direction of the inner loop changes: the capacities go from the book's price up to the budget. Then dp[c - w] may already include the current book, which is what lets it be bought again.
For the sample the program prints 16, from two copies of the book that costs 5 and has 8 pages.