| 背包问题的算法设计与分析研究 |
| |
| 引用本文： | 孙红丽.背包问题的算法设计与分析研究[J].数字社区&智能家居,2008,3(9):1534-1535. |
| |
| 作者姓名： | 孙红丽 |
| |
| 作者单位： | 商丘师范学院计算机科学系,河南商丘476000 |
| |
| 基金项目： | 商丘师范学院骨干教师资助项目;商丘师范学院教学改革项目;河南省教育厅资助项目（20088520029） |
| |
| 摘 要： | 背包问题是算法设计分析中的经典问题，本文采用贪婪法、动态规划法及递归法三种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程，并以具体实例详细描述不同方法求解问题解时算法基本思想，总结三种方法实现的优缺点并得出结论。
|
| 关 键 词： | 背包问题 贪婪法 动态规划法 时间复杂度 |
Study on Algorithm Design and Analysis of Knapsack Problem |
| |
| SUN Hong-li.Study on Algorithm Design and Analysis of Knapsack Problem[J].Digital Community & Smart Home,2008,3(9):1534-1535. |
| |
| Authors: | SUN Hong-li |
| |
| Affiliation: | SUN Hong-li (Computer Science Department, Shangqiu Normal University, Shangqiu 476000, China) |
| |
| Abstract: | 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. |
| |
| Keywords: | knapsack problem greedy method dynamic programming method time complexity |
| 本文献已被 维普 等数据库收录！ |
|
