发布时间 : 星期五 文章第6讲 - - 动态规划专题讲座更新完毕开始阅读
#include
{int n,c1,c2,i,j,s,cw,sw,w[N],m[N][N];
printf(\ printf(\ s=0;
for(i=1;i<=n;i++) // 输入n个集装箱重量整数 {scanf(\
if(s>c1+c2) return; // 确保n个集装箱重量之和不大于c1+c2 printf(\集装箱重量：\ for(i=1;i<=n;i++)
printf(\
printf(\
printf(\ for(j=0;j for(j=w[n];j<=c1;j++) m[n][j]=w[n]; // 首先计算m(n,j) for(i=n?1;i>=1;i??) // 逆推计算m(i,j) for(j=0;j<=c1;j++) if(j>=w[i] && m[i+1][j] m[i][j]=m[i+1][j]; printf(\// 得最优值m(1,c1) if(m[1][c1]<=c1 && m[1][c1]>=s?c2) // 判断是否有解 {printf(\ cw=m[1][c1]; for(sw=0,i=1;i<=n?1;i++) // 构造最优解，输出船1的装载 if(m[i][cw]>m[i+1][cw]) {cw?=w[i];sw+=w[i]; printf(\ w[i]=0; // w(i)装载后赋0,为装船2作准备 } if(m[1][c1]?sw==w[n]) {printf(\ sw+=w[n]; w[n]=0; } printf(\ printf(\ for(sw=0,i=1;i<=n;i++) // 输出船2的装载 if(w[i]>0) {sw+=w[i]; printf(\ } printf(\ } else printf(\此装载问题无解！\// 输出无解信息 } 4．程序运行与说明 运行程序，输入： input c1,c2:120,126 input n:15 集装箱重量：26 19 24 13 10 20 15 12 6 5 22 7 17 27 20 n=15,s=243 c1=120, c2=126 maxc1=120 C1: 15 12 22 7 17 27 20 (120) C2: 26 19 24 13 10 20 6 5 (123) 注意：上述所求解的装载问题中，要求各个集装箱的重量与两船的载重量c1,c2均为正整数。 6.5 0-1背包问题 0?1背包问题是应用动态规划设计求解的典型例题。本节在应用动态规划采用逆推与顺推两种设计求解一般0?1背包问题基础上，拓广到带两个约束条件的二维0?1背包问题的设计求解。 6.5.1 0?1背包问题 1. 案例提出 已知n种物品和一个可容纳c重量的背包，物品i的重量为wi，产生的效益为 pi。在装包时物品i可以装入，也可以不装，但不可拆开装。物品i可产生的效益为xipi， 这里xi?{0,1},c,wi,pi?N?。问如何装包，所得装包总效益最大。 2．最优子结构特性 0?1背包的最优解具有最优子结构特性。设(x1,x2,?,xn),xi?{0,1}是0?1背包的最优解， 那么(x2,x3,?,xn)必然是0?1背包子问题的最优解：背包载重量c?x1w1，共有n?1件物品， 物品i的重量为wi，产生的效益为pi，2≤i≤n。若不然，设(z2,z3,?,zn)是该子问题的最 优解，而(x2,x3,?,xn)不是该子问题的最优解，由此可知 2≤i≤n?zipi＞2≤i≤n?xipi 且 x1w1?2≤i≤n?ziwi≤c 因此 x1p1?2≤i≤n?zipi＞?xipi 且 x1w1?1≤i≤n2≤i≤n?ziwi≤c 显然(x1,z2,z3,?,zn)比(x1,x2,?,xn)收益更高，(x1,x2,?,xn)不是背包问题的最优解， 与 假设矛盾。因此，(x2,x3,?,xn)必然是0?1背包子问题的一个最优解。最优性原理对0?1 背 包问题成立。 3．动态规划逆推求解 （1）算法设计 与一般背包问题不同，0?1背包问题要求xi?{0,1},即物品i不能折开，或者整体装入， 或者不装。当约定每件物品的重量与效益均为整数时，可用动态规划求解。 按每一件物品装包为一个阶段，共分为n个阶段。 目标函数：max?xipi i?1n,i?1,2,?,n) 约束条件：?xiwi≤c,(xi?{0,1},c,wi,pi?N?i?1n1) 建立递推关系 设m(i, j)为背包容量j，可取物品范围为i,i+1,?,n的最大效益值。则 当0≤j 不装入物品i，这时最大效益值为m(i+1,j)； 装入物品i，这时已产生效益p(i)，背包剩余容积j?w(i)，可以选择物品i+1,?,n来装，最大效益值为m(i+1,j?w(i))+p(i)。 我们期望的最大效益值是两者中的最大者。于是有递推关系 0≤j＜w(i)?m(i?1,j)m(i,j)?? max(m(i?1,j),m(i?1,j?w(i))?p(i))j≥w(i)?其中w(i),p(i)均为正整数，x(i)∈{0,1}, i=1,2,?, n。 边界条件为: m(n,j)=p(n), 当j≥w(n)； m(n,j)=0, 当j for(j=0;j<=c;j++) if(j>=w[n] ) m[n][j]=p[n]; // 首先计算m(n,j) else m[n][j]=0; for(i=n?1;i>=1;i??) // 逆推计算m(i,j) for(j=0;j<=c;j++) if(j>=w[i] && m[i+1][j] m[i][j]=m[i+1][j]; printf(“最优值为%d”,m(1,c)); 3) 构造最优解 若m(i,cw)>m(i+1,cw), i=1,2,?,n?1 则x[i]=1；装载w(i)。其中cw=c开始，cw=cw?x(i)*w(i)。 否则，x(i)=0,不装载w(i)。 最后，所装载的物品效益之和与最优值比较，决定w(n)是否装载。 （2）0/1背包问题逆推C程序实现 // 逆推0/1背包问题 #include {int p[N],w[N],m[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[n] ) m[n][j]=p[n]; // 首先计算m(n,j) else m[n][j]=0; for(i=n?1;i>=1;i??) // 逆推计算m(i,j) for(j=0;j<=c;j++) if(j>=w[i] && m[i+1][j] m[i][j]=m[i+1][j];