236 OTHER ALGORITHMIC TECHNIQUES
first fit, we will use the optimal three bins. If we sort first, we get the list (0.8,
0.6, 0.5, 0.3, 0.2, 0.2, 0.2, 0.2). When we do the first fit algorithm with this
new list, we get bins of [0.8, 0.2], [0.6, 0.3], [0.5, 0.2, 0.2], and [0.2], which is
1 more than optimal.
Analysis has shown that this decreasing first fit technique will require
approximately 50% more than the optimal number of bins. This means that if
some set of input requires 10 bins in the optimal case, this algorithm will pro-
duce a result that will likely need 15 bins. First fit without sorting has been
shown to need about 70% more than the optimal number of bins, or about 17
bins if optimal is 10 bins.■ 9.1.3 Backpack Approximation
The backpack approximation algorithm is a simple greedy algorithm that is
based on the worth ratio of the items. We create a sorted list of the items based
on the ratio of the worth to the item size. We represent each item as a pair
[size, worth]. If we had the list of items of ([25, 50], [20, 80], [20, 50], [15, 45],
[30, 105], [35, 35], [20, 10], [10, 45]), they would have worth ratios of (2, 4,
2.5, 3, 3.5, 1, 0.5, 4.5). Sorting by the worth ratios would put our items in the
order ([10, 45], [20, 80], [30, 105], [15, 45], [20, 50], [25, 50], [35, 35],
[20, 10]). We now begin filling the backpack using the items in the order of
this list. If the next item will not fit, we skip it and continue down the list until
the backpack is full or we have passed through the entire list. So, if we have a
backpack of size 80, we would be able to put in the first four items for a total
size of 75 and a total worth of 275. This is not, however, optimal, because
using the first three items and the fifth item would give a total size of 80 and a
total worth of 280.■ 9.1.4 Subset Sum Approximation
In the backpack problem, if you set the worth of each item to be the same as
its size, the resulting problem is the same as the subset sum problem. This
means that the greedy algorithm described there could also be used here. In
each case, the worth ratio would be 1, so the sorting method could put the
items in order of decreasing size.
There is an alternative algorithm for the subset sum approximation that has
some of the flavor of a greedy algorithm. In this alternative, we have an algo-
rithm that will be able to do better the longer it is run and will be optimal if,
for a set of N numbers, we can run it for all N + 1 passes. This is because each