Further packing and the knapsack problem

The knapsack problem as an integer programme

Bin packing hands over the whole list of items and asks for the fewest bins. The knapsack problem puts a different question to a single container. Each item carries a mass and a profit, the container has a stated limit on the mass it will hold, and the load has to stay inside that limit while earning as much as it can. Items are left behind, and deciding which ones is the problem.

It is an optimisation question, and it has the shape a linear programme has: something to maximise, and a restriction that stops it running away. Writing it out in that shape before choosing a method fixes the objective and the constraint explicitly.

One instance runs through the first three sections. A stall holder has a barrow that carries 10 kg and five crates to choose between.

Give crate i a variable x_i that takes the value 1 when the crate is loaded and 0 when it is left on the ground. The whole problem then goes onto four lines.

Every line but the last is linear, so this is a linear programme wearing one extra condition, and branch and bound, which this unit meets later, is one way at it. That last line is what makes the problem hard. With n items there are 2ⁿ subsets to choose between, which is 32 here and over a million at twenty items, so inspecting them all is an exponential method.

Loading by profit per kilogram

The greedy rule ranks the crates by profit per kilogram, which is also called the value density, and works down the ranking loading each crate that still fits. It costs one division per item and one sort, and it decides each crate without looking at what is left.

On these five the ranking is A at £8.00 per kg, B at £7.50, C at £7.20, E at £7.00 and D at £6.67. So A goes in, using 3 kg of the 10; B goes in, taking the load to 7 kg; and C, E and D each need more than the 3 kg still free. The barrow leaves with £54 aboard and 3 kg of room unused. It is not the best load.

Swapping to another greedy rule is not a cure. Loading the most profitable crate first takes E and then A, which reaches £73 on this list and happens to be the best there is; on the list in the exercise below the same rule falls short. A heuristic that lands on the best answer for one instance has not been shown to be reliable, any more than first fit decreasing was by meeting the lower bound on one set of items.

An upper bound from fractional loading

The same ranking supplies a ceiling, and it costs nothing beyond the division already done. Drop the whole-crate condition, allow a crate to be split, and load in density order until the limit is reached. Splitting a crate widens the choice rather than narrowing it, so the fractional profit is at least the best whole-crate profit and is therefore an upper bound on it.

On the five crates: 3 kg of A at £24, then 4 kg of B at £30, then 3 of C's 5 kg, worth 3 × £7.20 = £21.60, for £75.60 in all. A whole-crate total is a whole number of pounds here, so the bound tightens to £75. Together with the greedy load of £54 that brackets the answer before any table is drawn, and the £2.60 between £73 and £75.60 is what the whole-crate condition costs.

Dynamic programming for the knapsack problem

An exact answer needs a method that looks ahead, and the standard one is dynamic programming, worked here as a table. Write V(i, w) for the largest profit reachable from the first i crates alone under a limit of w kilograms. The table carries a row for each i and a column for each whole-number limit from 0 up to the real one.

One decision sits behind each cell. Crate i is either left, in which case the profit is V(i − 1, w), or loaded, which uses m_i kilograms and pays p_i, leaving V(i − 1, w − m_i) to be earned from the crates before it. So V(i, w) is the larger of those two. Where m_i is above w the second option is not open, and the cell copies the one above it.

The principle underneath that line is the one dynamic programming rests on. Whatever the best load does about crate i, what it does with the crates before i has to be the best use of the room they were left, or the load could be improved without touching crate i. That is why one comparison per cell is enough.

The top row is nought all the way across, since a choice made from no crates at all gives a profit of zero, and each later cell is one comparison away from cells already written down. Filling the rows in turn, left to right, completes the table with no searching at all.

The table here is 5 rows by 11 columns, so 55 cells against 32 subsets, and on a problem this small it saves nothing. The saving arrives with size, because the work goes as the number of items times the limit rather than as 2ⁿ: twenty crates under the same 10 kg limit need 220 cells where the subsets number 1 048 576. The catch is the limit itself. A barrow rated in grams has the same crates and a table a thousand times as wide, so the method is quick in the number of items and slow in the size of the limit.

Packing in two dimensions

Bin packing and the knapsack both run along one dimension: an item has a size, and sizes add. Cutting shapes from a sheet does not behave that way. A set of rectangles has to be laid on a roll of fixed width without overlapping and without being turned, and what has to be made small is the length of roll used. Two sets of the same total area can leave very different amounts of the roll unusable, so the sizes no longer simply add.

Shelf packing is the standard heuristic, and it turns the problem back into one dimension. Sort the rectangles by decreasing height. Lay them along the bottom of the roll, left to right, while the width allows; when the next one will not fit, close that shelf at the height of its tallest rectangle and start a fresh shelf on top. That is first fit decreasing with a second measurement attached, and it inherits the speed along with the weakness.

The bound comes from area rather than from length. The rectangles cover a fixed area, and the roll they lie on is a rectangle of known width, so the length used is at least the total area divided by the width. It is also at least the height of the tallest piece. Reach either figure and the packing is settled, in the same way a packing meeting the bin-packing lower bound finishes that question.

Three dimensions changes the arithmetic and little else. Boxes go into a container, the heuristic fills one layer at a time, and the bound is the total volume divided by the area of the base.