发布时间 : 2024/5/11 3:12:09 星期六 文章第6讲 - - 动态规划专题讲座更新完毕开始阅读

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

{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]; // 求物品效益之和