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

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

Discussion on the Zero- One Knapsack Problem

Simply introduces greedy algorithm,heuristic greedy algorithm and simulated anneanling algorithm and solves the zero-one knapsack problem through these methods.It provides concrete algorithms and describes the course 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 quality of solution and CPU time.And find that simulated annealing algorithm is comparatively optimal.