algorithm design techniques some set of binsand from previous considerationsthe total number of such items is ( the proof is completed by noting that if si there is no way for si to be placed in one of these bins clearlyit cannot go in one of the binssince if it couldthen first fit would have done so too to place it in one of the remaining bins requires distributing ( items into the bins thussome bin would have to have three itemseach of which is larger than clear impossibility this contradicts the fact that all the sizes can be placed in binsso the original assumption must be incorrect thussi < lemma the number of objects placed in extra bins is at most proof assume that there are at least objects placed in extra bins we know that = si <msince all the objects fit in bins suppose that bj is filled with wj total weight for < < suppose the first extra objects have sizes xm thensince the items in the first bins plus the first extra items are subset of all the itemsit follows that = si > wj = xj > = (wj xj = now wj +xj since otherwise the item corresponding to xj would have been placed in bj thus = si > = but this is impossible if the items can be packed in bins thusthere can be at most extra items theorem let be the optimal number of bins required to pack list of items then first fit decreasing never uses more than ( )/ bins proof there are at most extra itemsof size at most thusthere can be at most ( )/ extra bins the total number of bins used by first fit decreasing is thus at most ( )/ <( )/ it is possible to prove much tighter bound for both first fit decreasing and next fit decreasing recall that first fit packed these elements into bins and placed two items in each bin thusthere are ( jitems