装箱问题的一种新的近似算法  

A new approximation algorithm for Bin-Packing problem

作　　者：孙春玲[1] 陈智斌[1] 李建平[1] 

机构地区：[1]云南大学数学系,云南昆明650091

出　　处：《云南大学学报（自然科学版）》2004年第5期392-396,共5页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学研究基金资助项目 ( 10 2 7110 3 );云南省自然科学研究基金资助项目 ( 2 0 0 3F0 0 15M ) .

摘　　要：研究了一维装箱问题 (BinPackingProblem) ,给出了一个新的近似算法 :交叉装填算法 (简称CF算法 ) .证明了CF算法达到装箱问题的最好的近似值 32 ;并且当这些物件的大小按非增性质预先排序后 。The Bin-Packing problem is studied again and derived a new32-approximation algorithm in (O(nlogn)) steps;In addition,if the sizes of all objects decreasing according to their sizes,our algorithm runs in O(n) steps.

关 键 词：装箱问题 NP-完备 近似算法 交叉装填算法 CF算法 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构] O157.6[自动化与计算机技术—计算机科学与技术]