%0 Journal Article
%T FFD(L)≤11/9OPT(L)+7/9
%A 李荣珩
%J 科学通报
%D 1997
%I 
%X 一维装箱问题可定义为:给定一个代表工件大小的正数表(为方便计p_ⅰ也表第ⅰ个工件),如何把这些工件装入大小为单位容量的箱子里去,使所用的箱子数最小。FFD(first fit decreasing)算法是装箱问题的一个近似算法。FFD算法是指:首先按工件大小将工件排队,然后从大的开始装入箱内.不妨设,当装第ⅰ个工件p_ⅰ时,B_k是下标最小且其中装入的工件的大小总量不超过1-p_ⅰ的箱子,那么FFD算法就将p_ⅰ放入箱子B_k中。用FFD(L)表示用FFD装L中的工件所用的箱子数。OPT(L)表示最优装法所用的箱子数。Johnson证明了成立,Baker证明了越民义证明了,本文利用权函数证明了
%K 权函数
%K FFD算法
%K 装箱问题
%K 最优装法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=01BA20E8BA813E1908F3698710BBFEFEE816345F465FEBA5&cid=7C7E63796F062382A606A3A9833B8C05&jid=B40D4BA57FF46E45205A09B4DC283152&aid=74A16C136777731F21CB297004F98BE4&yid=5370399DC954B911&vid=ECE8E54D6034F642&iid=708DD6B15D2464E8&sid=966760CE8B6E636C&eid=D932AD0F8FDA3032&journal_id=0023-074X&journal_name=科学通报&referenced_num=0&reference_num=1