algorithm design techniques empty empty empty figure best fit for notice that the item of size is placed in where it fits perfectlyinstead of one might expect that since we are now making more educated choice of binsthe performance guarantee would improve this is not the casebecause the generic bad cases are the same best fit is never more than roughly times as bad as optimaland there are inputs for which it (nearlyachieves this bound neverthelessbest fit is also simple to codeespecially if an ( log nalgorithm is requiredand it does perform better for random inputs offline algorithms if we are allowed to view the entire item list before producing an answerthen we should expect to do better indeedsince we can eventually find the optimal packing by exhaustive searchwe already have theoretical improvement over the online case the major problem with all the online algorithms is that it is hard to pack the large itemsespecially when they occur late in the input the natural way around this is to sort the itemsplacing the largest items first we can then apply first fit or best fityielding the algorithms first fit decreasing and best fit decreasingrespectively figure figure first fit for