30.4 The 0/1 knapsack problem: which order?¶
Part 4 · Heuristic algorithms · Chapter 30 · Chapter 30: Constructive heuristics · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Constructive heuristics · App: Bin packing heuristics · App: List scheduling and LPT · App: Vertex coloring: greedy and DSATUR · App: TSP: nearest neighbour and 2-opt
- For the KP the elements are the items, and the feasibility test is the capacity constraint: an item is selected if its weight does not exceed the residual capacity \(rc\). Since the test is fixed, a greedy heuristic for the KP is completely determined by the order in which the items are examined. Three orders are natural:
| by profit (\(GR_{p}\)): | non-increasing \(p_j\) | most valuable items first |
|---|---|---|
| by weight (\(GR_{w}\)): | non-decreasing \(w_j\) | as many items as possible |
| by efficiency (\(GR\)): | non-increasing \(\dfrac{p_j}{w_j}\) | best value per unit of weight |
Ties are broken in favour of the item with the smallest index.
- The greedy by efficiency is denoted by \(GR\); here we compare it with the other two orders.
The greedy algorithm with order \(\rho\) is a constructive heuristic for the KP. It examines the items in the order \(\rho=(\rho_1,\dots,\rho_n)\), a permutation of \(\mathscr{I}\), starting from the empty knapsack, and selects each item if and only if it fits into the residual capacity.
Algorithm: Greedy with order
- The three heuristics differ only in the order \(\rho\), computed once by sorting the items in \(O(n\log n)\) time. Each criterion captures one aspect of a good solution and ignores the other: the profit ignores how much capacity an item consumes, the weight ignores how much an item is worth, and the efficiency balances the two, but ignores how well the items fill the knapsack.
Example 30.1: Three orders on the KP reference instance
On the KP reference instance (\(c=9\)) the three orders are
| criterion | values | order \(\rho\) |
|---|---|---|
| profit | \(p=(10,7,6,4)\) | \((1,2,3,4)\) |
| weight | \(w=(5,4,3,3)\) | \((3,4,2,1)\) |
| efficiency | \(\frac{p}{w}=\left(\frac{10}{5},\frac{7}{4},\frac{6}{3},\frac{4}{3}\right)=(2,\,1.75,\,2,\,1.33)\) | \((1,3,2,4)\) |
(items \(3\) and \(4\) have the same weight, items \(1\) and \(3\) the same efficiency, and the ties are broken by the index). The executions, with the residual capacity after each step, are:
| step 1 | step 2 | step 3 | step 4 | |
|---|---|---|---|---|
| \(GR_p\) | item \(1\): in, \(rc=4\) | item \(2\): in, \(rc=0\) | item \(3\): out | item \(4\): out |
| \(GR_w\) | item \(3\): in, \(rc=6\) | item \(4\): in, \(rc=3\) | item \(2\): out | item \(1\): out |
| \(GR\) | item \(1\): in, \(rc=4\) | item \(3\): in, \(rc=1\) | item \(2\): out | item \(4\): out |
Hence
The greedy by profit finds the optimal solution \(\{1,2\}\), which fills the knapsack exactly; the greedy by efficiency, after items \(1\) and \(3\), is left with \(rc=1\), too little for any other item; the greedy by weight takes the two light items, which are also the least valuable ones.
-
On this instance the “naive” criterion wins. This is not a general rule: no order is the best on every instance, and each of the three orders can be arbitrarily bad. Let \(c\ge 3\):
-
profit: one item with \(p_1=2\), \(w_1=c\) and \(c\) items with \(p_j=1\), \(w_j=1\). \(GR_p\) takes item \(1\), which fills the knapsack: \(GR_p(I)=2\), while the \(c\) light items together give \(z(I)=c\);
-
weight: two items with \(p_1=1\), \(w_1=1\) and \(p_2=c\), \(w_2=c\). \(GR_w\) takes item \(1\) and item \(2\) no longer fits: \(GR_w(I)=1\), while \(z(I)=c\);
-
efficiency: two items with \(p_1=2\), \(w_1=1\) and \(p_2=c\), \(w_2=c\): here \(GR(I)=2\) and \(z(I)=c\).
In all three cases the ratio \(\frac{z(I)}{\mathscr{A}(I)}\) grows with \(c\).
-
-
A remedy is to combine two solutions: the Ext-Greedy algorithm \(GR^e\) returns the better of the solution of \(GR\) and of the best single item, and this simple combination guarantees \(\frac{z(I)}{GR^e(I)}\le 2\). Running several greedy heuristics and keeping the best solution is a general and cheap way to protect against the weakness of each single criterion.