第 6 章 动态规划 掌握最优性原理与动态规划的概念 掌握应用动态规划设计求解0-1背包问题、装载问题与最优路径问题等多阶段决策典型案例 第 6 章 动态规划 教学要求 掌握最优性原理与动态规划的概念 掌握应用动态规划设计求解0-1背包问题、装载问题与最优路径问题等多阶段决策典型案例 本章重点 根据案例的实际构建状态转移方程 在案例求解基础上理解与掌握最优性原理

6.1 动态规划概述 1. 动态规划的概念 (1) 动态规划（Dynamic programming）是运筹学的一个分支，是求解决策过程最优化的数学方法。 (2) 动态规划处理的对象是多阶段决策问题。 (3) 多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。

2. 最优性原理 作为整个过程的最优策略具有这样的性质，无论过去的状态和决 策如何，对前面的决策所形成的状态而言，余下的诸决策必须构 成最优策略。最优决策序列中的任何子序列都是最优的。 “最优性原理”用数学语言描述：假设为了解决某一多阶段决策 过程的优化问题，需要依次作出n个决策D1,D2,…,Dn，如若这个 决策序列是最优的，对于任何一个整数k，1<k<n，不论前面k个 决策D1,D2,…,Dk是怎样的，以后的最优决策只取决于由前面决 策所确定的当前状态，即以后的决策序列Dk+1,Dk+2,…,Dn也是 最优的。 最优性原理体现为问题的最优子结构特性。最优子结构特性是动 态规划求解问题的必要条件。

例如，在数字串847313926中插入5个乘号，分为6个整数相乘，使乘积最大的最优解为： 8*4*731*3*92*6=38737152 3. 最优子结构特性举例 例如，在数字串847313926中插入5个乘号，分为6个整数相乘，使乘积最大的最优解为： 8*4*731*3*92*6=38737152 该最优解包含了以下子问题的最优解： 在84731中插入2个乘号使乘积最大为：8*4*731； 在7313中插入1个乘号使乘积最大为：731*3； 在3926中插入2个乘号使乘积最大为：3*92*6； 在4731392中插入3个乘号使乘积最大为：4*731*3*92。 这些子问题的最优解都包含在原问题的最优解中。 最优性原理是动态规划的基础。

4. 动态规划实施步骤 （1）把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。 4. 动态规划实施步骤 （1）把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。 （2）将问题各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，并确定初始条件。 分析归纳出各个阶段状态之间的转移关系是应用动态规划的关键。 （3）应用递推求解最优值。 递推计算最优值是动态规划算法的实施过程。 （4）根据计算最优值时所得到的信息，构造最优解。 构造最优解就是具体求出最优决策序列。

6.2 最长子序列探索 6.2.1 最长非降子序列 案例提出： 由n个正整数组成的序列，从该序列中删除若干个整数，使剩下的整数组成非降子序列，求最长的非降子序列。 例如，由12个正整数组成的序列为： 48，16，45，47，52，46，36，28，46，69，14，42 请在序列中删除若干项，使剩下的项为非降（即后面的项不小于前面的项）序列，非降序列最多为多少项？

1. 动态规划设计要点 设序列的各项为a[1],a[2],…,a[n] ，对每一个整数操作为一个阶段，共为n个阶段。 （1）建立递推关系 1. 动态规划设计要点 设序列的各项为a[1],a[2],…,a[n] ，对每一个整数操作为一个阶段，共为n个阶段。 （1）建立递推关系 设置b数组，b[i]表示序列的第i个数（含第i个数）到第n个数中的最长非降子序列的长度，i=1,2,…,n。对所有的j>i，比较当a[j]≥a[i]时的b[j]的最大值，显然b[i]为这一最大值加1，表示加上a[i]本身这一项。 因而有递推关系： b[i]=max(b[j])+1 (a[j]≥a[i],1≤i<j≤n) 边界条件：b[n]=1

（2）递推计算最优值 b[n]=1; for(i=n−1;i>=1;i−−) { max=0;for(j=i+1;j<=n;j++) if(a[i]<=a[j] && b[j]>max) max=b[j]; b[i]=max+1; // 逆推得b[i] } 逆推依次求得b[n−1],…,b[1]，比较这n−1个值得其中的最大值lmax，即为最优值。 以上动态规划算法的时间复杂度为O(n^2)。

6.3 最优路径搜索 6.3.2 边数值矩形的最优路径 案例提出： 6.3 最优路径搜索 6.3.2 边数值矩形的最优路径 案例提出： 已知n行m列的边数值矩阵，每一个点可向右或向下两个去向，试求左上角顶点到右下角顶点的所经边数值和最大的路径。例如，给出5行6列的边数值矩形如图所示：

1．动态规划设计要点 设矩阵的每点为(i, j)，i=1,2,…,n；j=1,2,…,m。 从点(i,j)水平向右的边长记为r(i,j)(j<m)，点(i,j)向下的边长记为d(i,j)(i<n)。 设a(i,j)为点（i,j）到右下顶点的最大路程。st(i,j)为点(i,j)路标数组，其值取为{‘d’,’r’}。 a(i,j)的值由a(i+1,j)+d(i,j)与a(i,j+1)+r(i,j)比较，取其较大者，即有递推关系： a(i,j)=max(a(i+1,j)+d(i,j),a(i,j+1)+r(i,j)) st(i,j)={‘d’,‘r’} 其中i=1,2,…,n−1；j=1,2,…,m−1。 注意到右边纵列与下边横行只有惟一出口，因而有边界条件： a(n,m)=0; // 初始化最右下顶点的路径值为0 a(i,m)=a(i+1,m)+d(i,m); i=n−1,n−2,…,1 a(n,j)=a(n,j+1)+r(n,j); j=m−1,m−2,…,1

2．动态规划设计要点 for(i=n−1;i>=1;i−−) {a[i][m]=a[i+1][m]+d[i][m];st[i][m]='d';} // 右纵列初始化 for(j=m−1;j>=1;j−−) {a[n][j]=a[n][j+1]+r[n][j];st[n][j]='r';} // 下横行初始化 for(i=n−1;i>=1;i−−) // 逆推求解a(i,j) if(a[i+1][j]+d[i][j]>a[i][j+1]+r[i][j]) {a[i][j]=a[i+1][j]+d[i][j];st[i][j]='d';} else {a[i][j]=a[i][j+1]+r[i][j];st[i][j]='r';} 所求左上角顶点到右下角顶点的最大路程即最优值为a(1,1)。

3．构造最优解 利用路标数组输出最优解，从起点（1,1）即i=1,j=1开始判断： if(st[i][j]=='d') {printf("−%d−",d[i][j]);i++;} else {printf("−%d−",r[i][j]);j++;} 4. 算法的复杂度分析 动态规划算法的时间复杂度为O(n^2)。

6.4 装载问题

2) 递推计算最优值 for(j=0;j<w[n];j++) m[n][j]=0; 2) 递推计算最优值 for(j=0;j<w[n];j++) m[n][j]=0; 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+1][j−w[i]]+w[i]) m[i][j]=m[i+1][j−w[i]]+w[i]; else m[i][j]=m[i+1][j]; printf("%d",m[1][c1]);

3．构造最优解 构造最优解即给出所得最优值时的装载方案。 if(m[i][cw]>m[i+1][cw]) （其中cw为当前装载量） 装载w[i]; else 不装载w[i]; if(所载集装箱重量≠m(1,c1)) 装载w[n]. 4. 算法的复杂度分析 动态规划算法的时间复杂度为O(n^2)。

6.5 0-1背包问题 6.5.1 0−1背包问题 案例提出：

1. 动态规划设计逆推求解要点

2) 逆推计算最优值 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) if(j>=w[i] && m[i+1][j]<m[i+1][j−w[i]]+p[i]) m[i][j]= m[i+1][j−w[i]]+p[i]; else 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. 动态规划设计顺推求解要点

6.6 插入乘号问题 案例提出： 在指定数字串中插入运算符号问题，包括插入若干个乘号求积的最大最小，或插入若干个加号求和的最大最小，都是比较新颖且有一定难度的最优化问题。 在一个由n个数字组成的数字串中插入r个乘号(1≤r<n)，将它分成r+1个整数，找出一种乘号的插入方法，使得这r+1个整数的乘积最大。 例如，对给定的数串847313926，如何插入5个乘号，使其乘积最大?

6.6.1 动态规划求解 1） 建立递推关系 设f(i,k)表示在前i位数中插入k个乘号所得乘积的最大值，a(i,j)表示从第i个数字到第j个数字所组成的j−i+1(i≤j)位整数值。 一般地，为了求取f(i,k)，考察数字串的前i个数字，设前j（k≤j<i）个数字中已插入k−1个乘号的基础上，在第j个数字后插入第k个乘号，显然此时的最大乘积为f(j,k−1)*a(j+1,i)。 于是可以得递推关系式： f(i,k)=max(f(j,k−1)*a(j+1,i)) （k≤j<i） 前j个数字没有插入乘号时的值显然为前j个数字组成的整数，因而得边界值： f(j,0)=a(1,j) (1≤j≤i)

2) 递推计算最优值 for(d=0,j=1;j<=n;j++) {d=d*10+b[j−1]; //在设计中可省略a数组，用变量d替代 f[j][0]=d; // 计算初始值f[j][0] } for(k=1;k<=r;k++) for(i=k+1;i<=n;i++) for(j=k;j<i;j++) {for(d=0,u=j+1;u<=i;u++) d=d*10+b[u−1]; // 计算d即为a(j+1,i) if(f[i][k]<f[j][k−1]*d) // 递推求取f[i][k] f[i][k]=f[j][k−1]*d; printf("最优值为%.0f"，f[n][r]);

3) 构造最优解 为了能打印相应的插入乘号的乘积式，设置标注位置的数组t(k)与c(i,k)，其中c(i,k)为相应的f(i,k)的第k个乘号的位置，而t(k)标明第k个乘号“*”的位置，例如，t(2)=3，表明第2个“*”号在在第3个数字后面。 当给数组元素赋值f(i,k)=f(j,k−1)*d时，作相应赋值c(i,k)=j，表明f(i,k)的第k个乘号的位置是j。在求得f(n,r)的第r个乘号位置t(r)=c(n,r)=j的基础上，其他t(k)(1≤k≤r−1)可应用下式逆推产生 t(k)=c(t(k+1),k) 根据t数组的值，可直接按字符形式打印出所求得的插入乘号的乘积式。

6.6.2 基于组合枚举求解 注意到n个数字之间共有n−1个插入乘号的位置，在这n−1个位置中组合选取r个位置t(1),t(2),…,t(r)供插入乘号。计算被这r个乘号分成的r+1个整数的积d。每计算一个d与存储最大乘积的变量max比较，若d>max，则作赋值max=d，同时乘号位置t数组赋值给s数组。 完成所有组合枚举后，得乘积最大值max，按s数组的值打印插入乘号的乘积式及其最大乘积max。

6.7 动态规划应用小结 应用动态规划设计求解最优化问题，根据问题最优解的特性，找出最优解的递推关系（递归关系），是求解的关键。至于应用递推还是递归求取最优值，递推时应用顺推还是应用逆推，可根据设计者自己的习惯与爱好来定。一般来说，应用递推求最优值比应用递归求最优值效率要高。 应用动态规划设计求解最优化问题，当最优值求出后，如何根据案例的具体实际构造最优解，是求解的难点。构造最优解，没有一般的模式可套，必须结合问题的具体实际，必要时在递推最优解时有针对性地记录若干必要的信息。 动态规划根据不同阶段之间的状态转移，通过应用递推求得问题的最优值。这里，注意不能把动态规划与递推两种算法相混淆，不要把递推当成是动态规划，也不要把动态规划当成递推。

综合动态规划与递推之间的关系： （1）动态规划是用来求解多阶段最优化问题的有效算法，而递推一般是解决某些判定性问题、构造性或计数问题的方法，两者求解对象不同。 （2）动态规划求解的多阶段决策问题必须满足最优子结构特性，而递推所求解的问题无需满足最优子结构特性。 （3）动态规划在求解最优值通常应用递推来实现，递推只是完成最优值中的一种手段。 （4）动态规划在求得问题的最优值后通常需构造出最优解，而递推在求出计数结果后没有最优解的构造需求。 （5）当动态规划与递推需设置三维数组时，其空间复杂度都比较高，这是动态规划与递推所面临的共同问题。

第6章 作业 习题6: 1, 2, 3, 4, 5, 6 第6章上机 （1） 上机通过本章最长子序列、装载与0-1背包、最优路径与插入乘号问题等多阶段决策典型案例； （2） 上机通过习题6-7,6-9 （3） 分组讨论并上机通过二维约束0-1背包问题与最优路径等案例。

欢迎大家提出教学建议 返回