蓝雯飞，吴子莹，杨 波

(中南民族大学 计算机科学学院，武汉 430074)

背包问题的动态规划改进算法

蓝雯飞，吴子莹，杨 波

(中南民族大学 计算机科学学院，武汉 430074)

在动态规划算法的基础上提出了改进算法，对于0-1背包问题，改进了动态规划算法的状态表示以减少需要计算的状态个数来求解该问题；对于完全背包问题，简化了动态规划算法状态的决策依赖关系来求解该问题.实验结果表明：所提出的改进算法在时空效率上具有一定的有效性和优越性.

背包问题；动态规划；状态表示；决策依赖

背包问题在现实生活中广泛地应用于需要基于有限资源进行选择判断的领域[1]，如货物装载、投资组合、下料问题等[2]，因此对该问题的研究具有重要的实际意义.背包问题可以衍生出0-1背包问题、完全背包问题和多重背包问题等[3].解决0-1背包问题的动态规划算法的时空复杂度为O(nW)，本文通过简化动态规划算法的状态表示来改进算法，改进后算法的空间复杂度为O(W)，时间效率上有常数时间的优化.解决完全背包问题的动态规划算法时间复杂度为O(nW(W/wi))，空间复杂度为O(nW)，本文通过简化动态规划算法状态的决策依赖关系改进算法，改进后算法的时空复杂度均为O(nW).

1 求解0-1背包问题的动态规划算法

1.1 常规动态规划算法RDP

建立规划模型：子问题m(i,j)是前i个物品基于背包容量j所能得到的最大价值[7].根据0-1背包问题满足最优子结构的性质，建立状态转移方程如下：

m(i,j)=

问题迭代的初始条件为：

(2)

常规的动态规划算法RDP(Regular Dynamic Programming)的空间复杂度是O(nW)，时间复杂度为O(nW).利用动态规划方法，问题可以在O(nW)的时间效率内解决[8].但算法的时间复杂度与背包容量有关[9].当背包容量较小时，算法的时间复杂度是可以接受的.但是当W≥2n时，该动态规划算法的时间复杂度为O(n2n).

1.2 动态规划算法改进思路

在0-1背包问题中，公式(1)同时用容量较小的背包和较少的物品种类来缩小原问题的规模，即子问题m(i,j)表示前i件物品基于背包容量j所能得到的最大价值.子问题m(i,j)的计算只依赖于m(i-1,·)，即当前子问题的计算只依赖于算法中前一轮子问题的解.因此可以考虑改进状态表示，用一维的子问题状态m(j)表示容量为j的背包可以装入物品的最大价值.

依据公式(1)，子问题m(i,j)是由m(i-1,j)和m(i-1,j-wi)两个子问题递推而来.对于一维的子问题m(j)，若算法采用顺推的方式，在计算子问题“前i个物品基于背包容量j能得到的最大总价值”m(j)时，m(j-wi)保存的是子问题“前i个物品基于背包容量j-wi所能得到的最大总价值”，这与上述状态转移方程中的决策不符.若算法采用逆推的方式，在每次计算中以背包容量递减的方式考虑子问题m(j)，这样可以保证在计算子问题m(j)时，m(j)和m(j-wi)保存的是所依赖的子问题的解.改进后的状态转移方程如下：

(3)

迭代的初始条件为：

(4)

改变动态规划算法的规划顺序后，时间复杂度为O(nW)，算法的空间复杂度由O(nW)优化到O(W).动态规划算法的时间复杂度主要由每次状态转移所涉及的状态数、每次状态转移的时间、问题中需要计算的状态总数这三部分组成，在不改变前两个部分的基础上，限制问题中状态计算的上下界，减少算法中需要计算的状态个数，以此来提高算法的时间效率.

1.3 高效的动态规划算法EDP

公式(3)用逆推的方式解决问题.仔细分析算法发现其中仍然存在冗余，当依次考虑到第n件物品时，事实上前n-1件物品的最优装载方式已经确定，此时只需一次计算，计算公式如下：

(5)

状态转移方程可以被优化为：

(6)

2 求解完全背包问题的动态规划算法

2.1 传统动态规划算法NDP

0-1背包问题中每种物品只有两种决策：选或不选；完全背包问题中物品有选择0件、选择1件、选择2件、…、选择⎣W/wi」件等多种策略，虽然每种物品有无限件，但对于一件具体的物品，依然只有放进背包或不放进背包两种策略[11].

借用解决0-1背包问题的思想[12]，定义子问题m(i,j)为前i件物品基于背包容量j所能得到的最大价值.据此状态转移方程为：

m(i,j)=max{m(i-1,j-x·wi)+x·vi,0≤x·wi≤j}.

(7)

迭代的初始条件为：

m(1,j)=x·v1,0≤x·w1≤j.

(8)

2.2 动态规划算法改进

完全背包问题的优化措施：对于两件物品i,j，若满足约束条件wi≥wj,vi≤vj，则在将物品放入背包时，可以不考虑第i种物品.因为在任何情况下将装入背包的第i种物品替换为重量小、价值高的第j种物品时，背包的总价值不会变小.此优化措施可以减少物品的种类，提高算法执行的效率.但对于任意的两种物品i,j，不存在wi≥wj,vi≤vj关系时不能去掉任何物品.

分析公式(7)可以发现当计算子问题m(i,j)时，方程引用了x=0,1,2,…，⎣j/wi」每一种决策.令x=⎣j/wi」，计算子问题m(i,j)时，已求解的子问题m(i,j-wj)正是前i-1种物品和x-1件第i种物品基于背包容量j-wi所能获得的最大价值.因此状态转移方程可以被优化为：

m(i,j)=

我们把本文提出的动态规划改进算法称为优化动态规划算法ODP(Optimization of Dynamic Programming).ODP减少了每次状态转移的状态数，将方程中每次状态转移涉及的状态数从O(W/wi)降为O(1)，将算法的时间复杂度优化到O(nW).

3 性能测试结果与分析

实验将验证改进后的算法在解决0-1背包问题和完全背包问题时物品重量对时间效率的影响，按物品重量与背包容量的关系将实验数据分为5类，即物品重量wi分别在[1,W/20],[W/20,W/10],[W/10,3W/20],[3W/20,W/5],[1,W/5]范围内随机分布，令背包容量W=1000.

3.1 0-1背包问题的测试结果与分析

表1是不同问题规模不同物品重量分布时算法的运行时间，图1是不同问题规模物品重量在[1,200)分布时RDP和EDP的运行时间比较.下面从两个方面分析这两种算法的时间效率差异.

表1 不同问题规模不同物品重量分布时算法的运行时间

图1 RDP和EDP运行时间比较Fig.1 Comparison of running time between RDP and EDP

(1)不同数据类别的0-1背包问题. 当物品重量与背包容量有不同关系时，RDP有不同的状态转移关系，影响算法时间效率.EDP在RDP基础上，改变算法的规划方向，分析状态之间的依赖关系，紧致问题中所需要计算状态的界限条件.这个界限条件与物品重量有关系：当物品重量增加时，问题中需要计算的状态个数减少.由于每次状态转移过程中所涉及的状态数和转移时间不变，这样就从整体上提高了算法的时间效率.

如图1所示，在相同物品数量规模的情况下，EDP的运行时间比RDP的运行时间少，而且随着物品数量规模的增大，两条曲线之间的距离越来越大，EDP运行时间会明显比RDP的运行时间少.

(2) 相同数据类别相同数据规模的0-1背包问题. 如表1所示，物品重量在[1,50), [150,200), [1,200)随机分布时，在相同物品数量规模的情况下，EDP的运行时间均比RDP的运行时间少.

无论所考虑物品重量较小(即物品重量在[1,50)随机分布)，还是物品重量较大(在[150,200)分布)，或是所考虑物品中既有小重量物品又有大重量物品(在[1,200)随机分布)，EDP的时间效率都要比RDP的时间效率高.

EDP的时间效率比RDP的时间效率高，原因在于EDP对问题中需要计算的状态做了上下界约束，减少了需要计算的状态个数，因此减少问题中需要计算的状态总个数可以有效地提高动态规划算法的时间效率.

3.2 完全背包问题的测试结果与分析

表2是不同问题规模物品重量在[1,50),[50,100),[100,150)上随机分布时算法的运行时间，表3是不同问题规模物品重量在[150,200),[1,200)上随机分布时算法的运行时间，图2是不同问题规模物品重量在[1,200)分布时NDP、BDP和ODP的运行时间比较.下面从2个方面分析这3种算法的时间效率差异.

表2 物品重量在[1,50), [50,100), [100,150)上随机分布算法的运行时间

表3 物品重量在[150,200), [1,200)上随机分布算法的运行时间

Tab.3 Running time of the algorithm on the random distribution of the item weight in [150,200), [1,200) ms

(1)不同数据类别的完全背包问题. 如图2所示，在相同物品数量规模的情况下，ODP的运行时间比NDP、BDP的运行时间少，而且随着物品数量规模的增大，3条曲线之间的差异愈加显著，ODP的运行时间明显比NDP、BDP的运行时间少.

图2 NDP、BDP和ODP运行时间比较Fig.2 Comparison of running time among NDP, BDP and ODP

NDP和BDP在求解不同数据类别的完全背包问题时，随着物品重量的增加，算法的时间效率会相应地提高.ODP在NDP的基础上减少了每次状态转移所依赖的状态数.由于ODP的时间效率与物品重量并没有直接关系，因此ODP在求解不同数据类别的完全背包问题时表现出基本一致的性能.

(2) 相同数据类别相同数据规模的完全背包问题. 如表2、表3所示，物品重量在[1,50)随机分布时，在相同物品数量规模的情况下，ODP的运行时间明显比NDP、BDP的运行时间少，约是NDP运行时间的1/20,约是BDP运行时间的1/3；物品重量在[150,200)随机分布时，在相同物品数量规模的情况下，EDP的运行时间也均比NDP、BDP的运行时间少；物品重量在[1,200)随机分布时亦是如此.

BDP比NDP的时间效率要高.BDP将完全背包问题转化为0-1背包问题的过程中运用了二进制思想，减少了转化后的物品件数，而NDP是将问题直接进行转化.本文通过对NDP的研究，分析出状态间有效的决策依赖关系，发现NDP在每次状态转移的过程中涉及了大量无效的状态，而ODP明显减少了每次状态转移的状态数，因此提高了算法的时间效率.

4 结束语

动态规划是求解背包问题的一种经典算法.求解0-1背包问题时，论文通过对RDP中需要计算的状态做出了上下界约束，进而得到改进后的EDP.求解完全背包问题时，通过对NDP分析，发现每次状态转移的过程中涉及了大量无效的状态，分析出状态间有效的决策依赖关系，从而得到优化后的ODP算法.最后通过实验验证了论文提出的EDP和ODP的有效性和优势.今后将继续研究背包型动态规划，使得该问题的应用价值能更好地发挥出来.

[1] Bologna T P. Dynamic programming algorithms for the zero-one knapsack problem[J]. Computing, 1980, 25 (1): 29-45.

[2] Sitarz S. Dynamic programming with ordered structures: theory, examples and applications[J]. Fuzzy Sets and Systems,2010,161(20):2623-2641.

[3] Cormen T H, Leiserson C E, Rivest R L, et al. Introduction to algorithms[M]. Massachusetts: The MIT Press, 2012:101-120.

[4] Bellman R. Dynamic programming[M]. Princeton: Princeton University Press,1957:60-80.

[5] 李 端，钱富才，李 力，等. 动态规划问题研究[J]. 系统工程理论与实践，2007,27(8):56-64.

[6] 李北斗. 关于0-1背包问题的算法研究[J]. 计算机与数字工程，2008,36(5):23-26.

[7] 孙怀影，耿寅融，单 谦. 求解0-1背包问题的一种新混合算法[J]. 计算机工程与应用，2012,48(4):50-53.

[8] 朱阅岸. 解0-1背包问题的算法比较和改进[D]. 广州：暨南大学，2011.

[9] Cosnard M, Ferreira A G, Herbelin H. The two list algorithm for a knapsack problem[J]. Parallel Computing, 1989,34(9):385-388.

[10] Martello S, Pisinger D, Toth P. New trends in exact algorithms for the 0-1 knapsack problem[J]. European Journal of Operational Research, 2010, 123(2):325-332.

[11] Pisinger D. Where are the hard knapsack problems[J]. Computes and Operations Research, 2005,32(9):2271-2284.

[12] 马 良，王龙德. 背包问题的蚂蚁优化算法[J]. 计算机应用，2001,21(8):4-5.

[13] 刘汝佳，黄 亮. 算法艺术与信息学竞赛[M]. 北京：清华大学出版社，2004: 35-48.

Improved Dynamic Programming Algorithms for the Knapsack Problem

Lan Wenfei, Wu Ziying, Yang Bo

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

In this paper, we proposed improved algorithms based on dynamic programming thinking. For the 0-1 knapsack problem, we improved the status representation of dynamic programming algorithm to reduce the number of states needed to calculate. For the complete knapsack problem, we simplified the decision dependency status of dynamic programming algorithm to solve the problem. Experimental results showed that the improved algorithms have some validity and superiority in space and time efficiency.

knapsack problem；dynamic programming；state representation；decision dependency

2016-06-14

蓝雯飞(1966-)，女，教授，研究方向：数据库技术和软件新技术，E-mail:lanwenfei1@163.com; 吴子莹(1990-)，女，硕士研究生，研究方向：数据挖掘，E-mail:1047237684@qq.com

国家自然科学基金资助项目(71003038)

TP301

A

1672-4321(2016)04-0101-05