%0 Journal Article
%T FFD(L)≤11/9OPT(L)+7/9
%A 李荣珩
%A 越民义
%J 科学通报
%P 1137-1140
%D 1997
%X 一维装箱问题可定义为给定一个代表工件大小的正数表(为方便计pⅰ也表第ⅰ个工件),如何把这些工件装入大小为单位容量的箱子里去,使所用的箱子数最小.FFD(firstfitdecreasing)算法是装箱问题的一个近似算法。FFD算法是指首先按工件大小将工件排队,然后从大的开始装入箱内.不妨设,当装第ⅰ个工件pⅰ时,Bk是下标最小且其中装入的工件的大小总量不超过1-pⅰ的箱子,那么FFD算法就将pⅰ放入箱子Bk中。用FFD(L)表示用FFD装L中的工件所用的箱子数.OPT(L)表示最优装法所用的箱子数,
%K 装箱
%K 最小反例
%K 权函数
%K FFD算法
%U http://csb.scichina.com:8080/CN/abstract/abstract364733.shtml