|
|||||
|
|
| 0-1背包问题的一种新的启发式算法 | |
| 引用本文： | 谈群,夏敏学,钱建刚,彭飞. 0-1背包问题的一种新的启发式算法[J]. 空军雷达学院学报, 2006, 20(4): 301-303 |
| 作者姓名： | 谈群 夏敏学 钱建刚 彭飞 |
| 作者单位： | 1. 空军雷达学院研究生管理大队,武汉,430019 2. 空军雷达学院机电工程系,武汉,430019 3. 空军雷达学院预警探测指挥系,武汉,430019 |
| 摘 要： | 为了提高求解0—1背包问题的效率，提出了这类问题的一种基于贪婪算法的启发式近似算法，通过寻找尽可能大的可行解和尽可能小的上界，从而求出近似最优解，该算法最大的优点是可以给出计算误差，算法的最坏性能比是2，通过编程计算证明该算法具有良好的性能． |
| 关 键 词： | 0-1背包 启发式算法 贪婪算法 最坏性能比 |
| 文章编号： | CN42-1564（2006）04-0301-03 |
| 收稿时间： | 2006-06-20 |
| 修稿时间： | 2006-06-202006-08-30 |
A Novel Heuristic Algorithm for the Knapsack Problem |
|
| TAN Qun,XIA Min-xue,QIAN Jian-gang,PENG Fei. A Novel Heuristic Algorithm for the Knapsack Problem[J]. Journal of Air Force Radar Academy, 2006, 20(4): 301-303 | |
| Authors: | TAN Qun XIA Min-xue QIAN Jian-gang PENG Fei |
| Affiliation: | 1.Department o f Graduate Management, AF RA, Wuhan 430019, China; 2. DepartmentofMechatronics Engineering,AFRA, Wuhan 430019,China; 3. Department of Early Warning Detection Command, AFRA, Wuhan 430019, China |
| Abstract: | In order to raise the efficiency of solving for knapsack problem, a heuristic approximate algorithm of knapsack problem was put forward in terms of the greedy algorithm. By looking for the utmost available solution and a probably small upper-bound, the approximate optimum solution can be found. The greatest feature of this method is that the calculation error can be deduced, and the worst case ratio is 2. By programming calculation it proves that this algorithm proposed works better. |
| Keywords: | knapsack problem heuristic algorithm greedy algorithm worst case ratio |
| 本文献已被 维普 万方数据 等数据库收录！ | |