摘要
研究了分组0-1背包问题,提出了一种动态规划解决方法,在物品总数为n个和背包承重量为W时,递推过程的复杂度为O(nW),回溯过程的复杂度为O(n).计算实例表明利用该方法易于找到最优解.
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.
出处
《经济数学》
2012年第1期75-78,共4页
Journal of Quantitative Economics
基金
湖南省科技计划资助项目(2011FJ3066)
关键词
背包问题
NP完全
动态规划
Knapsack Problem
NP-complete
Dynamic Programming
