| 一种求解分组0-1背包问题的动态规划法 |
| |
| 引用本文： | 蒋亚军,易学军.一种求解分组0-1背包问题的动态规划法[J].经济数学,2012(1):75-78. |
| |
| 作者姓名： | 蒋亚军 易学军 |
| |
| 作者单位： | 湖南科技学院计算机与通信工程系;湖南大学数学与计量经济学院 |
| |
| 基金项目： | 湖南省科技计划资助项目(2011FJ3066) |
| |
| 摘 要： | 研究了分组0-1背包问题,提出了一种动态规划解决方法,在物品总数为n个和背包承重量为W时,递推过程的复杂度为O(nW),回溯过程的复杂度为O(n).计算实例表明利用该方法易于找到最优解.
|
| 关 键 词： | 背包问题 NP完全 动态规划 |
A Dynamic Programming Method for Classified 0-1 Knapsack Problem |
| |
| JIANG Ya-jun,YI Xue-jun.A Dynamic Programming Method for Classified 0-1 Knapsack Problem[J].Mathematics in Economics,2012(1):75-78. |
| |
| Authors: | JIANG Ya-jun YI Xue-jun |
| |
| Institution: | 1.Department of Computer and Communication Engineering,Hunan University of Science and Engineering,Yongzhou, Hunan 425100 China;2.College of Mathematics and Econometrics,Hunan University,Changsha,Hunan 410082 China) |
| |
| Abstract: | This paper studied the classified 0-1 knapsack problem,and proposed a dynamic programming method.The complexity of the recursive process is O(nW),and the complexity of the traceback process is O(n),where n is the total number of goods and W is the bearing weight of the knapsack.The example shows that it is easy to find the optimal solution by the method. |
| |
| Keywords: | Knapsack Problem NP-complete Dynamic Programming |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《经济数学》浏览原始摘要信息 |
| 点击此处可从《经济数学》下载免费的PDF全文 |
|
