| 多维0-1背包问题的新型近似解法 |
| |
| 引用本文： | 郑杨凡,冯嘉礼,甘棠仪,邵红青.多维0-1背包问题的新型近似解法[J].广西师范大学学报(自然科学版),2006,24(1):22-25. |
| |
| 作者姓名： | 郑杨凡 冯嘉礼 甘棠仪 邵红青 |
| |
| 作者单位： | 上海海事大学信息工程学院计算机系,上海,200135;上海海事大学信息工程学院计算机系,上海,200135;上海海事大学信息工程学院计算机系,上海,200135;上海海事大学信息工程学院计算机系,上海,200135 |
| |
| 基金项目： | 国家自然科学基金资助项目(60075016) |
| |
| 摘 要： | 运用属性论的转换程度函数,结合贪婪算法和核问题的研究思路提出了多维0-1背包问题的一种新型近似解法。该算法对生产实践中的四大类背包实例都有很快的收敛速度。特别是常规方法难以解决的最大子集和实例及强相关实例,算法能在一个很好的时间范围内给出近似度为99.7%的近似满意解甚至是最优解。
|
| 关 键 词： | 0-1背包问题 贪婪算法 核问题 转换程度函数 属性论 |
| 文章编号： | 1001-6600（2006）01-0022-04 |
| 收稿时间： | 2005-11-03 |
| 修稿时间： | 2005年11月3日 |
A New Approximation Algorithm for Knapsack Problem |
| |
| ZHENG Yang-fan,FENG Jia-li,GAN Tang-yi,SHAO Hong-qing.A New Approximation Algorithm for Knapsack Problem[J].Journal of Guangxi Normal University(Natural Science Edition),2006,24(1):22-25. |
| |
| Authors: | ZHENG Yang-fan FENG Jia-li GAN Tang-yi SHAO Hong-qing |
| |
| Institution: | Department of Computer ,SMU ,Shanghai 200135 ,China |
| |
| Abstract: | 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. |
| |
| Keywords: | 0-1 knapsack problem greedy algorithm core problem conversion degree functions attribute theory |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
