- Being filled
- Read from
- Answer
Knapsack problem
You can carry only so much weight, and every item has a weight and a value. Which items do you take to carry the most value? Trying every combination doubles the work with each item. A table of item rows and capacity columns finds the best bag one cell at a time. Tap an item to put it in the bag, and tap it again (in the bag or on the shelf) to take it out. The bag fills up by weight, and the tiles show the dollars you packed against the best possible. Press Best packing to see the best bag. Change the items' kilograms and dollars, add or remove items, and set the bag capacity in the panel. The Table view shows how dynamic programming finds the best bag: press Play to watch the table fill, or Step and Back to go one step at a time, and drag the step slider to jump anywhere. Each row adds one item, each column is a capacity in kilograms, and each cell holds the most dollars that fit. With the table selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Tap the item boxes to pack them into the bag, and watch it fill up by weight in kilograms.
- Try to reach the best possible value in dollars, or press Best packing to see the best bag.
- Open the Table view and press Play to watch each cell choose between packing and leaving an item.
How the table works
Each row adds one item and each column is a capacity from 0 up to the bag's. A cell holds the most value that fits in that capacity using the items up to its row. Without the new item, that is the cell above. With it, if it fits, it is the item's value plus the best value for the weight that is left, which is in the row above, the item's weight to the left. The cell keeps the larger of the two. The first row, with no items, is all zeros.
Reading back the items
The bottom right cell is the best value. To find the items, start there and compare it with the cell above: if it is the same, the last item was not needed; if it is bigger, the item is in the bag, so subtract its weight and move to that column. Go up one row each time until the first row. The app shows this read-back in orange and lists the packed items under the table.
Frequently asked questions
What does 0/1 mean in the 0/1 knapsack problem?
Each item is packed once or not at all, never in part and never twice. If items could be cut, like grains of rice, packing the best value per weight first would be optimal; that is the fractional knapsack problem.
Why not pack the best value per weight first?
Because whole items can leave gaps. With a capacity of 7 and items of weight 1, 3, 4 and 5 worth 1, 4, 5 and 7, the best value per weight is the item of weight 5, which leaves room only for the item of weight 1, for a total of 8. The items of weight 3 and 4 together are worth 9.
How fast is the knapsack algorithm?
The table has (number of items + 1) times (capacity + 1) cells, each filled in one step. That is fast for small capacities, but a capacity can be a huge number, so the problem is NP-hard in general; the table method is called pseudo-polynomial.
Can the same item be packed twice?
Not here. In the unbounded knapsack problem each item can be taken any number of times; the table then reads the cell to the left in the same row instead of the row above, as in the coin change app.
Is anything sent anywhere?
No. Everything is worked out in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor