| 求解0—1背包问题的动态规划法分析 |
| |
| 引用本文： | 吕聪颖,赵刚彬,周春光.求解0—1背包问题的动态规划法分析[J].南阳理工学院学报,2011,3(2):17-21. |
| |
| 作者姓名： | 吕聪颖 赵刚彬 周春光 |
| |
| 作者单位： | 南阳理工学院计算机科学与技术系,河南南阳473004 [2]吉林大学计算机科学与技术学院,吉林长春130012 |
| |
| 摘 要： | 0—1背包问题是一种经典的NP-hard组合优化问题，现实生活中的很多问题都可以以它为模型。首先对0—1背包问题进行了描述，根据其具有最优子结构性质和子问题重叠性质，进而提出了基于动态规划法的策略来求解该问题。另外，为了降低算法的复杂性，又提出了算法的改进策略。实例的运行结果表明了算法的有效性，同时也证实了改进策略的优越性。
|
| 关 键 词： | 0一1背包 动态规划 最优子结构 跳跃点 |
THE ANALYSIS OF THE DYNAMIC PROGRAMMING FOR 0 - 1 KNAPSACK |
| |
| LV Cong-ying,ZHAO Gang-bin,ZHOU Chun-guang.THE ANALYSIS OF THE DYNAMIC PROGRAMMING FOR 0 - 1 KNAPSACK[J].Journal of Nanyang Institute of Technology,2011,3(2):17-21. |
| |
| Authors: | LV Cong-ying ZHAO Gang-bin ZHOU Chun-guang |
| |
| Affiliation: | 1.Department of Computer Science and Technology,Nanyang Institute of Technology,Nanyang 473004,China;2.College of Computer Science and Technology,Jilin University,Changchun 130012,China) |
| |
| Abstract: | The 0 - 1 knapsack problem is a NP-hard problem, and many problems in real life can translate into it. Here 0 - 1 knapsack problem is described firstly, and then presents dynamic programming to solve the problem according to the properties of optimal subs |
| |
| Keywords: | 0- 1 knapsack dynamic programming optimal substructure jump point |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
