解01背包问题的动态规划算法(共6页).doc

《解01背包问题的动态规划算法(共6页).doc》由会员分享，可在线阅读，更多相关《解01背包问题的动态规划算法(共6页).doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上解0/1背包问题的动态规划算法摘要：本文通过研究动态规划原理，提出了根据该原理解决背包问题的方法与算法实现，并对算法的正确性作了验证观察程序运行结果，发现基于动态规划的算法能够得到正确的决策方案且比穷举法有效关键字：动态规划；背包；约束条件；序偶；决策序列；支配规则1、引 言 科学研究与工程实践中，常常会遇到许多优化问题，而有这么一类问题，它们的活动过程可以分为若干个阶段，但整个过程受到某一条件的限制。这若干个阶段的不同决策的组合就构成一个完整的决策。0/1背包问题就是一个典型的在资源有限的条件下，追求总的收益最大的资源有效分配的优化问题。对于0/1背包问题，我们可以

2、这样描述：设有一确定容量为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、求解问题的动态规划原理与算法21动态规划原理的描述求解问题的动态规划有向前处理法向后处理法两种，这里使用向前处理法求解0/1背包问题。对于0/1背包问题，可

3、以通过作出变量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)=maxfi-1(X

4、),fi-1(X-wi)+pi （2） 为了能由前向后推而最后求解出FN（M），需从F0（X）开始。对于所有的X=0,有F0（X）=0，当X0时，有F0（X）等于负无穷。根据（2），可求出0XW1和X=W1情况下F1（X）的值。接着由（2）不断求出F2，F3，FN在X相应取值范围内的值。22 0/1背包问题算法的抽象描述(1) 初始化各个元素的重量Wi、效益值Pi、包的最大容量M；(2) 初始化0；(3) 生成Si；a 在中i-1找满足约束条件的第R对序偶；b 生成S1i ;c 清除不满足条件的序偶；d 将Sn-1中满足条件的序偶复制到Sn 中；（4）对Sn+1置初值；（5）若不满足循环次数转

5、（3）,否则转（）；（6）用回溯法确定决策序列；终止程序。23计算复杂性分析假设Si的序偶是|i |。在i的情况下，每个i由1i-1和1i归并而成，并且1i |=|i-1 |,因此i |4时效果更加明显，减少了搜索的范围，避免了穷举搜索，比穷举法有效，结束语通过将动态规划原理引入到解背包问题中，由于支配规则的高效性，使该算法比运用穷举思想的算法有效需要指出的是，由于它的时间复杂性为（n），背包问题是一个难问题。如果能够将它降为多项式复杂性，那么所有的难问题就都可以在多项式时间内求解，这将会大大提高现行些类问题的算法的可靠性与效率。在这方面，有待深入研究，也是值得研究的问题。参考文献：1 数据结

6、构：C语言版/严蔚敏等编著。2 语言程序设计：潭浩强编著。3 计算机算法基础:第二版/余祥宣等编著。用动态规划解0/1背包问题的源程序代码：#include#include#define n 6void DKNAP();main() int pn+1,wn+1; int M,m=1,i,j; for(i=1;i=n;i+) m=m*2; printf(nin put the weight and the p:); scanf(%d %d,&wi,&pi); printf(%d,m); printf(n in put the max weight M:); scanf(%d,&M); DKNAP

7、(p,w,M,m);void DKNAP(int p,int w,int M,int m) int p2m,w2m,pp,ww,px; int Fn+1,pk,q,k,l,h,u,i,j,next,max,sn+1; F0=1; p21=w21=0; l=h=1; F1=next=2; for(i=1;in;i+) k=l; max=0； u=l; for(q=l;q=h;q+) if(w2q+wi=M)&max=w2q+wi) u=q; max=w2q+wi; for(j=l;j=u;j+) pp=p2j+pi; ww=w2j+wi; while(k=h&w2kww) p2next=p2k;

8、 w2next=w2k; next+; k+; if(k=h&w2k=ww) if(ppp2next-1) p2next=pp; w2next=ww;next+; while(k=h&p2k=p2next-1)k+; while(k=h) p2next=p2k; w2next=w2k; next=next+1; k+; l=h+1; h=next-1; Fi+1=next; for(i=1;i0;i-) next=Fi; next-; pp=pk=p2next; ww=w2next; while(ww+wiM&nextFi-1) next=next-1; pp=p2next; ww=w2next; if(ww+wiFi-1)px=pp+pi; if(pxpk&ww+wi=M) si=1; M=M-wi;printf(M=%d ,M); else si=0; for(i=1;i=n;i+) printf(%2d ,si);专心-专注-专业