发布时间 : 星期六 文章第6讲 - - 动态规划专题讲座更新完毕开始阅读
}
if(sw<=c && sv<=d && sp>pmax)
{pmax=sp;cw=sw;cv=sv; // 通过比较求最大效益pmax for(i=1;i<=8;i++) y[i]=x[i]; } }
printf(\
printf(\
for(i=1;i<=8;i++) // 以表格形式输出结果 if(y[i]==1)
printf(\ printf(\}
（3）程序运行示例 input c:80 input d:150
input w1,v1,p1:10,19,28 input w2,v2,p2:12,23,35 input w3,v3,p3:15,29,44 input w4,v4,p4:18,35,55 input w5,v5,p5:20,38,58 input w6,v6,p6:16,31,47 input w7,v7,p7:14,27,41 input w8,v8,p8:22,40,60 c=80, d=150
i w(i) v[i] p(i) 1 10 19 28 4 18 35 55 5 20 38 58 6 16 31 47 7 14 27 41 w=78, v=150, pmax=229 3．动态规划设计
当物品种数n从键盘输入确定，每一件物品的重量、容积与效益均为正整数时，可应用动态规划设计求解。 （1）算法设计
与以上一维的背包问题相同，二维的0?1背包问题同样要求xi?{0,1},即物品i不能拆开，
或者整体装入，或者不装。与以上一维的背包问题不同，二维的0?1背包问题增加了容积的 限制。
目标函数：max?xipi
i?1n约束条件： ?xiwi≤c,i?1n?xv≤d,
iii?1n
xi?{0,1},c,d,wi,vi,pi?N?,i?1,2,?,n
1） 建立递推关系
设三维数组m(i,j,k)为背包载重量j，容积为k，可取物品范围为：i,i+1,?,n的最大效益值。则
当0≤j 不装入物品i，这时最大效益值为m(i+1,j,k)； 装入物品i，这时已产生效益p(i)；剩余载重量为j?w(i)，可装容积为k?v(i)，可以选择物品i+1,?,n来装，最大效益值为m(i+1, j?w(i),k?v(i))+p(i)。 我们期望的最大效益值是两者中的最大者。于是有递推关系 0≤j＜w(i)or0≤k＜v(i)?m(i?1,j,k)m(i,j,k)?? max(m(i?1,j,k),m(i?1,j?w(i),k?v(i))?p(i))?j≥w(i)且k≥v(i) 其中w(i)、v(i)、p(i)均为正整数，x(i)∈{0,1}, i=1,2,?,n。 边界条件为： m(n,j,k)=p(n)，当j≥w(n)且k≥v(n)； m(n,j,k)=0， 当j for(j=0;j<=c;j++) for(k=0;k<=d;k++) if(j>=w[n] && k>=v[n]) m[n][j][k]=p[n]; // 首先计算m(n,j,k) else m[n][j][k]=0; for(i=n?1;i>=1;i??) // 逆推计算m(i,j,k) for(j=0;j<=c;j++) for(k=0;k<=d;k++) if(j>=w[i] && k>=v[i] && m[i+1][j][k] m[i][j][k]=m[i+1][j][k]; printf(\最优值为%d\3） 构造最优解 if(m[i][cw][cv]>m[i+1][cw][cv]) 则x(i)=1，装载第i件物品； （其中cw=c开始，cw=cw?x(i)*w(i); cv=d开始，cv=cv?x(i)*v(i)） 否则，x(i)=0，不装载第i件物品。 最后，所装载的物品效益之和与最优值比较，决定第n件物品是否装载。 4） 算法复杂度分析 以上动态规划算法的时间复杂度为O(ncd)，空间复杂度也为O(ncd)。 以下程序实现中c按5n,d按8n设置，必要时可进行修改。当n,c,d比较大时，算法所占空间很大，大大限制了该算法的求解范围。 （2）二维0/1背包问题C程序设计 // 二维0/1背包问题 #include {int p[N],w[N],v[N],m[N][5*N][8*N]; int i,j,k,c,d,cw,cv,n,sw,sv,sp; printf(\// 输入已知条件 printf(\ printf(\ for(i=1;i<=n;i++) {printf(\ scanf(\ } for(j=0;j<=c;j++) for(k=0;k<=d;k++) if(j>=w[n] && k>=v[n]) m[n][j][k]=p[n]; // 首先计算m(n,j,k) else m[n][j][k]=0; for(i=n?1;i>=1;i??) // 逆推，计算m(i,j,k) for(j=0;j<=c;j++) for(k=0;k<=d;k++) if(j>=w[i] && k>=v[i] && m[i+1][j][k] m[i][j][k]=m[i+1][j][k]; cw=c; cv=d; printf(\printf(\背包所装物品：\\n\ printf(\ for(sp=0,sw=0,sv=0,i=1;i<=n?1;i++) // 以表格形式输出结果 if(m[i][cw][cv]>m[i+1][cw][cv]) { cw?=w[i];cv?=v[i]; sw+=w[i];sv+=v[i];sp+=p[i]; printf(\ } if(m[1][c][d]?sp==p[n]) {sw+=w[i];sv+=v[i];sp+=p[i]; printf(\ } printf(\} 运行程序，输入与输出如下。 input n: 8 input c: 40 input d: 70 input w1,v1,p1: 8,14,20 input w2,v2,p2: 6,10,14 input w3,v3,p3: 11,19,28 input w4,v4,p4: 13,22,31 input w5,v5,p5: 5,9,12 input w6,v6,p6: 15,25,37 input w7,v7,p7: 12,20,27 input w8,v8,p8: 9,15,22 c=40, d=70 背包所装物品： i w(i) v[i] p(i) 3 11 19 28 5 5 9 12 6 15 25 37 8 9 15 22 sw=40, sv=68, pmax=99 4．以上两种算法比较 穷举法只适合于物品种数事先给定的情形，程序设计较为呆板。当物品种数n比较大时， n 时间复杂度为O(2)，程序运行时间长。该算法的空间复杂度为O(n)，而且当各种物品的重量、容积与效益不是整数时同样有效（修改相应的变量类型即可）。 动态规划可适应于物品种数n从键盘给定的情形，程序设计比较灵活。时间复杂度为 3 O(ncd)，空间复杂度高于O(n)，当n、c、d较大时所占内存空间大。而且不适合各种物品