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

Discussion on the Zero-One Knapsack Problem

简单介绍了贪婪算法、启发式贪婪算法和模拟退火算法(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.