How to use the knapsack optimizer
- Enter the weight limit of your bag, truck or budget, in the same unit as the item weights.
- List each item with its value, its weight and how many copies are available.
- Weights and the limit can have up to two decimals. Value is whatever number you choose, such as usefulness or price.
- Read the best total value, the weight used and the list of what to take, and compare with the simple rule of taking the best value per weight first.
Formula
best(w) = the largest value that fits in weight w
for each unit of an item with weight p and value v: best(w) = max(best(w), best(w - p) + v), taking w from the limit downward
weights are scaled to whole numbers first (for example x 100 for two decimals)
the answer is best(limit), and the items are read back from a record of which choices were made
This dynamic programming method gives the true best total. Taking the best value per unit of weight first is faster to do by hand but is not always optimal.
Packing a 15 kilogram bag
Water has value 9 and weight 5, a camera 8 and 2.5, a tent 12 and 6, a stove 6 and 3, snack bars 2 and 0.5 each with 4 available, and a jacket 7 and 2. With a limit of 15, the best set is the camera, tent, stove, jacket and 3 snack bars, with a total value of 39 and a weight of exactly 15. Water stays behind.
Taking items by best value per kilogram first, which is snack bars, jacket and camera, then the tent, reaches only 35 and leaves 2.5 kilograms unused. With the limit set to 1, the best is two snack bars for a value of 4. Trying every combination of the items confirms 39 as the maximum.
Why the simple rule can fail
Ranking items by value per unit of weight and filling the bag in that order feels natural, but a big item that fits exactly can beat several small ones that leave awkward gaps. The exact method looks at every capacity from zero up to the limit, so it never leaves a better combination unseen.
Using the answer
Several different sets can tie for the best value, and the tool shows one of them. If one item is a must-have, give it a very large value, or reduce the limit by its weight and remove it from the list. For loading a vehicle by volume instead, see the Moving Truck Size Calculator, and for scoring options against several criteria the Decision Matrix Calculator.
More planning and optimization tools
For related planning and optimization problems, try the Assignment Optimizer, Shortest Route Calculator and Linear Programming Solver.
Assumptions and limits
- Each copy of an item is either taken or left, and a copy cannot be split.
- Weights and the limit have at most two decimal places, and values can be any non-negative number.
- There are at most 400 copies in total and the scaled limit is at most 200,000.
- Example items are shown until you replace them.
Frequently asked questions
What is the knapsack problem?
It asks which items to pack to get the most total value without exceeding a weight limit. Each item has a value and a weight, and the best choice is not always obvious.
Is taking the best value per weight first optimal?
Not always. It is optimal only if items can be split. With whole items it can leave unused capacity that a different combination would fill, as in the packing example here.
Can I use more than one copy of an item?
Yes. Set the copies available for an item, and the tool treats each copy as a separate choice up to that many.
What can value stand for?
Anything you can rank by a number: usefulness, price, points, or priority. The tool maximizes the total of whatever you enter.