| 背包问题的两阶段动态规划算法 |
| |
| 引用本文： | 崔耀东,杨绍增.背包问题的两阶段动态规划算法[J].高校应用数学学报(A辑),1993(4):430-435. |
| |
| 作者姓名： | 崔耀东 杨绍增 |
| |
| 作者单位： | 郑州市郑州航空工业管理学院 450052
(崔耀东)，郑州市郑州航空工业管理学院 450052(杨绍增) |
| |
| 摘 要： | 本文通过理论分析给出了背包问题的两阶段动态规划算法，用例题说明了其求解过程。在计算机上运用本文所述算法和背包问题的动态规划算法求解了大量例题。解题实践说明，对于大中型背包问题，两阶段动态规划算法由于只要求对少量变量进行排序而使解题时间大为缩短，是一种值得推荐的算法。
|
| 关 键 词： | 背包问题 动态规划 整数规划 |
TWO STAGE DYNAMIC PROGRAMMING ALGORITHM FOR KNAPSACK PROBLEMS |
| |
| Cui Yaodong Yang Shaozeng.TWO STAGE DYNAMIC PROGRAMMING ALGORITHM FOR KNAPSACK PROBLEMS[J].Applied Mathematics A Journal of Chinese Universities,1993(4):430-435. |
| |
| Authors: | Cui Yaodong Yang Shaozeng |
| |
| Institution: | Zhengzhou Managemant College of Aeronautical Industry |
| |
| Abstract: | In this paper, a two-stage dynamic programming algorithm for knapsack problems is proposed through analysis. An example is given to illustrate the solution approach. Using a micro-computer, a large number of knapsack problems are solved by the algorithm described in this paper and the dynamic programming algorithm proposed in reference 1]. The results show that for middle or large scale knapsack problems, the computer time can be cut down greatly by using the new algorithm. |
| |
| Keywords: | Knapsack Problems Dynamic Programming Integer Programming |
| 本文献已被 CNKI 维普 等数据库收录！ |
