解01背包问题的动态规划算法

1解0/1背包问题的动态规划算法摘要：本文通过研究动态规划原理，提出了根据该原理解决０／１背包问题的方法与算法实现，并对算法的正确性作了验证．观察程序运行结果，发现基于动态规划的算法能够得到正确的决策方案且比穷举法有效．关键字：动态规划；０／１背包；约束条件；序偶；决策序列；支配规则1、引言科学研究与工程实践中，常常会遇到许多优化问题，而有这么一类问题，它们的活动过程可以分为若干个阶段，但整个过程受到某一条件的限制。这若干个阶段的不同决策的组合就构成一个完整的决策。0/1背包问题就是一个典型的在资源有限的条件下，追求总的收益最大的资源有效分配的优化问题。对于0/1背包问题，我们可以这样描述：设有一确定容量为C的包及两个向量C’=（S1，S2，……，Sn）和P=（P1，P2，……，PN），再设X为一整数集合，即X=1，2，3，……，N，X为SI、PI的下标集，T为X的子集，那么问题就是找出满足约束条件∑Si〈=C，使∑PI获得最大的子集T。在实际运用中，S的元素可以是N个经营项目各自所消耗的资源，C可以是所能提供的资源总量，P的元素可是人们从各项项目中得到的利润。0/1背包问题是工程问题的典型概括，怎么样高效求出最优决策，是人们关心的问题。2、求解问题的动态规划原理与算法2．1动态规划原理的描述求解问题的动态规划有向前处理法向后处理法两种，这里使用向前处理法求解0/1背包问题。对于0/1背包问题，可以通过作出变量X1，X2，……，XN的一个决策序列来得到它的解。而对于变量X的决策就是决定它是取0值还是取1值。假定决策这些X的次序为Xn，XN-1，……，X0。在对X0做出决策之后，问题处于下列两种状态之一：包的剩余容量是M，没任何效益；剩余容量是M-w，效益值增长了P。显然，之后对Xn-1，Xn-2，……，X1的决策相对于决策X所产生的问题状态应该是最优的，否则Xn，……，X1就不可能是最优决策序列。如果设Fj（X）是KNAP（1，j，X）最优解的值，那么Fn（M）就可表示为FN（M）=max(fn(M),fn-1(M-wn)+pn)}（1）对于任意的fi(X),这里i0，则有fi(X)=max{fi-1(X),fi-1(X-wi)+pi}（2）为了能由前向后推而最后求解出FN（M），需从F0（X）开始。对于所有的X=0,有F0（X）=0，当X0时，有F0（X）等于负无穷。根据（2），可求出0〈X〈W1和X〉=W1情况下F1（X）的值。接着由（2）不断求出F2，F3，……，FN在X相应取值范围内的值。2．20/1背包问题算法的抽象描述(1)初始化各个元素的重量W[i]、效益值P[i]、包的最大容量M；(2)初始化Ｓ0；(3)生成Si；2a．在中Ｓi-1找满足约束条件的第R对序偶；b．生成S1i;c．清除不满足条件的序偶；d．将Sn-1中满足条件的序偶复制到Sn中；（4）对Sn+1置初值；（5）若不满足循环次数转（3）,否则转（６）；（6）用回溯法确定决策序列；终止程序。2．3计算复杂性分析假设Si的序偶是|Ｓi|。在i＞０的情况下，每个Ｓi由Ｓ1i-1和Ｓ1i归并而成，并且｜Ｓ1i|=|Ｓi-1|,因此｜Ｓi|=2|Ｓi-1|。在最坏情况下没有序偶被清除，所以对|Ｓi|求和(i=0,1,2,．．．n-1)的结果是２n-1,也就是说ＤＫＮＡＰ的空间复杂度为Ｏ（２n）。由Ｓi-1生成Ｓi需要|Ｓi-1||的时间，所以在计算S0，S1，S2，……，Sn-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；运行程序，与上述实例对应的决策序列为（101）、（0101）、（11011）和（0011011010），各决策序列与穷举法得到的结果一致，得到了最大的效益值，都为有限资源下的最优决策序列。根据程序运行的中间结果，记录上述实例每次的Si的序偶个数，结果如下表：Si的序偶个数表：3Si的个数NS0S1S2S3S4S5S6S7S8S93124——————————————41245————————————612461121————————10124781215222732观察分析Si序偶的个数可以发现，运用动态规划思想的算法，随着N的增大，对于每一个Si并非都是|Si|==2|Si-1|,尤其当i4时效果更加明显，减少了搜索的范围，避免了穷举搜索，比穷举法有效．４，结束语通过将动态规划原理引入到解０／１背包问题中，由于支配规则的高效性，使该算法比运用穷举思想的算法有效．需要指出的是，由于它的时间复杂性为Ｏ（２n），０／１背包问题是一个ＮＰ－难问题。如果能够将它降为多项式复杂性，那么所有的ＮＰ－难问题就都可以在多项式时间内求解，这将会大大提高现行些类问题的算法的可靠性与效率。在这方面，有待深入研究，也是值得研究的问题。参考文献：[1]数据结构：C语言版/严蔚敏等编著。[2]Ｃ语言程序设计：潭浩强编著。[3]计算机算法基础:第二版/余祥宣等编著。用动态规划解0/1背包问题的源程序代码：#includestdio.h#includemath.h#definen6voidDKNAP();main(){intp[n+1],w[n+1];intM,m=1,i,j;for(i=1;i=n;i++){m=m*2;printf(\ninputtheweightandthep:);scanf(%d%d,&w[i],&p[i]);}4printf(%d,m);printf(\ninputthemaxweightM:);scanf(%d,&M);DKNAP(p,w,M,m);}voidDKNAP(intp[],intw[],intM,intm){intp2[m],w2[m],pp,ww,px;intF[n+1],pk,q,k,l,h,u,i,j,next,max,s[n+1];F[0]=1;p2[1]=w2[1]=0;l=h=1;F[1]=next=2;for(i=1;in;i++){k=l;max=0；u=l;for(q=l;q=h;q++)if((w2[q]+w[i]=M)&&max=w2[q]+w[i]){u=q;max=w2[q]+w[i];}for(j=l;j=u;j++){pp=p2[j]+p[i];ww=w2[j]+w[i];while(k=h&&w2[k]ww){p2[next]=p2[k];w2[next]=w2[k];next++;k++;}if(k=h&&w2[k]==ww){if(pp=p2[k])pp=p2[k];k++;}elseif(ppp2[next-1])5{p2[next]=pp;w2[next]=ww;next++;}while(k=h&&p2[k]=p2[next-1])k++;}while(k=h){p2[next]=p2[k];w2[next]=w2[k];next=next+1;k++;}l=h+1;h=next-1;F[i+1]=next;}for(i=1;inext;i++)printf(%2d%2d,p2[i],w2[i]);for(i=n;i0;i--){next=F[i];next--;pp=pk=p2[next];ww=w2[next];while(ww+w[i]M&&nextF[i-1]){next=next-1;pp=p2[next];ww=w2[next];}if(ww+w[i]=M&&nextF[i-1])px=pp+p[i];if(pxpk&&ww+w[i]=M){s[i]=1;M=M-w[i];printf(M=%d,M);}elses[i]=0;}for(i=1;i=n;i++)printf(%2d,s[i]);}6