Dynamic programming 0/49

Knapsack DP: capacity tables and grid paths · 2 of 2

Knapsack

Choose items under a weight limit with a state for the items considered and the capacity, keep one row of the table, and reuse it for reachable sums, counts and unlimited copies.

5,318 words · 24 min read

Part 1 of 9 0/1 knapsack

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:

The hiker can take at most one of each item
ItemWeightValue
Tent2 kg4
Stove3 kg5
Camera4 kg7

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 4+5=94 + 5 = 9, which is the best that fits.

This is the knapsack problem. There are nn 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 nn items have 2n2^n selections. That is 8 for the hiker, 1,048,576 for 20 items, and a number 31 digits long for 100 items.