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

Discussion on the Zero-One Knapsack Problem

作　　者：林鑫[1] 

机构地区：[1]同济大学计算机系,上海200433

出　　处：《微机发展》2005年第10期41-43,共3页Microcomputer Development

摘　　要：简单介绍了贪婪算法、启发式贪婪算法和模拟退火算法(SAA),并使用这三种算法解决了0-1背包问题,给出了具体的算法描述和求解过程。对三种方法解决此问题,进行了仿真模拟和算法分析,指出了在不同规模下各种方法的优缺点,最后分析了解的质量和CPU时间,发现模拟退火算法是相对最优的算法。Simply introduces greedy algorithm, heuristic greedy algorithm and simulated annearding algorithm and solves the zero - one knapsack problem through these methods. It provides ooncrete algorithms and describes the oourse of solving. To these three kinds of methods, this paper has carried on artificial simulation and algorithm analysis and also points out the pluses and minuses of different methods under different scale. Finally it analyses the quahty of ,solution and CPU time. And find that simulated annealing algorithm is comparatively optimal.

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

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