算法高级教程3.5Thebinpackingproblem.pptVIP

The bin packing problem The bin packing problem For n objects with sizes s1, …, sn where 0 si≤1, find the smallest number of bins with capacity one, such that n objects can be packed into bins. or find a minimum set partition such that the sum of objects in every set is less than 1. Can we partition n objects into two sets such the sum of objects in one set is equal to that of objects in another set? The First Fit Strategy Place the next object in the list S into the first bin which has not been completely filled into which it will fit. When bins are filled completely they are closed and if an object will not fit into any currently open bin, a new bin is opened. The First Fit Decreasing Strategy First sort the objects in decreasing order of sizes and then run the FF algorithm BinPackFirstFit(S, n, bin) 1 initialize all b[j] as 0.0 // space used up in bin j 2 for i←1 to n do 3 for j←1 to n do 4 if b[j]+s[i]≤1.0 then 5 B[i]← j 6 b[j]← b[j]+s[i] 7 break 8 j←1 9 while (b[j]!=0) do 10 j← j+1 11 return For example, given objects 0.4, 0.2, 0.4, 0.8, 0.2, 0.2, 0.5, 0.3. FFD sorts them in decreasing order 0.8, 0.5, 0.4, 0.4, 0.3, 0.2,0.2, 0.2 and then allocates to the first bin that fits 0.8 0.2 0.5 0.4 0.2 0.2 0.4 0.3 Note that this is not optimal: the objects would fit into 3 bins. Lemma Let S = (s1, …, sn) be an input I, in non-increasing order, for the bin packing problem and let OPT(I) be the optimal number of bins for S. All of the objects placed by FFD in extra bins (i.e., bins with index larger than OPT(I)) have size at most 1/3. Proof Let i be the index of the first object placed by FFD in bin OPT(I)+1. Si must be no larger than 1/3. Suppose Si 1/3. Then S1 ,…, Si-1 1/3, and are placed in bins Bj for 1≤j≤OPT(I), at most two objects each bin. For some k ≥ 0,the first k bins hold one object each, and bins Bk+1, …, BOPT hold two objects each. Si 1/3 can not fit even by an