shows that in our case this yields an optimal solution (althoughof coursethis is not true in generalin this sectionwe will deal with first fit decreasing the results for best fit decreasing are almost identical since it is possible that the item sizes are not distinctsome authors prefer to call the algorithm first fit nonincreasing we will stay with the original name we will also assumewithout loss of generalitythat input sizes are already sorted the first remark we can make is that the bad casewhich showed first fit using bins instead of binsdoes not apply when the items are sorted we will show that if an optimal packing uses binsthen first fit decreasing never uses more than ( )/ bins the result depends on two observations firstall the items with weight larger than will be placed in the first bins this implies that all the items in the extra bins have weight at most the second observation is that the number of items in the extra bins can be at most combining these two resultswe find that at most ( )/ extra bins can be required we now prove these two observations lemma let the items have (sorted in decreasing orderinput sizes sn respectivelyand suppose that the optimal packing is bins then all items that first fit decreasing places in extra bins have size at most proof suppose the ith item is the first placed in bin we need to show that si < we will prove this by contradiction assume si it follows that si- since the sizes are arranged in sorted order from this it follows that all bins bm have at most two items each consider the state of the system after the ( - )st item is placed in binbut before the ith item is placed we now want to show that (under the assumption that si the first bins are arranged as followsfirstthere are some bins with exactly one elementand then the remaining bins have two elements suppose there were two binsbx and by such that < <mbx has two itemsand by has one item let and be the two items in bx and let be the item in by > since was placed in the earlier bin >si by similar reasoning thusx > si this implies that si could be placed in by by our assumption this is not possible thusif si thenat the time that we try to process si the first bins are arranged such that the first have one element and the next have two elements to prove the lemma we will show that there is no way to place all the items in binswhich contradicts the premise of the lemma clearlyno two items sj can be placed in one binby any algorithmsince if they couldfirst fit would have done so too we also know that first fit has not placed any of the items of size sj+ sj+ si into the first binsso none of them fit thusin any packingspecifically the optimal packingthere must be bins that do not contain these items it follows that the items of size sj+ sj+ si- must be contained in