| 基于0/1背包问题的讨论 |
| |
| 引用本文： | 林鑫.基于0/1背包问题的讨论[J].微型电脑应用,2007,23(4):15-16,32. |
| |
| 作者姓名： | 林鑫 |
| |
| 作者单位： | 同济大学计算机系,上海,200433 |
| |
| 摘 要： | 简单介绍了贪婪算法、启发式贪婪算法和模拟退火算法(SAA),并使用这三种算法解决了0/1背包问题,给出了具体的算法描述和求解过程。对三种方法解决此问题,进行了仿真模拟和算法分析,指出了在不同规模下各种方法的优缺点,最后分析了解的质量和CPU时间。
|
| 关 键 词： | 0/1背包问题 贪婪算法 启发式贪婪算法 模拟退火算法 CPU时间 |
| 文章编号： | 1007-757X（2007）04-0015-02 |
| 收稿时间： | 2006-10-05 |
| 修稿时间： | 2006-10-05 |
0/1 Knapsack Problem |
| |
| LIN Xin.0/1 Knapsack Problem[J].Microcomputer Applications,2007,23(4):15-16,32. |
| |
| Authors: | LIN Xin |
| |
| Abstract: | This paper simply introduced the greedy algorithm, heuristic greedy algorithm and simulated annealing algorithm, and solved the 0/1 knapsack problem through these methods. It provided concrete algorithms and described the course of solving. This paper carried outartificial simulation and algorithm analysis on these three kinds of methods, and also pointed out the pluses and minuses of different methods under different scales. Finally, it analyzed the quality of the solution and CPU time. |
| |
| Keywords: | 0/1 knapsack problem Greedy algorithm Heuristic greedy algorithm Simulated annealing algorithm (SAA) CPU time |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
