摘要
背包问题是算法设计分析中的经典问题，本文采用贪婪法、动态规划法及递归法三种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程，并以具体实例详细描述不同方法求解问题解时算法基本思想，总结三种方法实现的优缺点并得出结论。
The knapsack problem is a classical question in the area of algorithm design and analysis, in this paper greedy method, the dynamic programming method and the recursion method are used separately to solve the knapsack problem, 0-1 knapsack problem and the simple 0-1 knapsack problem, and to design the algorithm, to discuss the time complexity. Algorithm design and realization process is given, and with example algorithm basic thought to describe different solution is introduced, and the conclusion is gotten by summarizing the goods and shortcoming of three methods.
作者
孙红丽
SUN Hong-li （Computer Science Department, Shangqiu Normal University, Shangqiu 476000, China）
出处
《电脑知识与技术》
2008年第9期1534-1535,共2页
Computer Knowledge and Technology
基金
商丘师范学院骨干教师资助项目
商丘师范学院教学改革项目
河南省教育厅资助项目（20088520029）
关键词
背包问题
贪婪法
动态规划法
时间复杂度
knapsack problem
greedy method
dynamic programming method
time complexity
