解0/1背包问题的动态规划算法
摘要：本文通过研究动态规划原理，提出了根据该原理解决０／１背包问题的方法与算法实现，
并对算法的正确性作了验证．观察程序运行结果，发现基于动态规划的算法能够得到正确的决策方案且比穷举法有效．
关键字：动态规划；０／１背包；约束条件；序偶；决策序列；支配规则
1、引 言
科学研究与工程实践中，常常会遇到许多优化问题，而有这么一类问题，它们的活动过程可以分为若干个阶段，但整个过程受到某一条件的限制。这若干个阶段的不同决策的组合就构成一个完整的决策。0/1背包问题就是一个典型的在资源有限的条件下，追求总的收益最大的资源有效分配的优化问题。
对于0/1背包问题，我们可以这样描述：设有一确定容量为C 的包及两个向量C ’=（S 1，S 2，……，S n ）和P=（P 1，P 2，……，P N ），再设X 为一整数集合，即X=1，2，3，……，N ，X 为SI 、PI 的下标集，T 为X 的子集，那么问题就是找出满足约束条件∑S i 〈=C ，使∑PI 获得最大的子集T 。在实际运用中，S 的元素可以是N 个经营项目各自所消耗的资源，C 可以是所能提供的资源总量，P 的元素可是人们从各项项目中得到的利润。
0/1背包问题是工程问题的典型概括，怎么样高效求出最优决策，是人们关心的问题。
2、求解问题的动态规划原理与算法 2．1动态规划原理的描述
求解问题的动态规划有向前处理法向后处理法两种，这里使用向前处理法求解0/1背包问题。对于0/1背包问题，可以通过作出变量X 1，X 2，……，X N 的一个决策序列来得到它的解。而对于变量X 的决策就是决定它是取0值还是取1值。假定决策这些X 的次序为X n ，X N-1，……，X 0。在对X 0做出决策之后，问题处于下列两种状态之一：包的剩余容量是M ，没任何效益；剩余容量是M-w ，效益值增长了P 。显然，之后对X n-1，Xn-2，……，X 1的决策相对于决策X 所产生的问题状态应该是最优的，否则X n ，……，X 1就不可能是最优决策序列。如果设F j （X ）是KNAP （1，j ，X ）最优解的值，那么F n （M ）就可表示为
F N （M ）=max(f n (M),f n-1(M-w n )+p n )} （1） 对于任意的f i (X),这里i>0，则有
f i (X)=max{f i-1(X),f i-1(X-w i )+p i } （2） 为了能由前向后推而最后求解出F N （M ），需从F 0（X ）开始。对于所有的X>=0,有F 0（X ）=0，当X<0时，有F 0（X ）等于负无穷。根据（2），可求出0〈X 〈W 1和X 〉=W 1情况下F 1（X ）的值。接着由（2）不断求出F 2，F 3，……，F N 在X 相应取值范围内的值。
2．2 0/1背包问题算法的抽象描述
(1)初始化各个元素的重量W[i]、效益值P[i]、包的最大容量M ； (2)初始化Ｓ0； (3)生成S i ；
a．在中Ｓi-1找满足约束条件的第R对序偶；
b．生成S
1
i ;
c．清除不满足条件的序偶；
d．将S n-1中满足条件的序偶复制到S n 中；
（4）对S
n+1
置初值；
（5）若不满足循环次数转（3）,否则转（６）；
（6）用回溯法确定决策序列；终止程序。
2．3计算复杂性分析
假设S
i 的序偶是|Ｓi|。在i＞０的情况下，每个Ｓi由Ｓ
1
i-1和Ｓ
1
i归并而成，并且｜
Ｓ
1
i |<=|Ｓi-1 |,因此｜Ｓi |<=2|Ｓi-1 |。在最坏情况下没有序偶被清除，所以对|Ｓi|求和(i=0,1,2,．．．n-1)的结果是２n-1,也就是说ＤＫＮＡＰ的空间复杂度为Ｏ（２n）。
由Ｓi-1生成Ｓi需要|Ｓi-1||的时间，所以在计算S
0，S
1
，S
2
，……，S
n-1
时所消耗的
总时间为（∑|Ｓi-1|），0〈＝i〈＝n－１。由于｜Ｓi｜〈＝２n，所以计算这些Ｓi 总的时间为Ｏ（２n）。
该算法的时间复杂性为Ｏ（２n），似乎表明当Ｎ很大时它的有效性不会让人满意，但由于支配规则的引入，很好的清除了不满足约束的序偶，因而该算法在很多情况下都能在可接受的时间内求出决策序列。
２．４基于动态规划的算法源程序
由于算法源程序有一定的篇幅，将其附后。
3、性能测试
３．１测试问题
为了验证算法的正确性与有效性，用两个数组Ｐ［Ｎ］和Ｗ［Ｎ］分别存储
始记录Ｃ’和P，记录为用穷举法已求出最优决策的实例。现分别取Ｎ＝3，4 ，6，10进行实验。
3．2试验结果与分析
为了便于说明问题，现将实验过程中的N取不同值的一组向量Ｃ’和P（也就是重量与效益值）记录如下：
N=3：Ｃ’=（2，3，4）；P=（1，2，5）；M=6；
N=4：Ｃ’=（2，4，6，7）；P=（6，10，12，13）；M=11；
N=6：Ｃ’=（100，50，20，10，7，3）；P=（90，70，30，20，5，15）；M=165；
N=10：Ｃ’=（2，4，5，7，10，14，19，20，25，30）；
P=（1，3，4，5，10，15，20，25，36，28）；M=70；
运行程序，与上述实例对应的决策序列为（1 0 1）、（0 1 0 1）、（1 1 0 1 1）和（0 0 1 1 0 1 1 0 1 0），各决策序列与穷举法得到的结果一致，得到了最大的效益值，都为有限资源下的最优决策序列。
根据程序运行的中间结果，记录上述实例每次的S i的序偶个数，结果如下表：
S i的序偶个数表：
