关于0-1背包问题的研究  

Research on 0-1 Knapsack Problem

作　　者：王雯[1] 武燕[1] 

机构地区：[1]太原工业学院,山西太原030008

出　　处：《机械工程与自动化》2014年第3期221-223,共3页Mechanical Engineering & Automation

基　　金：国家自然科学基金资助项目(60843006);山西省青年科学基金资助项目(2007021018)

摘　　要：阐述了0-1背包问题的概念,对主要的近似算法及精确算法进行了说明,并比较了它们各自的优点和缺点,在此基础上提出了未来0-1背包算法的发展方向和趋势,并指出用粗糙集理论来解决0-1背包问题的可能性。Firstly,the concept of 0-1knapsack problem（KP）is introduced in this paper.Then the basic thoughts of several exact algorithms and approximate algorithms are stated,and the advantages and disadvantages of the given methods are respectively compared,the prospect for the future of solving KP is provided.At last,this paper points out the possibility of rough set used for 0-1knapsack problem.

关 键 词：背包问题 贪婪法 遗传算法 粗糙集理论 

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