摘要
运用属性论的转换程度函数,结合贪婪算法和核问题的研究思路提出了多维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.
出处
《广西师范大学学报（自然科学版）》
CAS
北大核心
2006年第1期22-25,共4页
Journal of Guangxi Normal University:Natural Science Edition
基金
国家自然科学基金资助项目(60075016)
关键词
0-1背包问题
贪婪算法
核问题
转换程度函数
属性论
0-1 knapsack problem, greedy algorithm
core problem
conversion degree functions
attribute theory
