Fitting the most value into the bag

You have a bag that holds a total weight of capacity, and a set of items each with a weight and a value. Each item may be taken once or not at all, and cannot be broken up. Report the greatest total value that fits.

Worked example#

Weights [1, 3, 4, 5], values [1, 4, 5, 7], capacity 7.

Taking items 2 and 3 (weights 3 and 4) uses exactly 7 and gives 4 + 5 = 9. Taking items 2 and 4 (weights 3 and 5) is 8, too heavy. So the answer is 9.

Why greedy fails#

The obvious instinct is to sort by value per unit of weight and take the best first. Here item 4 has the best ratio, 7 over 5, so greedy takes it, has 2 left, and can only add item 1, for a total of 8.

Nine was available. Greedy fails because the last space in the bag is wasted, and no local ratio can see that coming.

(Greedy is correct if items can be cut up, because then no space is ever wasted. That is the fractional knapsack, and the difference between the two is worth remembering: whether a thing can be divided changes which technique applies.)

The table#

For each item, and each amount of room, the question is: take it or leave it?

best[room] = max(
    best[room],                                  # leave it
    best[room - weight[i]] + value[i]            # take it
)

best[room] means the most value that fits in that much room, using the items considered so far.

The backwards loop, again#

Walk room downwards for each item:

for each item i:
    for room from capacity down to weight[i]:
        best[room] = max(best[room], best[room - weight[i]] + value[i])

Going upwards, best[room - weight[i]] might already include item i, added earlier in this same pass, so the item would be taken twice. That turns this into the unbounded knapsack, where repeats are allowed, which is a real and different problem.

One character of direction is the entire difference between "each item once" and "each item as often as you like". If you take nothing else from this page, take that.

What it costs#

Items times capacity, and one array of capacity + 1 numbers. Note that the cost depends on the capacity number, not on how many digits it has, which is why a capacity of a billion would be hopeless even with only ten items.

Constraints#

• 1 <= n <= 200
• 1 <= capacity <= 10000
• weights and values between 1 and 1000