Python Program for the 0/1 Knapsack Problem

Finds the most value that fits in a bag with a weight limit, taking each item at most once, by filling in a table.

In the 0/1 knapsack problem you have a bag that holds a limited weight and some items, each with a weight and a value. Which items should go in to carry the most value? Each item goes in whole or not at all, which is what the 0/1 means. With a bag that holds 7 and items weighing 1, 3, 4 and 5, worth 1, 4, 5 and 7, the best is the items weighing 3 and 4, worth 9. Taking the most valuable item first, the one weighing 5, gets only 8, as only the item weighing 1 fits beside it. Trying every mix works for 4 items (16 mixes) but not for 50 (2⁵⁰, over a thousand trillion), so the program fills in a table of smaller problems instead: the best value for the first few items and a smaller bag.

Program

def knapsack(weights, values, capacity):
    """The most value that fits, taking each item at most once."""
    n = len(weights)
    # best[i][w]: the most value from the first i items in weight w
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight, value = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            best[i][w] = best[i - 1][w]  # without item i
            if weight <= w:  # with item i, if it fits
                with_item = best[i - 1][w - weight] + value
                best[i][w] = max(best[i][w], with_item)
    return best[n][capacity]


weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print("Best value for capacity 7:", knapsack(weights, values, 7))

Open in the editor Download knapsack.py

Output

Best value for capacity 7: 9

How it works

Visualize Step through the program line by line: each step below shows up as its line runs.

1. n is the number of items, and best is a table with a row for each number of items considered, 0 to 4, and a column for each capacity, 0 to 7. best[i][w] will be the most value the first i items can give in a bag that holds w. Row 0, with no items, stays all 0.
2. The rows are filled one at a time, each adding one item. weight and value are that item's (the lists count from 0, the rows from 1).
3. For each capacity w, one choice is to leave the item out: then the best is what the items before it managed with the same capacity, the cell above.
4. The other choice, if the item fits, is to take it: its value, plus the best the items before it can do in the weight left over, w - weight. The cell keeps the larger of the two.
5. The bottom-right cell, with every item and the full capacity, is the answer.
6. The program packs the four items into a bag that holds 7.

The table, one row per item added:

Take the 9 in the row for the weight-4 item: leaving it out gives 5, the cell above. Taking it leaves room for 3, where the items before it give 4, so 4 + 5 = 9. In the last row, taking the weight-5 item gives 7 plus the 1 that fits in the 2 left over, 8, which is less than the 9 above, so the 9 stays.

Time and space complexity

The table has (n + 1) × (W + 1) cells for n items and a capacity of W, and each cell takes a fixed amount of work, so the time and the space are both O(n × W). That's fast while W is small, but it grows with the capacity's size, not with how many digits it has: a capacity of a million needs a million columns. Each row reads only the row above it, so one row is enough when only the best value is wanted (below): O(W) space.

Other ways to write it

With one row

One list holds the current row, updated in place. Going through the capacities from high to low means best[w - weight] still holds the value from before this item, so each item is taken at most once.

def knapsack(weights, values, capacity):
    best = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for w in range(capacity, weight - 1, -1):
            best[w] = max(best[w], best[w - weight] + value)
    return best[capacity]

print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))

With recursion and lru_cache

Top-down: the best from item i onwards with room left is the better of skipping that item and taking it. lru_cache, a decorator, remembers the answer for each (i, room), so each is worked out once.

from functools import lru_cache

def knapsack(weights, values, capacity):
    @lru_cache(maxsize=None)
    def best(i, room):
        if i == len(weights):
            return 0
        skip = best(i + 1, room)
        if weights[i] > room:
            return skip
        return max(skip, values[i] + best(i + 1, room - weights[i]))

    return best(0, capacity)

print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))

Try it yourself

• Change the capacity to 5, then to 9. The best values are 7 and 12.
• Find which items to take: start at the bottom-right cell and go up a row at a time. Where a cell differs from the one above, that row's item was taken, so take its weight off w. For a capacity of 7 that's the items weighing 4 and 3.
• Print best a row at a time before the function returns, and compare it with the table above.
• Let each item be taken any number of times (the unbounded knapsack): in the one-row version, go through the capacities from low to high. With a capacity of 10 it takes the weight-5 item twice, for 14, where the 0/1 answer is 13.

More dynamic programming programs

• Python Program for the Coin Change Problem (Minimum Coins) Intermediate
• Python Program for Fibonacci Using Memoization Intermediate
• Python Program for the Longest Common Subsequence (LCS) Advanced