一种求解分组0-1背包问题的动态规划法  

A Dynamic Programming Method for Classified 0-1 Knapsack Problem

作　　者：蒋亚军[1] 易学军[2] 

机构地区：[1]湖南科技学院计算机与通信工程系,湖南永州425100 [2]湖南大学数学与计量经济学院,湖南长沙410082

出　　处：《经济数学》2012年第1期75-78,共4页Journal of Quantitative Economics

基　　金：湖南省科技计划资助项目(2011FJ3066)

摘　　要：研究了分组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.

关 键 词：背包问题 NP完全 动态规划 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]