cw=c;
printf(\
printf(\背包所装物品：\\n\
printf(\
for(sp=0,sw=0,i=1;i<=n?1;i++) // 以表格形式输出结果 if(m[i][cw]>m[i+1][cw])
{cw?=w[i];sw+=w[i];sp+=p[i];
printf(\ }
if(m[1][c]?sp==p[n]) {sw+=w[i];sp+=p[i];
printf(\ }
printf(\}
4．动态规划顺推求解 （1）算法设计
目标函数、约束条件与分阶段同上。 1) 建立递推关系
设g(i,j)为背包容量j，可取物品范围为：1,2,?,i的最大效益值。则 当0≤j 不装入物品i，这时最大效益值为g(i?1,j)； 装入物品i，这时已产生效益p(i)，背包剩余容积j?w(i)可以选择物品1,2,?,i?1来装，最大效益值为g(i?1,j?w(i))+p(i)。期望的最大效益值是两者中的最大者。 于是有递推关系 0≤j＜w(i)?g(i?1,j)g(i,j)???max(g(i?1,j),g(i?1,j?w(i))?p(i))j≥w(i) 其中w(i),p(i)均为正整数，x(i)∈{0,1}, i=1,2,?,n。 边界条件为： g(1, j)=p(1), 当j≥w(1)； g(1, j)=0, 当j for(j=0;j<=c;j++) if(j>=w[1] ) g[1][j]=p[1]; // 首先计算g(1,j) else g[1][j]=0; for(i=2;i<=n;i++) // 顺推计算g(i,j) for(j=0;j<=c;j++) if(j>=w[i] && g[i?1][j] 若g(i,cw)>g(i?1,cw), i=n,n?1,?,2 则x(i)=1；装载w(i)。其中cw=c开始，cw=cw?x(i)*w(i). 否则，x(i)=0，不装载w(i)。 最后，所装载的物品效益之和与最优值比较，决定w(1)是否装载。 （2）0/1背包问题C程序设计 // 顺推0/1背包问题 #include {int p[N],w[N],g[N][5*N]; int i,j,c,cw,n,sw,sp; printf(\// 输入已知条件 printf(\ for(i=1;i<=n;i++) {printf(\ scanf(\ } for(j=0;j<=c;j++) if(j>=w[1] ) g[1][j]=p[1]; // 首先计算g(1,j) else g[1][j]=0; for(i=2;i<=n;i++) // 顺推计算g(i,j) for(j=0;j<=c;j++) if(j>=w[i] && g[i?1][j] g[i][j]=g[i?1][j]; cw=c; printf(\ printf(\背包所装物品： \\n\// 构造最优解 printf(\ for(sp=0,sw=0,i=n;i>=2;i??) // 以表格形式输出最优解 if(g[i][cw]>g[i?1][cw]) {cw?=w[i];sw+=w[i];sp+=p[i]; printf(\ } if(g[n][c]?sp==p[1]) {sw+=w[i];sp+=p[i]; printf(\ } printf(\} 运行程序，输入原始数据后，得： input n:6 input c:60 input w1,p1:15,32 input w2,p2:17,37 input w3,p3:20,46 input w4,p4:12,26 input w5,p5:9,21 input w6,p6:14,30 c=60 背包所装物品： i w(i) p(i) 2 17 37 3 20 46 5 9 21 6 14 30 w=60, pmax=134 即装第2、3、5、6四件，装包重量为60，获取最大效益134。 5．算法复杂度分析 以上动态规划算法的时间复杂度为O(nc)，空间复杂度也为O(nc)。通常c>n，因而算法 2 的时间复杂度与空间复杂度均高于O(n)。 6.5.2 二维0?1背包问题 1. 案例提出 已知n种物品和一个可容纳c重量、d容积的背包，物品i的重量为wi，容积 为vi，产生的效益为pi。在装包时物品i可以装入，也可以不装，但不可拆开装，物品i可 产生的效益为xipi，这里xi?{0,1},c,wi,pi?N?。问如何装包，使所得效益最大。 在上案例基础上增加容积的约束条件即为二维0?1背包问题。 下面应用穷举与动态规划两种算法设计求解。 2．给定物品种数时穷举设计 （1）算法设计 当给定物品种数时，例如对8种物品，每一种物品的重量w(k)、容积v(k)与效益p(k)(1≤k≤8)可任意从键盘输入，应用穷举设计，可设计8重循环：第一种物品的循环变量为x(1)，其取值为0或1；第2种物品的循环变量为x(2)，其取值也为0或1；??。因而穷举可由循环结构 for(x[1]=0;x[1]<=1;x[1]++) for(x[2]=0;x[2]<=1;x[2]++) ?? for(x[8]=0;x[8]<=1;x[8]++) 来实现。对每一组x(k)(1≤k≤8)，计算重量之和sw，容积之和sv与效益之和sp，当sw≤c且sv≤d时通过sp与pmax比较求取效益的最大值pmax。 n 以上穷举设计的时间复杂度为O(2)，空间复杂度为O(n)。 （2）给定物品种数时的穷举程序实现 // 二维0/1背包问题穷举求解 #define N 9 void main() {int p[N],w[N],v[N],x[N],y[N]; int i,k,c,d,cw,cv,sw,sv,sp,pmax; printf(\输入已知条件 printf(\ for(k=1;k<=8;k++) {printf(\ scanf(\ } pmax=0; for(x[1]=0;x[1]<=1;x[1]++) for(x[2]=0;x[2]<=1;x[2]++) for(x[3]=0;x[3]<=1;x[3]++) for(x[4]=0;x[4]<=1;x[4]++) for(x[5]=0;x[5]<=1;x[5]++) for(x[6]=0;x[6]<=1;x[6]++) for(x[7]=0;x[7]<=1;x[7]++) for(x[8]=0;x[8]<=1;x[8]++) {for(sw=0,sv=0,sp=0,k=1;k<=8;k++) {sw=sw+x[k]*w[k]; // 求物品重量之和 sv=sv+x[k]*v[k]; // 求物品容积之和 sp=sp+x[k]*p[k]; // 求物品效益之和
