一种求解分组0-1背包问题的动态规划法
    点此下载全文
引用本文:蒋亚军, 易学军.一种求解分组0-1背包问题的动态规划法[J].经济数学,2012,(1):75-78
摘要点击次数: 1236
全文下载次数: 187
作者单位
蒋亚军, 易学军 (1.湖南科技学院 计算机与通信工程系, 湖南 永州425100
2.湖南大学 数学与计量经济学院, 湖南 长沙410082) 
中文摘要:研究了分组0-1背包问题,提出了一种动态规划解决方法,在物品总数为n个和背包承重量为W时,递推过程的复杂度为O(nW),回溯过程的复杂度为O(n).计算实例表明利用该方法易于找到最优解.
中文关键词:背包问题  NP完全  动态规划
 
A Dynamic Programming Method for Classified 0-1 Knapsack Problem
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
查看全文   查看/发表评论   下载pdf阅读器