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

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