基于0/1背包问题的讨论  

Discussion on the 0/1 Knapsack Problem

作　　者：林鑫[1] 

机构地区：[1]同济大学计算机系

出　　处：《微型电脑应用》2007年第4期15-16,32,共3页Microcomputer Applications

摘　　要：简单介绍了贪婪算法、启发式贪婪算法和模拟退火算法(SAA),并使用这三种算法解决了0/1背包问题,给出了具体的算法描述和求解过程。对三种方法解决此问题,进行了仿真模拟和算法分析,指出了在不同规模下各种方法的优缺点,最后分析了解的质量和CPU时间。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.

关 键 词：0/I背包问题 贪婪算法 启发式贪婪算法 模拟退火算法 CPU时间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]