多维0-1背包问题的新型近似解法  

A New Approximation Algorithm for Knapsack Problem

作　　者：郑杨凡[1] 冯嘉礼[1] 甘棠仪[1] 邵红青[1] 

机构地区：[1]上海海事大学信息工程学院计算机系,上海200135

出　　处：《广西师范大学学报（自然科学版）》2006年第1期22-25,共4页Journal of Guangxi Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目(60075016)

摘　　要：运用属性论的转换程度函数,结合贪婪算法和核问题的研究思路提出了多维0-1背包问题的一种新型近似解法。该算法对生产实践中的四大类背包实例都有很快的收敛速度。特别是常规方法难以解决的最大子集和实例及强相关实例,算法能在一个很好的时间范围内给出近似度为99.7%的近似满意解甚至是最优解。A new approximation algorithm is presented for the classical 0-1 knapsack problem in this paper. It involves the greedy theory ,the core problem thoughts and the thinking of conversion degree functions. Different from normal algorithms ,the new approach has a lower complexity but usually give better solutions for the all 4 kinds of KP instances.

关 键 词：0-1背包问题 贪婪算法 核问题 转换程度函数 属性论 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]