第6讲 - - 动态规划专题讲座

#include #define N 100 void main()

{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 #define N 50 void main()

{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];