The Knapsack Problem

The knapsack problem is a classic problem that is simple to explain but surprisingly tricky to solve well. It's all about making the best choice when you have limited space and too many things to choose from.

Imagine you're packing a knapsack (or backpack) for a trip. The knapsack can only carry a limited weight and you have a pile of items to choose from. Each item has its own weight and its own value. You can't take everything, so the goal is to pick the items that give you the highest total value without going over the weight limit.

• Items: each one has a weight and a value.
• Capacity: the maximum total weight the knapsack can carry.
• Goal: get the highest total value without going over the capacity.

A small example #

Let's say the knapsack can carry a maximum weight of 7 and there are four items to choose from.

An obvious approach is to pick the items that give the most value for their weight first. Item D has the best ratio (7 value for 5 weight) so that goes in first. That leaves room for 2 more weight so the only thing that fits is item A. The total value is 7 + 1 = 8.

But the best answer is actually B and C. Their weight adds up to exactly 7 and their value is 4 + 5 = 9. So picking the best looking item each time doesn't always give the best result which is what makes this problem interesting. A choice that looks great early on can leave you without enough room for a better combination later.

Solving it #

You could try every possible combination of items and see which one is best, but the number of combinations doubles with every item added. This is fine for four items but it becomes way too slow with a large number of items.

A better way is to use dynamic programming. The idea is to solve smaller versions of the problem first and reuse those answers instead of working them out again and again. We can build a table where each cell stores the best value we can get using the first i items with a capacity of w. For each item, there are only two options: leave it out or take it (if it fits) and add its value to the best result we had with the remaining capacity.

def knapsack(weights, values, capacity):
    n = len(values)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                # Take the best of leaving the item out or putting it in
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                # The item is too heavy so we have to leave it out
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

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

Running it with the items above gives us 9 which matches what we found by hand. The table has one row per item and one column per capacity so the amount of work depends on both the number of items and the capacity.

Where this shows up #

The same idea applies to plenty of other situations where something limited has to be shared out, such as choosing which projects to fund with a fixed budget, or deciding which files to fit onto a disk of limited size. Each project or file has a cost (weight) and a benefit (value) and the aim is to get as much benefit as possible out of what you have.