9.1 GREEDY APPROXIMATION ALGORITHMS 235■ 9.1.2 Bin Packing Approximations
One technique to approximate the bin packing problem is to use the first fit
strategy. This strategy will, for each item, look at the bins in order until one is
found that has enough space to hold the item. If we have a set of items with
sizes of (0.5, 0.7, 0.3, 0.9, 0.6, 0.8, 0.1, 0.4, 0.2, 0.5), how would the bins be
packed using this strategy? You should have found that the bins would be
packed so that bin 1 would have [0.5, 0.3, 0.1], bin 2 would have [0.7, 0.2],
bin 3 would have [0.9], bin 4 would have [0.6, 0.4], bin 5 would have [0.8],
and bin 6 would have [0.5]. You should see that this is not optimal because we
could have five bins with [0.9, 0.1], [0.8, 0.2], [0.7, 0.3], [0.6, 0.4], and [0.5,
0.5]. The algorithm for first fit would be
FirstFit( size, N, bin )
size the list of item sizes
N the number of items
bin the location for each item
for i = 1 to N do
binUsed[i] = 0
end do
for item = 1 to N do
binLoc = 1
while used[binLoc]+size[item] > 1 do
binLoc = binLoc + 1
end while
bin[ item ] = binLoc
used[ binLoc ] = used[ binLoc ] + size[ item ]
end for
Another version of this would be a decreasing first fit, where the items are
first sorted in decreasing order and then we begin the first fit process.^2 The
reader should be able to show that this would give the optimal answer for the
previous set of items. This will not, however, always do better than regular first
fit. Consider the set of items (0.2, 0.6, 0.5, 0.2, 0.8, 0.3, 0.2). With the regular
(^2) This is really nonincreasing, because we do not require that the sizes of the objects be
distinct. The analysis literature is split between whether to call this decreasing first fit or
nonincreasing first fit.