文档介绍：动态规划
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。
(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。
动态规划程序设计往往是针对一种最优化问题,由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法,而不存在一种万能的动态规划算法,可以解决各类最优化问题。
因此在学****时,除了要对基本概念和方法正确理解外,必须具体问题具体分析处理,以丰富的想象力去建立模型,用创造性的技巧去求解。
我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论,逐渐学会并掌握这一设计方法。
适用条件
任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
(最优子结构性质) 最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。
。其中的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。
动态规划的基本模型
多阶段决策过程的最优化问题
某些问题,可以将其解决的过程,分成若干个互相联系的阶段,在每一阶段都需要做出决策(选择),从而使整个过程达到最好的效果
各个阶段的决策的选取,即依赖于当前状态,又影响以后的发展
当各个阶段决策确定后,就组成了一个决策序列,这也就是解决问题的一条路线
这种可以看作一个前后关联的多阶段过程的问题,就称为多阶段决策问题
决策1
决策2
决策n
状态0
状态1
状态2
状态n
……
……
阶段1
阶段2
阶段n
动态规划关键词
阶段
状态
边界
转移
决策
例题数塔问题(IOI94)
有如图所示的数塔,从顶部出发,在每一结点可以选择向左下走或向右下走,一直走到底层,要求找出一条路径,使路径上的值最大
13
11
8
12
7
26
6
14
15
8
12
7
13
24
11
例题数塔问题
从上到下分析,逐层求值
阶段:按层分阶段
状态:f[i][j] 走到第i层第j个结点的最大值
边界:f[1][1]=a[1][1]
决策:对每个结点,取到达它的最大路径值
转移:f[i][j]=max{f[i-1][j-1],f[i-1][j]}+a[i][j]
13
11
8
12
7
26
6
14
15
8
12
7
13
24
11
阶段1
阶段2
阶段3
阶段4
f(1,1)=13
f(2,1)=24
f(3,1)=36
f(4,1)=42
f(5,1)=54
f(2,2)=21
f(3,2)=31
f(4,2)=50
f(5,2)=57
f(3,3)=47
f(4,3)=62
f(5,3)=75
f(4,4)=55
f(5,4)=86
f(5,5)=66
背包问题——01背包
有N件物品和一个容量为maxv的背包。第i件物品的体积是V[i],价值是C[i]。求解将物品装入背包的最大总价值
这是最基础的背包问题:每种物品仅有一件,可以选择放或不放
背包问题——01背包
物品N
容量maxv
体积V[i]
价值C[i]
状态
f[i][j],前i个物品装入j体积的最大价值
转移
放入物品i,总价值=前i-1个物品装入j-v[i]体积的总价值+C[i];
不放入物品i,总价值=前i-1个物品装入j体积的总价值
f[i][j]=max{f[i-1][j-v[