动态规划例题众多详细讲解 ppt课件

16
三、备忘录方法
•备忘录方法的控制结构与直接递归方法的控制结构相同，区别
在于备忘录方法为每个解过的子问题建立了备忘录以。
m0
int lookupChain(int i, int j)
{
if (m[i][j] > 0) return m[i][j];
if (i == j) return 0;
用动态规划算法解此问题，可依据其递归式以自底向 上的方式进行计算。在计算过程中，保存已解决的子 问题答案。每个子问题只计算一次，而在后面需要时 只要简单查一下，从而避免大量的重复计算，最终得 到多项式时间的算法
13
用动态规划法求最优解
void matrixChain(int [ ] p, int[][ ] m, int [ ][ ] s)
设有四个矩阵 A,B,C，,它D们的维数分别是：
A5010B1040C4030D305
总共有五中完全加括号的方式
(A((BC)D)) (A(B(CD))) ((AB)(CD)) ((A( B)C)D) ((A(BC))D)
16000, 10500, 36000, 87500, 34500 7
矩阵连乘问题
• 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的 子序列时，称Z是序列X和Y的公共子序列。
• 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y 的最长公共子序列。
18
最长公共子序列的结构
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为 Z={z1,z2,…,zk} ，则 (1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。 (2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。 (3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。

fk
1
(sk
1 )
过程指标（阶段递推）函数:
第23页/共103页
k= 4
7
f4 (C1) = 3, f4 (C2) = 4
A1 4
B1 1
k= 3
2
6
f f
3( 3(
B B
1 2
) )
= =
m m
i i
n n
{ {
1 6
+ +
f f
4( 4(
C C
1 1
) )
= =
4 9
* ,
,
34++f 4f(4QC( C22) =)4=78*
; 的 最 优 控 制 等 问 题
第9页/共103页
§7.2 动态规划的基本概念和基本思想
一、基本概念
使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求解要求的 形式,要涉及以下概念:
(1)阶段
(2)状态
(3)决策与策略
(4)状态转移方程
(5)指标函数
(6)基本方程
第10页/共103页
(1) 划分阶段
• 离散确定型 • 离散随机型 • 连续确定型 • 连续随机型
第6页/共103页
动态规划的特点:
• 动态规划没有准确的数学表达式和定义精确的算法, 它强调具体问题具体分 析, 依赖分析者的经验和技巧。
• 与运筹学其他方法有很好的互补关系, 尤其在处理非线性、离散性问题时有 其独到的特点。
第7页/共103页
何找到的这个终点）无关；-----无后效性
• 3、逐段地求解最优路径，势必会找到一个全过程最优路径。-----
动态规划

03
动态规划算法的实现步骤
明确问题，建立数学模型
1
确定问题的目标和约束条件，将其转化为数学模 型。
2
理解问题的阶段划分，将问题分解为若干个子问 题。
3
确定状态变量和决策变量，以便描述子问题的状 态和决策。
划分阶段，确定状态变量和决策变量
01
根据问题的阶段划分，将问题分解为若干个子问题。
02
确定状态变量和决策变量，以便描述子问题的状态 和决策。
02
将子问题的最优解组合起来，得到原问题的最优解。
对最优解进行验证和性能评估，确保其满足问题的要求。
03
04
动态规划算法的优化技巧
分支定界法
分支定界法是一种求解优化问题的算 法，它通过不断生成问题的分支并确 定每个分支的界限，来寻找最优解。 在动态规划中，分支定界法可以用来 优化状态转移方程，减少计算量。
详细描述
多目标规划问题在实际生活中应用广泛，如资源分配、项目计划、城市规划等领 域都有涉及。常用的求解多目标规划的方法包括权重和法、帕累托最优解等。
多阶段决策问题
总结词
多阶段决策问题是动态规划中的一类，解决的问题需要在多个阶段做出决策，每个阶段的决策都会影响到后续阶 段的决策。
详细描述
多阶段决策问题在实际生活中应用广泛，如生产计划、库存管理、路径规划等领域都有涉及。常用的求解多阶段 决策问题的方法包括递归法、动态规划等。
特点
动态规划算法具有最优子结构、重叠 子问题和最优解性质等特征。
动态规划算法的应用领域
计算机科学
在计算机科学中，动态规划算法广泛应用于字符 串处理、排序、数据压缩和机器学习等领域。
电子工程
在电子工程中，动态规划算法用于信号处理、通 信和控制系统等领域。

问题。
ppt精选版
3
例题
• 例1、数字三角形
•
（图2－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某
处的一条路径，使该路径所经过的数字的总和最大。
• ●每一步可沿左斜线向下或右斜线向下走；
• ●1＜三角形行数≤100；
• ●三角形中的数字为整数0，1，…99；
• 输入数据：
• 由INPUT.TXT文件中首先读到的是三角形的行数。
ppt精选版
11
每一个花瓶的形状和颜色也不相同，因此，当各个花瓶 中放入不同的花束时会产生不同的美学效果，并以美 学值(一个整数)来表示，空置花瓶的美学值为0。在 上述例子中，花瓶与花束的不同搭配所具有的美学值， 可以用如下表格表示。比如杜鹃花放在花瓶2中，会 显得非常好看，但若放在花瓶4中则显得很难看。
End; {for}
ppt精选版
7
例题
• 有一个体积为V背包，现在有n个物品，他 们格子有自己的体积vi，和各自的价值wi。 现在需要选出一些物品装进背包，你的任 务是使装进物品的价值最大。
ppt精选版
8
• 状态：f[I,j](i表示处理第几个物品，j表示已 用了多大空间)
• 转移：f[I,j]=max(f[i-1,j-v[i]]+c[i],f[i-1,j]) • 边界：f[0,0]=0;
我们采用动态规划中的顺推解法。按三角形的 行划分阶段。若行数为n, 则可把问题看作一个n-1 个阶段的决策问题。从始点出发，依顺序求出第 一阶段、第二阶段，……，第n-1阶段中各决策点 至始点的最佳路径，最终求出始点到终点的最佳 路径。
ppt精选版
5
• 状态：f[I,j]表示，走到第i行第j列最大得分