当前位置:首页 >> 学科竞赛 >>

Pascal动态规划-复习


动态规划---复习篇
Dynamic Programming

登山
Zlgg想要爬天梯,他有两种登山步法:一次登上一级台阶或 两级台阶。 问:他从第一级台阶爬到第五级台阶共有多少种走法?

动态 规划

哈尔滨工程大学校ACM集训队

初识
递推公式
F(

1) = 1 F(2) = 1 F (n) = F (n-1) + F (n-2)

F(1)
动态 规划

F(2)

F(3)

F(4)

F(5)

斐波那契

哈尔滨工程大学校ACM集训队


F(5)

计 算 顺 序
F(3)

F(4)

F(3)

F(2)

F(2)

F(1)

F(2)
动态 规划

F(1)
哈尔滨工程大学校ACM集训队

隐藏的算法
F(5) 树中的算法: F(3) = F(2) + F(1) F(4) = F(3) + F(2) F(4) F(3)

F(3) = F(2) + F(1)
F(5) = F(4) + F(3)

F(3) F(2) F(2) F(1)

F(3)被重复计算了!
那么按照如下的顺序: F(3) = F(2) + F(1)

F(2)

F(1)

F(4) = F(3) + F(2)
F(5) = F(4) + F(3)
哈尔滨工程大学校ACM集训队

动态 规划

继续
从A 地到D 地要铺设一条煤气管道,其中需经过两级中 间站,两点之间的连线上的数字表示距离,如图所示。 问应该选择什么路线,使总距离最短?
3 2 A 4 B2 B1 3 C1 1 3 4

1
2 3 1 C2

D

动态 规划

C3
哈尔滨工程大学校ACM集训队

3

解法
C1 C1 2 A 4 B2

B1
1 2 3

1 3 4

3
C2 C2 D

1
C3 C3

解:整个计算过程分三个阶段,从最后一个阶段开始。 第一阶段(C →D): C 有三条路线到终点D 。
动态 规划

显然有 f1 (C1 ) = 1 ; f1(C2 ) = 3 ; f1 (C3 ) = 4
哈尔滨工程大学校ACM集训队

递推

(最短路线为B1→C1 →D)
3 3 3 1 A 2 3 4 B2 2 1 C3 C3 C2 C2 4

C1 C1

2

B1 1

1 3

D

第二阶段(B →C): B 到C 有六条路线。

f2 ( B1 ) = min
动态 规划

d( B1,C1 ) + f1 (C1 ) d( B1,C2 ) + f1 (C2 ) d( B1,C3 ) + f1 (C3 )

3+1 = min 3+3 = 4 1+4

哈尔滨工程大学校ACM集训队

结果
3
2 A 4 B2 2 B1 1 1 2 3 1 C3 C3 C2 C2 4 3 3 D C1 C1 1

最短路线为

A→B1→C1 →D

路长为 6
动态 规划
哈尔滨工程大学校ACM集训队

动态规划的重要性
● 动态规划几乎是NOIP必考内容 ● 近几年试题如下:
● ● ● ● ● ● ● ● ● ● ● [NOIP2010提高组第二题]乌龟棋(线性模型的优化) [NOIP2009普及组第四题]道路游戏(DP优化) [NOIP2008提高组第三题]传纸条(多进程DP) [NOIP2007提高组第三题]矩阵取数游戏(区间DP,高精度) [NOIP2006提高组第一题]能量项链(环形区间DP) [NOIP2006提高组第二题]金明的预算方案(依赖背包问题) [NOIP2005提高组第二题]过河(线性模型的优化) [NOIP2004提高组第三题]合唱队形(LIS问题) [NOIP2003提高组第三题]加分二叉树(区间DP) [NOIP2000提高组第二题]乘积最大(线性模型,高精度) ……

动态规划的两种实现形式

1.记忆化搜索
2.递推

记忆化搜索
● 上楼梯问题
● ● ● ● ● 有N级台阶 每次可以选择上1级或2级 上完所有楼梯有多少种方案? Mod 1000 N≤106

上楼梯问题
● 方案一:暴力搜索
● 到i级台阶,有F[i]种方案 ● 则F[i]=F[i-2]+F[i-1]

● 说明:
● 第i级台阶,可以从第i-2级台阶迈2级台阶到达,也 可以从第i-1级台阶迈1级台阶到达

上楼梯问题
● 慢在哪里?
● 重叠的问题被计算了多次! ● 例如:计算f[5]时,f[5]=f[3]+f[4];而f[4]=f[3]+f[2], 此时,f[3]又被计算了一遍。 ● 每次计算f[i]时,都要递归到f[0]或f[1]! ● 时间复杂度变成了O(N!)
● 怎么解决?

● 记忆化搜索
● 要计算f[i]时,如果发现之前已经计算过了,就不再计算,而是直接读取之前 计算的结果; ● 如果没有计算过,则计算后将结果保存在r[i]中,下次需要时,直接读取即可。

多阶段决策过程
● 多阶段决策过程( multistep decision process )是指这样一类特殊的 活动过程,过程可以按时间顺序分解成若干个相互联系的阶段,在每 一个阶段都需要做出决策,全部过程的决策是一个决策序列。 ● 动态规划(dynamic programming )算法是解决多阶段决策过程最优 化问题的一种常用方法,难度比较大,技巧性也很强。利用动态规划

算法,可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问
题。

记忆化搜索的适用范围
● 记忆化搜索几乎适用于所有DP ● 尤其适用于状态先后顺序不明显的DP

● 初学DP的同学可以先写记忆化搜索
● 会搜索就会DP~

记忆化搜索的缺点
● 记忆化搜索虽然比O(N!)的搜索快了不少 ● 但是。。。N≤106 ● 递归的话,大约需要11M的栈空间 ● 显然这是不能承受的。。。

● 把递归改为非递归形式

我们先将NOIp里的动态规划分分类:
最长不降子序列
背包 方格取数 石子归并 状态压缩 数学递推 顺序递推

动态规划专题
● 本阶段主要处理三类问题:
● 子序列问题 ● 背包问题 ● 区间问题

1.子序列问题
●最长上升子序列 ●最长公共子序列 ●最大子序和

2.背包问题
● 背包问题——一类古老而经典的动态规划模型 ● 特点:变化多端,种类繁多,但大多题型难度不大
● 基本题型:
● 01背包 ● 完全背包 ● 多重背包

● 强化题型
● ● ● ● ● 混合背包 分组背包 二维费用背包 简单的依赖背包 多人背包

● 其它
● 部分背包(贪心可解)

3.区间模型
● 区间动规的特点
● 状态为一个区间 ● 用记忆化搜索更方便

● 典型例题
● 回文词 ● 括号序列 ● 沙子合并

求解问题的两个重要性质
● 最优子结构性质:如果问题的最优解所包含的子问题的解也是最优的, 我们就称该问题具有最优子结构性质( 即满足最优化原理 )。最优 子结构性质为动态规划算法解决问题提供了重要线索。 ● 子问题重叠性质:在用递归算法自顶向下对问题进行求解时,每次产 生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规

划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一
次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算 过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的

解题效率。

动态规划与分治、递归、贪心的区别
● 递归算法在程序实现上直观容易,但因为子问题被重复计算,且程序背后存 在对栈的操作,速度(计算复杂度一般是指数级的)上劣于动态规划。在递 归的过程中,通过保存子问题的结果,可以减少计算量,同样是空间换时间 的思想,称作memoization算法。 ● 分治法要求各个子问题是独立的(即不包含公共的子问题),因此一旦递归地求 出各个子问题的解后,便可自下而上地将子问题的解合并成原问题的解。动 态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题 可包含公共的子问题),它对每个子问题只解一次,并将结果保存起来,避免 每次碰到时都要重复计算。这就是动态规划高效的一个原因。 ● 在贪婪算法中,每采用一次贪婪准则,便做出一个不可撤回的决策;而在动 态规划算法中,还要考察每个最优决策序列中是否包含一个最优决策子序列, 即问题是否具有最优子结构性质。

最短路径问题
● 图中给出了一个地图,地图中每个顶点代表一个城市,两个城市间的 连线代表道路,连线上的数值代表道路的长度。现在,想从城市A到 达城市E,怎样走路程最短,最短路程的长度是多少?

[题1] 最长不下降子序列
【问题描述】 设有整数序列b1,b2,b3,…,bm,若存在 i1<i2<i3<…<in,且bi1<bi2<bi3<…<bin, 则称 b1,b2,b3,…,bm中有长度为n的不下降 序列bi1,bi2,bi3,…,bin。求序列 b1,b2,b3,…,bm中所有长度(n)最大不下降 子序列 输入:整数序列 输出:最大长度n

[题1] 最长不下降子序列
【分析】 设F(i)为前I个数中的最大不下降序列长度。由题意不难得知,要求F(i), 需要求得F(1)—F(i-1),然后选择一个最大的F(j) ( j<i, bi>bj ),那么前I 个数中最大不下降序列便是前j个数中最大不下降序列后添加bi而得。 可见此任务满足最优子结构,可以用动态规划解决。 通过上面的分析可得状态转移方程如下: F(i)=max{F(j)+1} (j<i, bj<bi) 边界为F(1)=1 【部分代码】 f[1]:=1;len:=1; {求解最大不下降序列长度} for i:=2 to n do begin f[i]:=1; for j:=1 to i-1 do if (b[i]>b[j])and(f[i]<f[j]+1) then f[i]:=f[j]+1; if f[i]>len then len:=f[i] {记录最大值}

[题2] 数塔
● 如下图所示的数塔,从顶部出发,在每一结点可以选择向左下走或是 向右下走,一直走到底层,要求找出一条路径,使路径上的数的和最 大。数塔层数用n表示,1<=n<=100。

[题2] 数塔
贪心法。时间上有保证,但得不到最优解。主要原因是贪心法只顾 眼前利益,不考虑长远利益。 在规定时间内得到正确结果,唯一的方法就是“动态规划”。

下面以示意图表示动态规划的过程:所选路径为:9-12-10-18-10
注意分析时,有以下几个特点:
(1)将问题划分成了4个阶段;

(2)每个阶段均得到了“部分”的最优解,得到最优解时,需要进行条件判断;
(3)从最下面一层往顶层推导。

[题3] 棋盘路径问题
【题目简介】 有一个n*m的棋盘,左下角为(1,1),右上角为(n,m),如下图: 有一颗棋子,初始位置在(1,1),该棋子只能向右走或者向上走,问该 棋子从(1,1)到(n,m)一共有几条路径? 输入:两个整数n和m 输出:一个数,路径总数

[题3] 棋盘路径问题
【题目简介】 如果使用枚举的方法,必定有很多路径被重复走过,这样,势必造 成程序运行时间的浪费,当n和m的值比较大的时候,程序很可能超时。 为了避免程序的重复运行,我们可以通过记录点(1,1)到任意一个点 (I,j)的路径总数来解决这个问题。假设F[I,j]是点(1,1)到点(I,j)(1≤i≤n, 1≤j≤m)的路径总数,因为棋子在棋盘中只能向右或者向上走,所以棋盘 中只能2个点的棋子可以走到点(I,j),即点(I,j-1)和(i-1,j),这样,我们 就可以知道,F[I,j]必定是F[I,j-1]和F[i-1,j]的和,即

F[i,j]=F[i-1,j]+F[i,j-1]

【例4】街道问题
● 在下图中找出从左下角到右上角的最短路径,每步只能向右方或上 方走。

【例4】街道问题
在一般情况下,如果我们用二维数组H(i,j)和V(i,j)分别表示水平 方向和竖直方向的各路段长度,如H(1,2)表示水平方向上路口 (1,1)到 路口(1,2)的路段长度,V(1,2)表示竖值方向上路口(0,2)到路口(1,2) 的路段长度,则有公式:如

dpl(i,j)=min{dpl(i-1,j)+v(i,j),dpl(i,j-1)+h(i,j)}

[题5] 机器分配
【问题描述】 总公司拥有高效生产设备M台,准备分给下属的N个公司。各分公司

若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设
备才能使国家得到的盈利最大?求出最大盈利值。其中M≤15,N≤10。 分配原则:每个公司有权获得任意数目的设备,但总台数不得超过总设

备数M。保存数据的文件名从键盘输入。
数据文件格式为:第一行保存两个数,第一个数是设备台数M,第二 个数是分公司数N。接下来是一个M*N的矩阵,表明了第I个公司分配J台

机器的盈利。

[题5] 机器分配
【分析】 这是一个典型的动态规划试题。用机器数 来做状态,数组F[I,J]表示前I个公司分配J台 机器的最大盈利。则状态转移方程为 F[i,j]=Max{F[i-1,k] + Value[i,j-k]} (0〈=K〈=J〉

[题6] 0-1背包问题
【题目】 有N件物品和一个容量为V的背包。第i件 物品的费用是c[i],价值是w[i]。求解将哪些物 品装入背包可使价值总和最大。

[题6] 0-1背包问题
这是最基础的背包问题,特点是:每种物 品仅有一件,可以选择放或不放。 用子问题定义状态:即f[i][v]表示前i件物 品恰放入一个容量为v的背包可以获得的最大 价值。则其状态转移方程便是: f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

[题7] 完全背包问题
【题目】 有N种物品和一个容量为V的背包,每种物 品都有无限件可用。第i种物品的费用是c[i], 价值是w[i]。求解将哪些物品装入背包可使这 些物品的费用总和不超过背包容量,且价值 总和最大。

[题7] 完全背包问题
【基本思路】 这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也

就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而
是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的 思路,令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍

然可以按照每种物品不同的策略写出状态转移方程,像这样:

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]} 0<=k*c[i]<=v

[题8] 拦截导弹
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦 截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发 炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统 还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数), , 计算这套系统最多能拦截多少导弹,并依次输出被拦截的导弹飞来时候的高度。 样例:

INPUT
389 207 155 300 299 170 158 65 OUTPUT 6 (最多能拦截的导弹数)

[题8] 拦截导弹
【分析】 设 D(i) 为第 i 枚导弹被拦截之后,这套系统最多还能拦截的导弹数(包含被拦 截的第 i 枚)。我们可以设想,当系统拦截了第 k 枚导弹 x k ,而 x k 又是序列 X={x 1 ,x 2 ,…,x n } 中的最小值,即第 k 枚导弹为所有飞来的导弹中高度最低的, 则有 D(k)=1 ;当系统拦截了最后一枚导弹 xn ,那么,系统最多也只能拦截这一 枚导弹了,即 D(n)=1 ;其它情况下,也应该有 D(i)≥1 。根据以上分析,可归纳 出问题的动态规划递归方程为:

假设系统最多能拦截的导弹数为 dmax (即问题的最优值),则 dmax

( i 为被系统拦截的第一枚导弹的顺序号)

习题
1. 7万元投资到A、B、C 3个项目,其利润见下表: 如何分配投资额,使获得的利润最大。

2. 编写用动态规划法求组合数 C

m n

3. 有n个整数排成一圈,现在要从中找出连续的一段数串,使得这串数的和最大。


相关文章:
动态规划讲解大全(含例题及答案)
2.动态规划问题中的术语 阶段:把所给求解问题的过程恰当地分成若干个相互联系的...如果一个集合 P 中的元素可以通过串联(允许重复;串联,相当于 Pascal 中的 “...
动态规划练习题(含答案)
动态规划练习题 USACO 2.2 Subset Sums 题目如下: 对于从 1 到 N 的连续...如果一个集合 P 中的元素可以通过串联(允许重复;串联,相当于 Pascal 中的 “...
4种常见的动态规划模型
4种常见的动态规划模型_高三数学_数学_高中教育_教育专区。pascal,提高组信息学竞赛,动态规划模型,整理辛苦,请体谅例谈四种常见的动态规划模型动态规划是解决多阶段决...
动态规划理论(精华)
动态规划理论(精华)_IT/计算机_专业资料。动态规划理论一.动态规划的逆向思维法动态规划是一种思维方法,没有统一的、具体的模式。动态规划可以从多方面 去考察,不...
动态规划专题
关键词:pascal语言动态规划专题 1/2 相关文档推荐 动态规划专题 123页 免费 专题...及相关的优化方法 把讲稿的相关内容再复习一遍, 把讲稿的相关内容再复习一遍, ...
大计基复习重点
5.算法的方法学:贪心法、分治法、动态规划、回溯法。 第六章 1.指令分类如...4.常用的面向过程的高级语言有:BASIC 语言;C 语言;Pascal 语言;Fortran 语言;...
动态规划47题
动态规划47题_计算机软件及应用_IT/计算机_专业资料。dp动态规划练习 动态规划练习...保证总数将会适合 long long(C/C++)和 Int64(Free Pascal) 。 【输入格式】...
动态规划36讲
动态规划 极品 pascal动态规划 极品 pascal隐藏>> 一,动态规划三要素:阶段,状态,决策。 他们的概念到处都是,我就不多说了,我只说说我对他们的理解: 如果把动态...
PASCAL复习1
Pascal初赛复习 18页 2下载券 PASCAL程序复习 20页 1下载券 Pascal动态规划-复习2 29页 1下载券P​A​S​C​A​L​复​习​1 ...
动态规划部分
NOIP初赛复习 31页 5财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能...pascal动态规划pascal动态规划隐藏>> 第一章 什么叫动态规划 1.1 多阶段决策过...
更多相关标签: