中华中学动态规划讲义.ppt
《中华中学动态规划讲义.ppt》由会员分享,可在线阅读,更多相关《中华中学动态规划讲义.ppt(73页珍藏版)》请在三一文库上搜索。
1、中华中学动态规划讲义,周默,介绍,动态规划是NOIP中非常重要的一类题型。在动态规划中,算法是最难想到的,当你想到了算法,实现也就迎刃而解。今天,我们将强调算法的研究,不作上机实践,递推,递推是动态规划的根本,我们首先花一点时间进行递推训练,递推关系是一种简洁高效的常见数学模型,比如我们熟悉的Fibonacci数列问题。在这种类型的问题中,每个数据项都和它前面的若干个数据项(或后面的若干个数据项)有一定的关联,这种关联一般是通过一个“递推关系式”来表示的。求解问题时我们从初始的一个或若干个数据项出发,通过递推关系逐步推进,从而得到最终结果,这种求解问题的方法叫“递推法”。其中,初始的若干数据项
2、称为“边界”。,解决递推问题有三个重点:,一、如何建立正确的递推关系 二、递推关系有何性质 三、递推关系式如何求解,递推按照我们推导问题的方向,常分为顺推法和倒推法。,例1、有一只经过训练的蜜蜂只能爬向右侧相邻的 蜂房,不能反向爬行。试求出蜜蜂从蜂房a爬到蜂 房b的可能路线数。,问题分析:这是一道很典型的Fibonacci 数列类题目,其中的递推关系很明显。由于 “蜜蜂只能爬向右侧相邻的蜂房,不能反向爬 行”的限制,决定了蜜蜂到b点的路径只能是 从b-1点或b-2点到达的,故fn=fn-1+fn-2 (a+2=n=b),边界条件fa=1,fa+1=1。,例2、打印杨晖三角形的前10行。杨晖三角
3、形的前5行如左下图所示。,问题分析:我们观察左上图不太容易找到规律,但如果将左上图转化为右上图就不难发现杨辉三角形其实就是一个二维表(数组)的下三角部分。,假设用二维数组yh存储,每行首尾元素都为1,且其中任意一个非首尾元素yhi,j的值其实就是yhi-1,j-1与yhi-1,j的和,另外每一行的元素个数刚好等于行数。有了这些规律,给数组元素赋值就不难了,而要打印杨晖三角形,只需控制一下每行输出的起始位置即可。,例3、猴子第1天摘下若干个桃子,当即吃了一半又一个。第2天又把剩下的桃吃了一半又一个,以后每天都吃前一天剩下的桃子的一半又一个,到第10天猴子想吃时,只剩下一个桃子。 问猴子第1天一共
4、摘了多少桃子?,问题分析: 已知条件第 10 天剩下 1 个桃子,隐含条件每一次前一天的桃子个数等于后一天桃子的个数加 1 的 2 倍。 我们采取逆向思维的方法,从后往前推,可用倒推法求解。,Var S,I:LongInt; Begin S:=1;第10天只有一个桃子 For I:=9 DownTo 1 Do S:=(S+1)*2;第10天依次求前一天的桃 Writeln(S); 子数 End.,程序填空:设有一个n级的楼梯(1=n=12),编号从下到上依次为1至n,其中有若干级为坏的。有一个人上楼梯时一步可走1级、或2级、或3级(坏级只能跨过不能踏上,但级数照算)。问:这个人从楼下走到第n级
5、,共有多少种不同的走法? 例如: 当n=l时(无坏级情况下),仅有1种走法 n=2时(无坏级情况下),有:1级+l级 或 2级 共2种走法 n=3时(第二级为坏级情况下),有:1级+2级,直接3级, 共2种走法 【程序说明】用递推方法求解。用集合记录坏级。,var x,i,n,fl,f2,f3,f4:longint;s:set of 030; begin readln(n);s:= readln(x);x:坏级,以0结束 while (xO)do begin s:= readln(x); end; If (1 in s) then f1:=0 else fl:=1; If (2 in s) t
6、hen f2:=0 else f2:= If (3 in s) then f3:=0 else f3:=1+f1+f2;,if n=1 then f4:=f1 else if n=2 then f4:=f2 else if n=3 then f4:=f3 else begin for i:=4 to n do begin if(i in s)then f4:=0 else f4:= fl:=f2;f2:=f3;f3:=f4; end; end; writeln(f4);readln; end.,例4、棋盘上A点有一个过河卒,需要走到目标B点。 卒行走的规则:可以向下、或者向右。同时在棋盘 上C
7、点有一个对方的马,该马所在的点和所有跳跃 一步可达的点称为对方马的控制点。因此称之为“马 拦过河卒”。棋盘用坐标表示,A点(0, 0)、B点(n, m)(n, m为不超过15的整数),同样马的位置坐标是 需要给出的。现在要求你计算出卒从A点能够到达B 点的路径的条数,假设马的位置是固定不动的,并 不是卒走一步马走一步。 【样例】 knight.in knight.out 6 6 3 3 6,分析:本题可用搜索算法,但N,M=15就会超时。 再分析题意会发现:要到达棋盘上的一个点,只能 从左边过来或是从上面过来。根据加法原理,到达 某一点的路径数目,就等于到达其相邻的上点和左 点的路径数目之和,
8、因此我们可以使用逐列(或逐 行)递推的方法来求出从起点到终点的路径数目。 障碍点(马的控制点)也完全适用,只要将到达该 点的路径数目设置为0即可。,假设用fi,j表示到达点(i,j)的路径数目,用 gi,j表示点(i,j)是否是对方马的控制点,gi,j=0表示 不是对方马的控制点,gi,j=1表示是对方马的控制 点。则,我们可以得到如下的递推关系式:,递推边界为f0,0=1,考虑到最大情况下: n=20,m=20,路径条数可能会超出长整数范围所以要使用Comp类型或高精度运算。,fi,j=0 gx,y=1 fi,0=fi-1,0 i0,gx,y=0 f0,j=f0,j-1 j0,gx,y=0
9、fi,j=fi-1,j+fI,j-1 i0,j0,gx,y=0,例5、(NOIP普及组第四题)给定A,B,C三根足够长的细柱,在A柱上放有 2n个中间有空的圆盘,共有n个不同的尺寸,每个 尺寸都有两个相同的圆盘,注意这两个圆盘是不加 区分的(下图为n=3的情形)。现要将 这些国盘移到 C柱上,在移动过程中可放在B柱上暂存。要求: (1)每次只能移动一个圆盘; (2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序; 任务:设An为2n个圆盘完成上述任务所需的最少移动次数,对于输入的n,输出An。,【输入】 输入文件hanoi.in为一个正整数n,表示在A柱上放有2n个圆盘。 【输出】 输出文
10、件hanoi.out仅一行,包含一个正整数,为完成上述任务所需的最少移动次数An。 【输入输出样例1】 hanoi.in hanoi.out 1 2,问题分析:如果每个尺寸只有一个圆盘,共n个 圆盘,也就是常见的汉诺塔问题。则设hn为n 个盘子 从a柱移到c柱所需移动的盘次。显然,当n=1时,只 需把a 柱上的盘子直接移动到c柱就可以了,故h1=1。 当n=2时,先将a柱上面的小盘子移动到b柱上去;然 后将大盘子从a柱移到c 柱;最后,将b柱上的小盘子 移到c柱上,共记3个盘次,故h2=3。以此类推,当a 柱上有n(n=2)个盘子时,总是先借助c柱把上面的n- 1个盘子移动到b柱上,然后把a柱
11、最下面的盘子移动 到c柱上;再借助a柱把b柱上的n-1个盘子移动到c柱 上;总共移动hn-1+1+hn-1个盘次。 hn=2hn-1+1 边界条件:hn-1=1,该题若仔细观察,很容易发现是hanoi塔的变形 (只不过多了几个盘子),操作过程中,可以 将两个相同尺寸的盘子看成一个整体,这样就 成了典型的hanoi塔问题。再运用公式: fn=2n-1来做,最后只要乘2就行了。由于数据 较大,须用到高精度运算。,题型大类,简单线性dp 背包 最长XX子序列 最长公共子序列LCS 区间dp 树dp 坐标dp 。,1.数塔,7 3 8 8 1 0 2 7 7 4 5 5 2 6 5 如图,有一数字三角
12、形。数字三角形中的数字为不超过100的正整数。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层,每一步可沿左斜线向下或右斜线向下走。假设三角形行数100,编程求解从最顶层走到最底层的一条路径,使得沿着该路径所经过的数字的总和最大,输出最大值。 此数塔输出为30,是否可以用前两次课所用的深搜呢。显然前两次课的深搜写数塔这道题的时候程序简明易懂。但是当行数很大时,当三角形的行数等于100时,其枚举量之大是可想而知的,用枚举法肯定超时,甚至根本不能得到计算结果,必须用动态规划法来解。 const maxn=10; var a:array1maxn,1maxn of integer;
13、 max:longint;n,i,j:integer; procedure try(x,y,dep:integer;sum:longint); begin if (dep=n) then begin if summax then max:=sum; exit end; try(x+1,y,dep+1,sum+ax+1,y); try(x+1,y+1,dep+1,sum+ax+1,y+1);end; begin readln(n); for i:=1 to n do for j:= 1 to i do read(ai,j); max:=0; try(1,1,1,a1,1); writeln(ma
14、x); end.,那我们又该如何实现动态 规划呢?,1.逆推法: 按三角形的行划分阶段,若行数为 n,则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和,再依次求出第n-2阶段、第n-3阶段第1阶段(起始点)各决策点至第n行的最佳路径。设:fi,j为从第i阶段中的点j至第n行的最大的数字和;则: fn,j=an,j 1=j=n fi,j=maxai,j+fi+1,j,ai,j+fi+1,j+1 1=j=i. f1,1即为所求。,const maxn=100; var n,i,j:integer; a:array1maxn,1maxn of int
15、eger; f:array1maxn,1maxn of integer; begin readln(n); for i:=1 to n do for j:=1 to i do read(ai,j); for i:=1 to n do fn,i:=an,i; for i:=n-1 downto 1 do for j:=1 to i do if fi+1,jfi+1,j+1 then fi,j:=ai,j+fi+1,j else fi,j:=ai,j+fi+1,j+1; writeln(f1,1); end.,2. 顺推法 按三角形的行划分阶段,若行数为 n,则可把问题看做一个n-1个阶段的决策问
16、题。先求第2行各元素到起点的最大和 ,再依次求出第3,4,5,.n-1,n到起点的最大和,最后找第n行的最大值 设fi,j为 第i行第j列上点到起点的最大和 则 f1,1=a1,1; fi,1=ai, 1+fi-1,1; f i,j =max ai,j+fi-1,j-1,ai,j+fi-1,j 2=j=i max(fn,1,fn,2,.,fn,n即为所求。,const maxn=100; var n,i,j:integer; a:array1maxn,1maxn of integer; f:array1maxn,1maxn of integer; maxsum:integer; begin r
17、eadln(n); for i:=1 to n do for j:=1 to i do read(ai,j); fillchar(f,sizeof(f),0); f1,1:=a1,1; for i:=2 to n do begin fi,1:=ai,1+fi-1,1; for j:=2 to i do if fi-1,j-1fi-1,j then fi,j:=ai,j+fi-1,j-1 else fi,j:=ai,j+fi-1,j; end; maxsum:=0; for i:=1 to n do if fn,imaxsum then maxsum:=fn,i; writeln(maxsum)
18、; end.,2.最长不下降子序列,设有由n个不相同的整数组成的数列,记为:a(1)、a(2)、a(n)例如3,18,7,14,10,12,23,41,16,24。若存在i1i2i3 ie 且有a(i1)a(i2) a(ie)则称为长度为e的不下降序列。如上例中3,18,23,24就是一个长度为4的不下降序列,同时也有3,7,10,12,16,24长度为6的不下降序列。程序要求,当原数列给出之后,求出最长的不下降序列。,const maxn=100; var a,b,c:array1maxn of integer; n,i,j,max,p:integer; begin readln(n); f
19、or i:=1 to n do begin read(ai); bn:=1; cn:=0; end; for i:= n-1 downto 1 do begin max:=0;p:=0; for j:=i+1 to n do if (aimax) then begin max:=bj;p:=j end; if p0 then begin bi:=bp+1;ci:=p end end; max:=0;p:=0; for i:=1 to n do if bimax then begin max:=bi;p:=i end; writeln(maxlong=,max); while p0 do beg
20、in write(ap:5);p:=cp end; end.,谁能够说出刚刚做法的时间复杂度? n2 有没有速度更快的做法呢 有!下面介绍nlogn的算法,var n,i,ans,j,k,m:longint; a,b:array110000 of longint; begin read(n); for i := 1 to n do read(ai); ans:=0; for i := 1 to n do begin j:=1;k:=ans; while j ans then inc(ans); bj:=ai; end; writeln(ans); end.,同样的道理我们也可以做最长不上升子序
21、列等等最长XX子序列,3.背包问题,1.部分背包问题 一个旅行者有一个最多能用m公斤的背包,现在有n种物品,它们的总重量分别是W1,W2,.,Wn,它们的总价值分别为C1,C2,.,Cn.求旅行者能获得最大总价值。 解决问题的方法是贪心算法:将C1/W1,C2/W2,.Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止.,2.0/1背包 一个旅行者有一个最多能用m公斤的背包,现在有n件物品,它们的重量分别是W1,W2,.,Wn,它们的价值分别为C1,C2,.,Cn.若每种物品只有一件求旅行者能获得最大总价值。 分析说明: 显然这个题可用深度优先方法对每件物品进行枚举(选
22、或不选用0,1控制). 程序简单,但是当n的值很大的时候不能满足时间要求,时间复杂度为O(2n)。按递归的思想我们可以把问题分解为子问题,使用递归函数 设 f(i,x)表示前i件物品,总重量不超过x的最优价值 则 f(i,x)=max(f(i1,x-Wi)+Ci,f(i1,x) f(n,m)即为最优解,边界条件为f(0,x)0 ,f(i,0)=0;,const maxm=200;maxn=30; type ar=array1maxn of integer; var m,n,j,i:integer; c,w:ar; f:array0maxn,0maxm of integer; function
23、max(x,y:integer):integer; begin if xy then max:=x else max:=y; end; begin readln(m,n); for i:= 1 to n do readln(wi,ci); for i:=1 to m do f(0,i):=0; for i:=1 to n do f(i,0):=0; for i:=1 to n do for j:=1 to m do begin if j=wi then fi,j:=max(fi-1,j-wi+ci,fi-1,j) else fi,j:=fi-1,j; end; writeln(fn,m); e
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中华 中学 动态 规划 讲义
链接地址:https://www.31doc.com/p-3420585.html