摘要
0/1背包问题是计算机算法中一个经典问题。提出背包问题在现实生活中具有广泛的应用,从理论入手,给出背包问题的数学描述,并对0-1背包问题的四种经典算法:分支界限法、动态规划法、近似算法、遗传算法的算法思想进行详细描述,并对四种算法在实现的时间,空间和准确性等性能方面进行分析和对比,总结四种方法实现的优缺点,并得出结论:在不同的约束条件下,四种算法各有优劣,但遗传算法应该是未来发展的方向。
0-1 knapsack problem is a classical problem in computer algorithms. Presents the wide application of the knapsack problem, arithmetically describes the problem in the real world, by doing the contrast between the time, space and accuracy, mainly analyses the four classical algorithms： branch and bound, dynamic programming; approximate algorithms and genetic algorithm, summarizes the advantages and disadvantages of the different algorithms and points out that genetic algorithm wins the future under the different constraints.
出处
《现代计算机》
2009年第6期35-38,共4页
Modern Computer
关键词
0-1背包
分支-界限
动态规划
近似算法
遗传算法
0-1Knapsack Problem
Branch and Bound
Dynamic Programming
Approximate Algorithms
Genetic Algorithm
