最小基数箱子覆盖问题及其启发式算法  

Minimum cardinality bin covering problem and its heuristic algorithm

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

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

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

基　　金：国家自然科学研究基金资助项目(10271103);云南省自然科学研究基金资助项目(2003F0015M).

摘　　要：研究了一个新颖的装箱问题,即最小基数箱子覆盖问题(MinimumCardinalityBinCoveringProblem),证明了该问题是强NP-完备的;在物件大小满足一定的条件下,给出了一个时间复杂度为O(n)的启发式算.In the minimum cardinality bin covering problem(MCBCP),it is given m bins of capacity 1 and n items,the objective is to minimize the number of items covering the m bins without splitting items.MCBCP is proved to be strongly NP-hard and a heuristic algorithm is devised.

关 键 词：最小基数箱子覆盖问题 强NP-完备 启发式算法 最优值 

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