| 求解背包问题的一种新的近似算法 |
| |
| 引用本文： | 张生,梁国宏,黄辉,何尚录.求解背包问题的一种新的近似算法[J].兰州铁道学院学报,2007,26(6):131-133. |
| |
| 作者姓名： | 张生 梁国宏 黄辉 何尚录 |
| |
| 作者单位： | 兰州交通大学数理与软件工程学院 甘肃兰州730070 |
| |
| 基金项目： | 甘肃省自然科学基金，光电技术智能控制教育部重点实验室(兰州交通大学)开放基金 |
| |
| 摘 要： | 给出了求解背包问题的一种新的近似算法,这一算法是一种改进的贪婪算法,即将部分枚举法与贪婪算法相结合.从而使其具有更好的性能保证.同时,从理论上证明了这一算法的可靠性.最后,通过具体算例验证了算法的有效性.
|
| 关 键 词： | 背包问题 贪婪算法 性能保证. |
| 文章编号： | 1001-4373（2007）06-0131-03 |
| 收稿时间： | 2007-03-23 |
| 修稿时间： | 2007年3月23日 |
A New Approximate Algorithm for the Knapsack Problem |
| |
| Zhang Sheng,Liang Guohong,Huang Hui,He Shanglu.A New Approximate Algorithm for the Knapsack Problem[J].Journal of Lanzhou Railway University,2007,26(6):131-133. |
| |
| Authors: | Zhang Sheng Liang Guohong Huang Hui He Shanglu |
| |
| Abstract: | This paper presents a new approximation algorithm for knapsack problem. The algorithm is an improved greedy algorithm which combined the part of enumeration method with the greedy algorithm,thus to make it a better performance guarantee.At the same time,the reliability of this algorithm is theoretically proved.Finally,the effectiveness of the algorithm is verified by the specific example. |
| |
| Keywords: | knapsack problem greedy algorithm performance guarantee |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
