第6讲动态规划专题讲座

第6章动态规划

6.1动态规划概述

动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代

美国数学家贝尔曼(RechardBellman)等人在研究多阶段决策过程的优化问题时，提出

了著名的最优性原理，把多阶段决策过程转化为一系列单阶段问题逐个求解，创立了解决

多阶段过程优化问题的新方法一一动态规划。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛

的应用。例如最短路线、库存管理、资源分配、装载等问题，用动态规划方法比用其它方

法求解更为方便。

6.1.1动态规划的概念

动态规划所处理的对象是多阶段决策问题。多阶段决策问题，是指这样的一类特殊的

活动过程，问题可以分解成假设干相互联系的阶段，在每一个阶段都要做出决策，形成一

个决策序列，该决策序列也称为一个策略。对于每一个决策序列，可以在满足问题的约束

条件下用一个数值函数(即目标函数)衡量该策略的优劣。多阶段决策问题的最优化求解

目标是获取导致问题最优值的最优决策序列(最优策略)，即得到最优解。

例6.16种物品和一个可载重量为60的背包，物品i…,6)的重量分别为

[15,17,20,12,9,14),产生的效益分别为(32,37,46,26,21,30)o在装包时每一件物品可

以装入，也可以不装，但不可拆开装。确定如何装包，使所得装包总效益最大。

这就是一个多阶段决策问题，装每一件物品就是一个阶段，每一个阶段都要有一个决

策：

这一件物品装包还是不装。

这一装包问题的约束条件为：

/=1

目标函数为：maxZ%P"£{()」}

»=i

对于这6个阶段的问题，如果每一个阶段都面临2个选择，那么共存在26个决策序列。

应用贪心算法，按单位重量的效益从大到小装包，得第1件与第6件物品不装，依次装第

5、3、

2、4件物品，这就是一个决策序列，或简写为序列(O,1,1,1,1,0),该策略所得总效益为

130o第1件与第4件物品不装，第2、3、5、6件物品装包,或简写为序列(0,1,1,0,1,1),

这一决策序列的总载重量为60,满足约束条件，使目标函数即装包总效益达最大值134,

即最优值为134o

因而决策序列10,1,1,0,1,1)为最优决策序列，即最优解，这是应用动态规划求解

的目标。

在求解多阶段决策问题中，各个阶段的决策依赖于当时的状态并影响以后的开展，即引

起状态的转移。一个决策序列是随着变化的状态而产生的。应用动态规划设计使多阶段决策

过程到达最优(本钱最省，效益最高，路径最短等)，依据动态规划最优性原理：”作为整个

过程的最优策略具有这样的性质，无论过去的状态和决策如何，对前面的决策所形成的状态

而言，余下的诸决策必须构成最优策略”。也就是说，最优决策序列中的任何子序列都是最

优的。

“最优性原理”用数学语言描述：假设为了解决某一多阶段决策过程的优化问题，需

要依次作出n个决策及D%…,D”，如假设这个决策序列是最优的，对于任何一个整数k,

l<k<n,不管前面k个决策是怎样的，以后的最优决竟只取决于由前面决策所确定的当前

状态，即以后的决策序列DkT,Dk+2,…,D”也是最优的。

最优性原理表达为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最

优解时，那么称该问题具有最优子结构特性。最优子结构特性使得在从较小问题的解构造

较大问题的解时，只需考虑子问题的最优解，从而大大减少了求解问题的计算量.最优子

结构特性是动态规划求解问题的必要条件。

例如，在以后案例中求得在数字串847313926中插入5个乘号，使乘积最大的最优解

为：

8*4*731*3*92*6=38737152

该最优解包含了在84731中插入2个乘号使乘积最大，插入方式为8*4*731；

在7313中插入1个乘号使乘积最大，插入方式为731*3；

在3926中插入2个乘号使乘积最大，插入方式为3*92*6。

这些子问题的最优解，这就是最优子结构特性。

最优性原理是动态规划的根底。任何一个问题，如果失去了这个最优性原理的支持，

就不可能用动态规划设计求解。能采用动态规划求解的问题都需要满足以下条件：

(1)问题中的状态必须满足最优性原理；

(2)问题中的状态必须满足无后效性。

所谓无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态

无关，当前状态是对以往决策的总结”。

6.1.2动态规划实施步骤

动态规划求解最优化问题，通常按以下几个步骤进行。

(1)把所求最优化问题分成假设干个阶段，找出最优解的性质，并刻划其结构特性。

最优子结构特性是动态规划求解问题的必要条件，只有满足最优子结构特性的多阶段

决策问题才能应用动态规划设计求解。

(2)将问题开展到各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递

推(或递归)关系，并确定初始(边界)条件。

通过设置相应的数组表示各个阶段的最优值，分析归纳出各个阶段状态之间的转移关

系，是应用动态规划设计求解的关键。

(3)应用递推[或递归)求解最优值。

递推(或递归)计算最优值是动态规划算法的实施过程。具体应用与所设置的表示各

个阶段最优值的数组密切相关。

(4)根据计算最优值时所得到的信息，构造最优解。

构造最优解就是具体求出最优决策序列。通常在计算最优值时，根据问题具体实际记

录更多的信息，根据所记录的信息构造出问题的最优解。

以上步骤前3个是动态规划设计求解最优化问题的根本步骤。当只需求解最优值时，

第4个步骤可以省略。假设需求出问题的最优解，那么必须执行第4个步骤。

6.2最长子序列探索

本节应用动态规划探索两个典型的子序列问题：最长非降子序列与两个序列的最长

公共子序列。

6.2.1最长非降子序列

1.案例提出

给定一个由n个正整数组成的序列，从该序列中删除假设干个整数，使剩下的整数组

成非降子序列，求最长的非降子序列。

例如，由12个正整数组成的序列为：

48,16,45,47,52,46,36,28,46,69,14,42

请在序列中删除假设干项，使剩下的项为非降(即后面的项不小于后面的项)序列，

剩下的非降序列最长为多少项？

2.递推实现动态规划没计

设序列的各项为…,a[n]]可随机产生，也可从键盘依次输入)，对每一个

整数操作为一个阶段，共为n个阶段。

(1)建立递推关系

设置b数组，b[i]表示序列的第i个数(保存第i个数)到第n个数中的最长非降子

序列的长度，i=l,2,…,n。对所有的j>i,比拟当a[j]2a[i]时的b[j]的最大值，显然

b[i]为这一最大值加1,表示加上a[i]本身这一项。

因而有递推关系：

b[i]=max(b[j])+l(a[j]2a[i],lWi<jWn)

边界条件：b[n]=l

(2)逆推计算最优值

b[n]=l;

for(i=n-l;i>=l;i—)

{max=O;for(j=i+l;j<=n;j++)

if(a[i]<=a[j]&&b[j]>max)

max=b[j];

b[i]=max+1;//逆推得b[i]

)

逆推依次求得b[n-l]]…,b[l],比拟这n-1个值得其中的最大值Imax,即为所求的

最长非降子序列的长度即最优值。

(3)构造最优解

从序列的第1项开始，依次输出b[i]分别等于Imax,lmax-1,•••,1的项a[i],这就是

所求的一个最长非降子序列。

(4)递推实现动态规划程序设计

//递推实现动态规划

#include<stdio.h>

#include<stdlib.h>

4include<time.h>

voidmain()

{inti,j,n,t,x,max,Imax,a[2000],b[2000];

t=time(0)%1000;srand(t);//随机数发生器初始化

printf(，zinputn(n<2000):;

scanf(〃％d〃，&n);

for(i=l;i<=n;i++)

{a[i]=rand()%(5*n)+10;//产生并输出n个数组成的序列

printf(z/%d",a[i]);

)

b[n]=l;lmax=0;

for(i=n-l;i>=l;i—)//逆推求最优值Imax

{max=0;

for(j=i+l;j<=n;j++)

if(a[i]<=a[j]&&b[j]>max)

max=b[j];

b[i]=max+l;//逆推得b[i]

if(b[i]>lmax)lmax=b[i];//比拟得最大非降序列长

)

printf(，z\nL=%d.\n〃，Imax);//输出最大非降序列长

x=lmax;

for(i=l;i<=n;i++)

if(b[i]==x)

{printfC%d”,a[i]);x-;}//输出一个最大非降序列

3.递归实现动态规划设计

(1)建立递归关系

设q(i)表示序列的第i个数(保存第i个数)到第n个数中的最长非降子序列的长度,

i=1,2,…,n。对所有的j>i,比拟当a[j]2a[i]时的q(j)的最大值,显然q(i)为这一最

大值加1,表示加上a[i]本身这一项。

因而有递归关系：

q(i)=max(q(j))+l(a[j]lWi<jWn)

递归出口：q(n)=l

(2)递归函数设计

intq(inti)

{intj,f,max;

if(i==n)f=l;

else

{max=0;

for(j=i+l;j<=n;j++)

if(a[i]<=a[j]&&q(j)>max)

max二q(j);

f=max+l;

)

returnf;

(3)在主函数中依次调用q(n-l),-,q(l),比拟这n-1个值得其中的最大值Imax,

即为所求的最长非降子序列的长度即最优值。

(4)构造最优解

从序列的第1项开始,依次输出q⑴分别等于Imax,lmax-1,1所那就的项a[i],

这就是所求的一个最长非降子序列。

(5)递归实现动态规划程序设计

//递归实现动态规划

ttinclude<stdio.h>

^include<stdlib.h>

ttinclude<time.h>

inti,n,a[2000];

voidmainO

{intt,x,Imax;intq(inti);

t=time(0)%1000;srand(t);//随机数发生滞初始化

printf(z，inputn(n<2000)：z，);

scanf(〃％d〃，&n);

for(i=l;i<=n;i++)

{a[i]=rand()%(5*n)+10;//产生并输出n个数组成的序列

printf(^d〃，a[i]);

lmax=O;

for(i=n-l;i>=l;i­)

if(q(i)>lmax)lmax=q(i);//比拟得最大非降序列长

printf(/z\nL=%d.\n，z,Imax);//输出最大非降序列长

x=lmax;

for(i=l;i<=n;i++)

if(q(i)==x)

(printf(z/%d”,a[i]);x—；｝//输出一个最大非降序列

)

4.程序运行例如与讨论

运行程序,inputn(n<2000):12

481645475246362846691442

L=5.

1645475269

注意，所给序列长度为5的非降子序列可能有多个，这里只输出其中一个。

由上可知，在动态规划设计中，最优值可经递推得到，也可经递归得到。一般地，应

用递推效率更高些，以下各案例的动态规划设计中均应用递推得最优值。

6.2.2最长公共子序列

一个给定序列的子序列是在该序列中删去假设干个元素后所得到的序列。用数学语言

表述，

给定序列X=｛%,工2，，4｝，另一序列2=｛Z],Z2，,zj,X的子序列是指存在一个严格递

增

下标序列｛小2,4｝使得对于所有j=l，2,…,k有4=叼。例如，序列Z=｛4d,c,a｝是序

列

X=｛a,〃,c,d,c,瓦〃｝的一个子序列，或按紧凑格式书写，序列“bdca"是"abcccba”的

一个子序列。

假设序列Z是序列X的子序列，又是序列Y的子序列，那么称Z是序列X与Y的公共

子序列。例如，序列“bcba”是“abcbdab”与“bdcaba”的公共子序列。

1.案例提出

给定两个序列X=｛x，w，，怎,｝和丫=｛加以，，”｝，找出序列X和Y的最长

公共子序列。

例如,给出序列X：hsbafdreghsbacdba与序列Y：acdbegshbdrabsa,这两个序列的

最长公共子序列如何求得？

2.动态规划算法设计

求序列X与Y的最长公共子序列可以使用穷举法：列出X的所有子序列，检查X的每

一个子序列是否也是Y的子序列，并记录其中公共子序列的长度，通过比拟最终求得X与

Y的最长公共子序列。对于一个长度为m的序列X,其每一个子序列对应于下标集｛1,2,…,m)

的一个子集，即X的子序列数目多达才个。由此可见应用穷举法求解是指数时间的。

最长公共子序列问题具有最优子结构性质，应用动态规划设计求解。

(1)建立递推关系

设序列X=｛5,电,，4｝和Y=｛芦,丁2，，%｝的最长公共子序列为Z=｛Z],Z2，,zj,

,xm｝与｛x，%i，,%｝(i=0,L…,m;j=0,1,…，n)的最长公共子序列的长度为

c(i,j)o

假设i=m+l或j=n+L此时为空序列，c(i,j)=0(边界条件)。

假设x(l)=y(l),那么有z⑴=x⑴,c(l,D=c(2,2)+l(其中1为z⑴这一项);

假设x(l)Wy(D,那么C(1,1)取C⑵1)与c(l,2)中的最大者。

一般地,假设x(i)=y(j),那么c(i,j)=c(i+l,j+l)+l；

假设x(i)#y(j),那么c(i,j)=max(c(i+1,j),c(i,j+1))o

因而归纳为递推关系：

边界条件：c(i,j)=O(1初+1或j=n+l)

(2)逆推计算最优值

根据以上递推关系，逆推计算最优值c(0,0)流程为：

for(i=0;i<=m;i++)c[i][n]=0;//赋初始值

for(j=0;j<=n;j++)c[m][j]=0;

for(i=m-l;i>=0;i—)//计算最优值

for(j=n-l;j>=0;j—)

if(x[i]==y[j])

c[i][j]=c[i+l][j+l]+l;

elseif(c[i][j+l]>c[i+l][j])

c[i][j]=c[i][j+l];

elsec[i][j]=c[i+l][j];

printf("最长公共子串的长度为：%d?/,c[0][0]);〃输出最优值

以上算法时间复杂度为0(mn)。

(3)构造最优解

为构造最优解，即具体求出最长公共子序列，设置数组s(i,j),当x(i)=y(j)时

s(i,j)=l；当x⑴Wy(j)时s(i,j)=0。

X序列的每一项与Y序列的每，一项逐一比拟，根据s(i,j)与c(i,j)取值具体构造最长

公共子序列。实施x(i)与y(j)比拟，其中i=0,1,…,mT;j=t,1,…,nT；变量t从。开

始取值，当确定最长公共子序列一项时，t=j+lo这样处理可防止重复取项。

假设s(i,j)=1且c(i,j)=c(0,0)时，取x(i)为最长公共子序列的第1项;

随后,假设s(i,j)=l且c(i,j)=c(0,0)T时,取x(i)最长公共子序列的第2项；

一般地，假设s(i,地=1且c(i,j)=c(0,0)-w时(w从0开始,每确定最长公共子序列

的一项，w增1),取x(i)最长公共子序列的第w项。

构造最长公共子序列描述：

for(t=0,w=0,i=0;i<=m-l;i++)

for(j=t;j<=n-l;j++)

if(s[i][j]=l&&c[i][j]=c[0][0]-w)

{printf('%c",x[i]);

w++;t=j+l;break;

)

(4)算法的复杂度分析

以上动态规划算法的时间复杂度为0(i?)。

3.最长公共子序列C程序实现

//最长公共子序列

#include<stdio.h>

#defineN100

voidmain()

{charx[N],y[N];

inti,j,m,n,t,w,c[N][N],s[N][N];

printf(〃请输入序列〃)；〃先后输入序列

scanfx);

printf(〃请输入序列y：〃);scanf("%s",y);

for(m=0,i=0;x[i]!=\0J;i++)m++;

for(n=0,i=0;y[i]!=,\0,;i++)n++;

for(i=0;i<=m;i++)c[i][n]=0;//赋边界值

for(j=0;j<=n;j++)c[m][j]=0;

for(i=m-l;i>=0;i—)〃递推计算最优值

for(j=n-l;j>=0;j—；

if(x[i]=y[j])

{c[i][j]=c[i+l][j+l]+l;

)

else

{s[i][j]=O;

if(c[i][j+l]>c[i+l][j])

c[i][j]=c[i][j+l];

elsec[i][j]=c[i+l][j];

}

printf(〃最长公共子序列的长度为：%d",c[0][0：);//输出最优值

printf(〃\n最长公共子序列为：〃)；//构造最优解

t=0;w=0;

for(i=0;i<=m-l;i++)

for(j=t;j<=n-l;j++)

if(s[i][j]==l&&c[i][j]==c[O][0]-w)

{printfx[i]);

w++;t=j+l;break;

)

prinlf(〃\n〃)；

}

运行程序例如：

请输入序列x：hsbafcreghsbacdba

请输入序列y：acdbcgshbdrabsa

最长公共子序列的长度为：9

最长公共子序列为：adcghbaba

6.3最优路径搜索

本节应用动态规划探记两类最优路径搜索问题，一类是点数值路径，即连接成路径的

每一个点都带有一个数值；另一类是边数值路径，即连接成路径的每一条边都带有一个数

值。

6.3.1点数值三角形的最优路径搜索

点数值三角形是一个二维数阵：三角形由n行构成，

22

第k行有k个点，每一个点都带有一个数值数。点数值三

1419

角形的数值可以随机产生，也可从键盘输入。

302510

最优路径通常由路径所经各点的数值和来确定。

8201227

1.案例提出

6253264

在一个n行的点数值三角形中，寻找从顶点开始每一

610106232

步可沿左斜(L)或右斜(R)向下至底的一条路径，使该

322921315324

路径所经过的点的数值和最小。

图6.17行点数值三角形

例如，n=7时给出的点数值三角形如图6.1所示，如何寻找从项到底的数值和最小路

径？该最优路径的数值和为多少？

2.动态规划算法设计

设点数值三角形的数值存储在二维数组a(n,n)o

(1)建立递推关系

设数组b(i,j)为点(i,j)到底的最小数值和，字符数组stm(i,j)指明点(i,j)向左或

向右的路标。b(i,j)与j)(i=n-l,…,2,1)的值由b数组的第i+1行的第j个元素与

第j+1个元素值的大小比拟决定，即有递推关系：

b(i,j)=a(i,j)+b(i+l,j+1);stm(i,j)="R”(b(i+l,j+l)<b(i+l,j))

b(i,j)=a(i,j)+b(i+l,j);stm(i,j)="L"(b(i+l,j+1)2b(i+1,j))

其中i=n-l,…,2,1

边界条件：b(n,j)=a(n,j),j=l,2,•••»n0

所求的最小路径数值和即问题的最优值为b(l,1)。

(2)逆推计算最优值

for(j=l;j<=n;j++)b[n][j]=a[n][j];

for(i=nT;i>=l;iT//逆推得

for(j=l;j<=i;j++)

if(b[i+l][j+l]<b[i+l][j])

(b[i][j]=a[i][j]+b[i+l][j+1][j]=R，；}

else

{b[i][j]=a[i][j]+b[i+l][j];stm[i][j]=C;}

Printf(zz%d，z,b(l,1));

(3)构造最优解

为了确定与并输出最小路径，利用stm数组从上而下查找：

先打印假设stm(l,l)="R"，那么下一个打印a(2,2),否则打印a(2,1)。

一般地，在输出i循环(i=2,3,-,n)中：

假设stm(iT,j)=“R”那么打印“T-"；a(i,j+1)；同时赋值

假设stm(iT,j)=“L”那么打印a(i,j)；

依此打印出最小路径，即所求的最优解.

(4)算法的复杂度分析

以上动态规划算法的时间复杂度为0(r),空间复杂度也为0(r)。

2.最小路径寻求与测试程序设计

//点数值三角形的最小路径

Sinclude<stdio.h>

Sinclude<stdlib.h>

#include<time.h>

voidmain()

{intn,i,j,t;

inta[50][50],b[50][50];charstm[50][50];

printf(〃请输入数字三角形的行数n:〃)；

scanf(绘d〃，&n);

t=time(0)%1000;srand(t);〃随机数发生器初始化

for(i=l;i<n;i++)j=rand();

for(i=l;i<=n;i++)

(for(j=l;j<=36-2*i;j++)printfC9;

for(j=l;j<=i;j++)

{a[i][j]=rand()/1000+1;

printf(绘4c1〃,a[i][j])；//产生并打印n行数字三角形

)

printfCV);

)

printf(〃请在以上点数值三角形中从顶开始每步可左斜或右斜至底〃)；

printf(〃寻找一条数字和最小的路径.\n〃)；

for(j=l;j<=n;j++)b[n][j]=a[n][j];

for(i=n-l;i>=l;i-)//逆推得

for(j=l;j<=i;j++)

if(b[i+l][j+l]<b[i+l][j])

(b[i][j]=a[i][j]+b[i+l][j+1];stm[i][j]-R';}

else{b[i][j]=a[i][j]+b[i+l][j];stm[i][j]=f;}

printf(〃最小路径和为:％d\n〃,b[l][1]);//输出最小数字和

printf(〃最小路径为:%[1]);j=l;//输出和最小的路径

for(i=2;i<=n;i++)

if(stm[i-l][j]=-If)

(printf("-R-%d〃,a[i][j+1]);j++;}

else

printf(v-L-%d，z,a[i][j]);

printfCW);

)

运行程序，对于数据如下图的点数值三角形，输出如下：

最小路径和为:74

最小路径为:22-R-l9-R-lO-L-l2-R-6-R-2-R-3

6.3.2边数值矩形的最优路径搜索

边数值矩形也是一个二维数阵：矩形由n行m列构成，每一行有n】T条横边，每一列

ffn-1条竖边，每一条边都带有一个数值。最优路径通常由路径所经各边的数值和来确定。

1.案例提出

1341.13.19.

n行m列的边数值矩阵，每一个点可向右或向

3232264224

卜两个去向，试求左上角顶点到右下角顶点的所经

3042.13.32.

边数值和最大的路径。**

112915

例如，给出一个4行5列的边数值矩形如图

22.19.38.

6.2所示，如何寻找从矩阵的左上角顶点到右下角2；3；

282842

顶点的数值和最大路径？该最优路径的数值和为

,•10.29.40.15.

多少？

图6.2一个4行5列的边数值矩形

2.动态规划算法设计

设矩阵的行数n,列数m,每点为(i,j),i=1,2,…,n；j=1,2,…,m。显然，该边数值

矩阵每行有mT条横向数值边，每列有n-1条纵向数值边。

从点(i,j)水平向右的边长记为r(i,j)(j〈m),点(i,j)向下的边长记为d(i,j)(i〈n)。

(1)建立递推关系

设a(i,j)为点(i,j)到右下角顶点的最大路程。st(i,j)为点(i,j)路标数组,其值

取为{dr'}。

a(i,j)的值由a(i+l,j)+d(i,j)与a(i,j+l)+r(i,j)比拟，取其较大者得到,即有递

推关系：

a(i,j)=max(a(i+l,j)+d(i,j),a(i,j+l)+r(i,j))

st(i,j)={d,'/}

其中i=l,2,…，n-1；j=l,2,•••,m-lo

注意到右边纵列与下边横行只有惟一出口，因而有边界条件：

a(i,m)=a(i+l,m)+d(i,m);i=n-l,n-2,1

a(n,j)=a(n,j+l)+r(n,j);m-2,•••,1

(2)逆推计算最优值

for(i=n-l;i>=l;i^

{a[i][m]=a[i+l][m]+d[i][m];st[i][m]=d*;}//右边纵列初始化

for(j=mT;j>=l;jT

{a[n][j]=a[n][j+l]4-r[n][j];st[n][j]=f;}//下边横行初始化

for(i二nT;i)=1;i—〃逆推求解a(i,j)

for(j=mT;j>=l;jT

if(a[i+l][j]+d[i][j]>a[i][j+l]+r[i][j])

{a[i][j]=a[i+l][j]+d[i][j];st[i][j]=d*;}

else

{a[i][j]=a[i][j+l]+r[i][j];st[i][j]^f;}

所求左上角顶点到右下角顶点的最大路程即最优值为a(l,1)。

(3)构造最优解

利用路标数组输出最优解,从点(1,1)即i=l,尸1开始判断:

if(st[i][j]==,d,)

{printfC-%d-,d[i][j]);i++;}

else

{printfC-%d-,r[i][j]);j++;}

必要时可打印出点座标。

(4)算法的复杂度分析

以上动态规划算法的时间复杂度为0(7)O

3.求边数值矩阵图的最大路径程序设计

//求边数值矩阵图的最大路径

^include<stdio.h>

#include<stdlib.h>

#include<time.h>

voidmain()

{intm,n,i,j,t,a[50][50],r[50][50],d[50][50];

charst[50][50];

t=time(0)%1000;srand(t);//随机数发生器初始化

printfC在矩形图中寻找一条路程最大的路径.\n〃)；

printfC请输入矩阵的行数n,列数用:〃)；

scanf(“/d,%d”,&n,如)；

for(i=l;i<=n;i++)

for(j=l;j<=m;j++)

a[i][j]=0;

printf("\n〃)；

for(i=l;i<=n-l;i++)//随机产生并打印数值边矩阵

{for(j=l;j<=m-l;j++)

{printf(z，.〃)；

r[i][j]=rand()/1000+10;printf("%3d",r[i][j]);}

printf(，z.\n〃)；

for(j=l;j<=m;j++)

{d[i][j]=rand()/1000+10;printfC%3d”,d[i][j]);}

printf(//\n，/);

)

for(j=l;j++)

{printfC.〃:i；

r[n][j]=rand0/1000+10;printfr[n][j]);}

printf(，z.\n〃)；

for(i=n-l;i>=l;i—)

{a[i][m]=a[i+l][m]+d[i][m];st[i][m]-d>;}

for(j=m-l;j>=l;j­)

{a[n][j]=a[n][j+l]+r[n][j];st[n][j]=r';}

for(i=n-l;i>=l;i­)

for(j=m-l;j>=l;j—)

if(a[i+l][j]+d[i][j]>a[i][j+l]+r[i][j])

{a[i][j]=a：i+l][j]+d[i][j];st[i][j]=d*;}

else

{a[i][j]=a：i][j+l]+r[i][j];st[i][j]=,r;}

printf(z，\n最大路程为：%d.〃,a[l][1]);//打印最大路程

printfC\n最大路径为：(1,1)")；

j=l;i=l;//打印最大路径

while(i<n|j<m)

if(st[i][j]==d')

{printf(f,d[i][j]);i++;

printf(〃(%d,%d)〃，i,j);)

else

{printfr[i][j]);j++;

printfC(%d,%d)，z,i,j);}

printf(〃\n〃)；

}

4.运行例如与说明

运行程序，对图所示4行5列矩阵得：

最大路程为：226.

最大路径为：

(1,1)-32-(2,1)-30-(2,2)-42-(2,3)-13-(2,4)-29-(3,4)-38-(3,5)-42-(4,5)

为操作简单，以上各例中的三角形或矩形的点数据或边数据是应用C语言的随机函数

产生的。对于求解某些实际路径问题，具体的点数据或边数据可把随机产生改为通过键盘

输入，然后进行搜索，确定最优路径。

6.4装载问题

1.案例提出

有n个集装箱要装上两艘载重量分别为cl,c2的轮船，其中集装箱i的重量为

叫，且汽叱Vq+c，2，qj叱w旷(不考虑集装箱的体积)。

1=1

试求解一个合理的装载方案，把所有n个集装箱装上这两艘船。

2.动态规划算法设计

(1)问题求解策略

试采用以下的装载策略：

1)首先将第一艘船尽可能装满；

2)将剩余的集装箱装上第二艘船。

设装载量为cl的船最多可装maxcl,如果满足不等式

那么装载问题有解。

装载问题不一定总有解。例如，当n=3,cl=c2=50,w={15,40,40},显然无法把这三个

集装箱装上这两艘轮船。当问题无解时，作无解说明。

(2)动态规划设计

为了求取maxcl,应用动态规划设计。

目标函数：maxgi,%

r=l

约束条件：t看吗Wq,(七G{OJ},CPW.eR+,i=l,2,…

1=1

按装载每一个集装箱为一个阶段，共分为n个阶段。

1)建立递推关系

设m(i,j)为船C1还有载重量为j,可取集装箱编号范围为：+…,n的最大装载

重量值。那么

当OWj<w(i)时,物品i不可能装入。m(i,j)与m(i+(j)相同。

而当j2w(i)时,有两种选择:

不装入物品i,这时最大重量值为m(i+l,j)；

装入物品i,这时已增加重量w(i),剩余载重容量为jf(i),可以选择集装箱i+1,…,n

来装，最大载重量值为m(i+l,j-w(i))+w(i)。我们期望的最大载重量值是两者中的最大者。

于是有递推关系

以上j、cl与w⑴均为正整数，i=l,2,…,n,

所求最优值为m(Lcl)。

2)递推计算最优值

for(j=0;j<w[n];j++)m[n][j]=O;

for(j=w[n];j<=cl;j++)m[n][j]=w[n];//首先计算m(n,j)

for(i=n-l;i>=l;i—)//逆推计算m(i,j)

for(j=0;j<=cl;j++)

if(j>=w[i]&&m[i+l][j]<m[i+l][j-w[i]]+w[i])

m[i][j]=m[i+l][j-w[i]]+w[i];

else

m[i][j]=m[i+l][j];

printfm[l][cl]);

(3)递推过程分析

例如，n=5,5个集装箱的重量分别为:w(1)=2,w(2)=5,w(3)=13,w(4)=8,w(5)=4,两船

的载重量分别为：cl=16,c2=18；

展示以上所述递推过程如下：

1)首先赋初值

m(5,0)=---=m(5,3)=0(不装w(5))

m(5,4)=m(5,5)二…二m(5,16)=4(装w(5))

2)递推过程展示

按递推关系分别列出"4,3,2,1时•m数组的取值如下：

表6.1推出n=4时m数纽值

j0-34〜78-1112〜16

m(4,j)04812

表6.2推出n=3时m数组值

J0〜34〜78-111213〜16

m(3,j)0481213

表6.3推出n=2时口数组值

J0-345〜789〜111213〜16

m(2,j)045891213

表6.4推出n刁时m数组值

J0-12〜345678

m(l,j)0245678

J9101112131415〜16

m(l,j)9101112131415

最后所得目标值即船C1的最大装载量为：ni(l,16)=15。注意到5个集装箱的总重量

为32,满足3278W15W16,此装载问题有解。

(4)构造最优解

构造最优解即给出所得最优值时的装载方案。

if(m[i][cw]>m[i+l][cw])(其中cw为当前的装载量，i=l,2,n-1)

装载w[i]；

else不装载w[i];

if(所载集装箱重量Wm(l,cl))装载w[n].

以上述举例说明：

由m(l,16)>m(2,16),装w⑴=2；

m(2,14)=m(3,14),不装w(2)；

m(3,14)>m(4,14),装w(3)=13；

w(l)+w(3)=15=m(l,16),不装w(5)。

于是得装载方案：

Cl:213(15)

C2:584(17)

(5)算法复杂度分析

以上动态规划算法的时间复杂度为O(ncl),空间复杂度也为O(ncl)。通常cl>n,因

而上述算法的时间与空间复杂度均高于0(南)。

2.装载问题的C程序实现

〃装载问题

#include<stdio.h>

tfdefineN100

voidmain()

{intn,cl,c2,i,j,s,cw,sw,w[N],m[N][N];

prinlf("inputcl,c2:〃)；scanf(，，%d,%d，z,&cl,&c2);

printf(，zinputn:〃)；scanf("%d〃,&n);

s=0;

for(i=l;i<=n;i++)//输入n个集装箱重量整数

{scanf(〃%d〃,s+=w[i];}

if(s>cl+c2)return;//确保n个集装箱重量之和不大于cl+c2

printf(〃集装箱重量：〃);

for(i=l;i<=n;i++)

printfC%dz，,w[i]);

printf(/z\nn=%d,s=%d”,n,s);

printf(z，\ncl=%d,c2=%d\n〃，cl,c2);

for(j=0;j<w[n];j++)m[n][j]=0;

for(j=w[n];j<=cl;j++)m[n][j]=w[n];//首先计算m(n,j)

for(i=n-l;i>=l;i—)//逆推计算m(i,j)

for(j=0;j<=cl;j^+)

if(j>=w[i]&&[j-w[i]]+w[i])

m[i][j]=m[i+l][j-w[i]]+w[i];

else

m[i][j]=m[i+l][j]；

printf(z，maxcl=%d\n/z,m[l][cl]);//得最优值

if(m[l][cl]<=cl&&m[l][cl]>=s-c2)//判断是否有解

{printf(〃C1:〃)；

cw=m[l][cl];

for(sw=0,i=l;i<=n-l;i++)〃构造最优解，输出船1的装载

if(m[i][cw]>m[i+l][cw])

{cw-=w[i];sw+=w[i];

printf(〃％3d〃，w[i]);

w[i]=0;〃w(i)装载后赋0,为装船2作准备

}

if(ni[1][c1]-sw—w[n])

{printf(/z%3dv,w[n]);

sw+=w[n];

w[n]=0;

}

printf(〃(%d)\n，z,sw);

printf(〃C2:〃)；

for(sw=0,i=l;i*n;i++)//输出船2的装载

if(w[i]>0)

{sw+=w[i];

printfC%3d”,w[i]);

)

printf(〃(%d)\n\sw);

)

elseprintf(〃此装载问题无解！〃)；//输出无解信息

)

4.程序运行与说明

运行程序，输入：

inputcl,c2:120,126

inputn:15

集装箱重量：261924131020151265227172720

n=15,s=243

cl=120,c2=126

maxcl=120

Cl:1512227172720(120)

C2:26192413102065(123)

注意：上述所求解的装载问题中，要求各个集装箱的重量与两船的载重量cLc2均为

正整数。

6.50-1背包问题

背包问题是应用动态规划设计求解的典型例题。本节在应用动态规划采用逆推与

顺推两种设计求解一般0T背包问题根底上，拓广到带两个约束条件的二维0T背包问题

的设计求解。

6.5.10-1背包问题

1.案例提出

n种物品和一个可容纳c重量的背包，物品i的重量为叫，产生的效益为

P,。在装包时物品i可以装入，也可以不装，但不可拆开装。物品i可产生的效益为天〃,.，

这里七6{0』},c,吗，Pi£2。问如何装包,所得装包总效益最大。

2.最优于结构特性

0-1背包的最优解具有最优子结构特性。设（5,与，，大”），为£{0,1}是0T背包的最优

解，

那么（马,不，，王）必然是CT背包子问题的最优解:背包载重量c-内吗，共有nT件物品,

物品i的重量为吗,产生的效益为化,2W0。假设不然,设心曰,・，z“）是该子问

题的最

优解，而（w，&，，4）不是该子问题的最优解，由此可知

Zz,Pi>z且X”+XZMWc

因此

工出+ZZXjP：且内叫

显然（玉/2*3,,,Z“）比（内,工2,•,工“）收益更高，（士,为，，X〃）不是背包问题的最优解,

与

假设矛盾。因此，（七,七，，王）必然是0T背包子问题的一个最优解。最优性原理对0T

背

包问题成立。

3.动态规划逆推求解

(1)算法设计

与一般背包问题不同，0T背包问题要求七£{0,1},即物品i不能折开，或者整体装

入，

或者不装。当约定每件物品的重量与效益均为整数时，可用动态规划求解。

按每一件物品装包为一个阶段，共分为n个阶段。

目标函数：maxZ%p；

/=1

约束条件：之工叱Wj(%£{(),1},C,吗,PiwN+,i=l,2,,几)

i=l

1)建立递推关系

设m(i,j)为背包容量j，可取物品范围为i,包1,…,n的最大效益值。那么

当0Wj<w⑴时,物品i不可能装入。最大效益值与m(i+l,j)相同。

而当jew(iM寸，有两个选择：

不装入物品i,这时最大效益值为m(i+l,j);

装入物品i,这时已产生效益p(i),背包剩余容积可以选择物品i+1,…,n

来装，最大效益值为m(i+Lj~w(i))+p(i)。

我们期望的最大效益值是两者中的最大者。于是有递推关系

其中w(i),p(i)均为正整数,x(i)e(0,1},i=l,2,•••,n。

边界条件为：

m(n,j)=p(n),当j^w(n)；

m(n,j)=0,当j<w(n)«

所求最大效益即最优值为ni(Lc)。

2)逆推计算最优值

for(j=0;j<=c;j++)

if(j>=w[n])m[n][j]=p[n];//首先计算m(n,j)

elsem[n][j]=0;

for(i=n-l;i>=l;i-^//逆推计算m(i,j)

for(j=0;j<=c;j++)

if(j>=w[i]&&m[i+l][j]<m[i+l][j^r[i]]+p[i])

m[i][j]=m[i+l][j-w[i]]+p[i];

else

m[i][j]=m[i+l][j];

printf("最优值为%d”，m(l,c));

3)构造最优解

假设m(i,cw)>m(i+l,cw),i=l,2,•••,nT

那么x[i]=l；装载w⑴。其中cw=c开始,cw=cw-x(i)*w(i)o

否则，x(i)=0,不装载\v(i)。

最后，所装载的物品效益之和与最优值比拟，决定w(n)是否装载。

(2)0/1背包问题逆推C程序实现

〃逆推0/1背包问题

^include<stdio.h>

#defineN50

voidmainO

{intp[N],w[N],m[N][5*N];

inti,j,c,cw,n,sw,sp;

printfC\ninputn:〃)；scanf&n);//输入条件

printf("inputc:〃)；scanf&c);

for(i=l;i<=n;i++)

{printf(/zinputw%d,p%d:",i,i);

scanf(〃％d,%d”,&w[i],&p[i]);

}

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=n4;i>=l;i-)//逆推计算m(i,j)

for(j=0;j<=c;j++)

if(j>=w[i]&&m[i+l][j]<m[i+l][j-w[i]]+p[i])

m[i][j]=m[i+l][j-w[i]]+p[i];

else

m[i][j]=m[i+l][j]；

cw=c;

printf(〃c=%d\n〃，c);

printf(〃背包所装物品：\n〃)；

printfCi\v⑴p⑴\n〃)；

for(sp=0,sw=0,i=l;i<=n-l;i++)//以表格形式输出结果

if(m[i][cw]>m[i+l][cw])

{cw-w[i];sw+=w[i];sp+=p[i];

printf(线2d%3d%3d\n〃，i,w[i],p[i：);

}

if(m[l][c]-sp==p[n])

{sw+=w[i];sp+=p[i];

printf(〃%2d%3d%3d\n，z,n,w[n],p[n]);

)

printfpmax=%d\n”,sw,sp);

4.动态规划顺推求解

(1)算法设计

目标函数、约束条