0/1 Knapsack Problem
You have n items. Item i weighs weights[i] and is worth values[i]. Your bag carries a total weight of at most capacity. Each item exists once, and you either pack it whole or leave it behind. Return the largest total value you can pack.
Function
- weightsinteger-array
- the weight of each item
- valuesinteger-array
- the value of each item
- capacityinteger
- the most weight the bag can carry
- Returnsinteger
- the largest total value of items whose weights fit within capacity
Constraints
1 ≤ n ≤ 100, wheren = weights.length = values.length1 ≤ weights[i] ≤ 10001 ≤ values[i] ≤ 1041 ≤ capacity ≤ 1000
Examples
- Input
- weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
- Output
- 17
- Explanation
- Items 0 and 2 weigh 4 + 3 = 7 and are worth 10 + 7 = 17. Packing the most valuable item first (weight 5, value 12) leaves room for item 1 only, for 16.
- Input
- weights = [5, 4, 3]values = [10, 7, 6]capacity = 7
- Output
- 13
- Explanation
- Items 1 and 2 weigh 4 + 3 = 7 and are worth 7 + 6 = 13. Item 0 earns 2 per unit of weight, as much as any item, but after it the 2 units left fit nothing.
- Input
- weights = [6, 8]values = [5, 9]capacity = 5
- Output
- 0
- Explanation
- Both items weigh more than 5, so nothing fits and the empty bag is worth 0.
Follow-up
Suppose the capacity can reach 10^9 while the values add up to at most 10^4. What would you index the table by?
Hints
Open them one at a time. Each one gives away a little more.
Decide the items in order, starting with item 0. Whether you pack it or leave it, you face the same question about the items after it. Which number in that question changes?
The best value from here on depends on two numbers only: which item you are looking at and how much room is left. With 100 items and a capacity of 1000 there are about 10^5 such pairs, so you can work out each one once and store it.
Keep
best[c]for every capacitycfrom 0 tocapacity, all 0 at the start. For an item of weightwand valuev, walkcfromcapacitydown towand keep the larger ofbest[c]andbest[c-w] + v. Going down stops the item from being packed twice.
Solution
No greedy order works: packing the most valuable item first gets 16, not 17, on the first example. The best value from item i on depends only on i and the room left, a whole number up to 1000. One table cell per pair gives O(n × capacity), and one row is enough if you walk the capacities downward.
Try both choices for every item
Correct, but does not finish on the largest tests
Intuition
Let best(i, room) be the most value items i onward can add with room units free; past the last item it is 0. Skipping item i gives best(i+1, room). Packing it, when weights[i] ≤ room, gives values[i] + best(i+1, room-weights[i]). Keep the larger. Every packing that fits is one sequence of pack and skip choices, and the recursion tries them all.
Each item doubles the paths. When all 100 items fit together, as with weight 10 each in a bag of 1000, that is 2^100 paths.
Algorithm
- Write
best(i, room); return 0 wheniis past the last item. - Set
skiptobest(i+1, room). - If
weights[i] > room, returnskip. - Otherwise return the larger of
skipandvalues[i] + best(i+1, room-weights[i]). - Return
best(0, capacity).
def knapsack(weights, values, capacity):
n = len(weights)
# The most value items i, i+1, ... can add with room units of weight left
def best(i, room):
if i == n:
return 0
skip = best(i + 1, room)
if weights[i] > room:
return skip
take = values[i] + best(i + 1, room - weights[i])
return max(skip, take)
return best(0, capacity)Fill a table by item and capacity
Intuition
The recursion reaches the same pair (i, room) along many paths. There are at most 101 × 1001, about 10^5, pairs, so compute each one once.
Let best[i][c] be the most value the first i items can put in a bag of capacity c; row 0 is all 0. For item i-1 with weight w and value v, leaving it out gives best[i-1][c], and packing it, when w ≤ c, gives best[i-1][c-w] + v. Row i reads only row i-1, so each item enters a cell at most once.
On the first example, item 2 (weight 3, value 7) lifts capacity 7 to best[2][4] + 7 = 17. Item 3 then offers only best[3][2] + 12 = 16, so the answer stays 17.
Algorithm
- Make a table of n+1 rows and capacity+1 columns, all 0.
- For each row
ifrom 1 to n, takew = weights[i-1]andv = values[i-1]. - For each capacity
c, setbest[i][c]tobest[i-1][c]. - If
w ≤ candbest[i-1][c-w] + vis larger, store that instead. - Return
best[n][capacity].
def knapsack(weights, values, capacity):
n = len(weights)
# best[i][c]: the most value from the first i items within capacity c
best = [[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):
best[i][c] = best[i - 1][c] # leave item i-1 out
if w <= c and best[i - 1][c - w] + v > best[i][c]:
best[i][c] = best[i - 1][c - w] + v # put it in
return best[n][capacity]One row, capacities walked downward
Intuition
Row i needs only row i-1, so keep one row best[c] and overwrite it item by item. The direction of the walk decides whether the answer is right.
Walking c upward, best[c-w] may already include the current item. One item of weight 3 and value 5 with capacity 6 makes capacity 3 worth 5, then capacity 6 reads it and becomes 10: two copies. Walking downward from capacity to w, the cell you read lies below the one you write and is overwritten later, so it still holds the previous row's value.
The upward walk is the right loop when items come in unlimited copies. Here the time stays O(n × capacity) and the memory drops to one row.
Algorithm
- Make
bestwithcapacity + 1entries, all 0. - For each item with weight
wand valuev, walkcfromcapacitydown tow. - If
best[c-w] + vbeatsbest[c], store it inbest[c]. - Return
best[capacity].
def knapsack(weights, values, capacity):
# best[c]: the most value from the items seen so far within capacity c
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
# Walk the capacities downward so each item goes in at most once
for c in range(capacity, w - 1, -1):
if best[c - w] + v > best[c]:
best[c] = best[c - w] + v
return best[capacity]
Pitfalls and edge cases
- Walking the capacities upward in the one-row version packs an item twice: one item of weight 3 and value 5 in a bag of 6 scores 10 instead of 5.
- A row of
capacityentries instead ofcapacity + 1. Returningbest[capacity-1]then loses any packing that fills the bag exactly, such as weight 1 in a bag of 1. - Starting entries at minus infinity. The bag need not be full, so every entry starts at 0; with minus infinity the third example returns minus infinity instead of 0.
- An item heavier than the bag must be skipped. In the third example a closed range
w...capacitystops the program in Swift, and(w+1):(capacity+1)counts backward in R.
Frequently asked questions3
What is the time complexity of the 0/1 knapsack problem?
The table runs in O(n × capacity) time, about 10^5 steps for 100 items and a capacity of 1000, and the one-row version uses O(capacity) memory. The bound is pseudo-polynomial: it grows with the capacity's value, not its number of digits. The general problem is NP-hard.
Why does a greedy algorithm not work for the 0/1 knapsack problem?
A greedy rule never undoes a choice, even when the item leaves room nothing fills. With capacity 7, the item of weight 5 and value 10 ties for the best ratio, yet the items of weight 4 and 3 together are worth 13. Greedy by ratio is optimal only for the fractional knapsack, where you can cut items.
How do you find which items the 0/1 knapsack picked?
Keep the full table and walk back from best[n][capacity]. If best[i][c] differs from best[i-1][c], item i-1 was packed, so record it and subtract its weight from c. Otherwise move to row i-1 with the same c.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def knapsack(weights, values, capacity):
# Write code hereTest #1
Test #2
Test #3
Arguments
weights = [4, 2, 3, 5] values = [10, 4, 7, 12] capacity = 7
Expected Output
17