FFD(L)≤11/9OPT(L)+7/9

一维装箱问题可定义为给定一个代表工件大小的正数表(为方便计pⅰ也表第ⅰ个工件),如何把这些工件装入大小为单位容量的箱子里去,使所用的箱子数最小.FFD(firstfitdecreasing)算法是装箱问题的一个近似算法。FFD算法是指首先按工件大小将工件排队,然后从大的开始装入箱内.不妨设,当装第ⅰ个工件pⅰ时,Bk是下标最小且其中装入的工件的大小总量不超过1-pⅰ的箱子,那么FFD算法就将pⅰ放入箱子Bk中。用FFD(L)表示用FFD装L中的工件所用的箱子数.OPT(L)表示最优装法所用的箱子数,