动态规划朱全民.ppt
《动态规划朱全民.ppt》由会员分享,可在线阅读,更多相关《动态规划朱全民.ppt(60页珍藏版)》请在三一文库上搜索。
1、动态规划,参与竞赛的同学应由竞争关系和独立关系(你做你的,我干我的,程序和算法互相保密,彼此津津乐道于对方的失败和自己的成功)转向合作学习的关系(通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务),2,斐波纳契数列F(n),3,递归 vs 动态规划,递归版本: F(n) 1 if n=0 or n=1 then 2 return 1 3 else 4 return F(n-1) + F(n-2),动态规划: F(n) 1 A0 = A1 1 2 for i 2 to n do 3 Ai Ai-1 + Ai-2 4 return An,太慢!,有效率! 算法复杂度是 O(n),4,方
2、法概要,构造一个公式,它表示一个问题的解是与它的子问题的 解相关的公式. E.g. F(n) = F(n-1) + F(n-2). 为这些子问题做索引 ,以便它们能够在表中更好的存储与检索 (i.e., 数组array【】) 以自底向上的方法来填写这表格; 首先填写最小子问题的解. 这就保证了当我们解决一个特殊的子问题时, 可以利用比它更小的所有可利用的 子问题的解.,由于历史原因, 我们称这种方法为: 动态规划. 在上世纪40年代末 (计算机普及很少时), 这些规划设计是与”列表“方法相关的.,5,动态规划算法,算法思想 将待求解的问题分解成若干个子问题,并存储子问题的解而避免计算重复的子问
3、题,并由子问题的解得到原问题的解。 动态规划算法通常用于求解具有某种最优性质的问题。 动态规划算法的基本要素: 最优子结构性质和重叠子问题。,原理,6,最优子结构性质:问题的最优解包含着它的子问题的最优解。即不管前面的策略如何,此后的决策必须是基于当前状态(由上一次决策产生)的最优决策。 重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些问题被反复计算多次。对每个子问题只解一次,然后将其解保存起来,以后再遇到同样的问题时就可以直接引用,不必重新求解。,原理,7,动态规划,解决问题的基本特征,1. 动态规划一般解决最值(最优,最大,最小,最长)问题;,2. 动态规划解
4、决的问题一般是离散的,可以分解(划分阶段)的;,3. 动态规划解决的问题必须包含最优子结构,即可以由(n1)的最优推导出n的最优,原理,8,动态规划算法的4个步骤: 1. 刻画最优解的结构特性. (一维,二维,三维数组) 2. 递归的定义最优解. (状态转移方程) 3. 以自底向上的方法来计算最优解. 4. 从计算得到的解来构造一个最优解.,解决问题的基本步骤,原理,9,实例,例题一. 斐波纳契数列F(n),步骤1:用F(n)表示在斐波纳契数列中第n个数的值;,步骤2:状态转移方程:,步骤3:以自底向上的方法来计算最优解,步骤4:在数组中分析构造出问题的解;,10,例题二. 输入n,求出n!,
5、步骤1:用F(n)表示n!的值;,步骤2:状态转移方程:,步骤3:以自底向上的方法来计算最优解,实例,11,例题三:排队买票问题,一场演唱会即将举行。现有n个歌迷排队买票,一个人买一张,而售票处规定,一个人每次最多只能买两张票。假设第i位歌迷买一张票需要时间Ti(1in),队伍中相邻的两位歌迷(第j个人和第j+1个人)也可以由其中一个人买两张票,而另一位就可以不用排队了,则这两位歌迷买两张票的时间变为Rj,假如RjTj+Tj+1,这样做就可以缩短后面歌迷等待的时间,加快整个售票的进程。现给出n, Tj和Rj,求使每个人都买到票的最短时间和方法。,实例,12,1,2,3,4,5,i,i,步骤1:
6、用F(i)表示前i个人买票的最优方式,即所需最短时间;现在要决定F(i)需要考虑两种情况: (1)第i个人的票自己买 (2)第i个人的票由第i-1个人买,步骤2:状态转移方程:,min,步骤3:以自底向上的方法来计算最优解,13,程序的实现,BuyTicks(T, R) 1 n lengthT 2 f0 0 3 f1 T1 4 for i 2 to n do 5 fi fi-2+Ri-1 6 if fi fi-1+Ti then 7 fi fi-1+Ti 8 return f,14,实例,例题四:求最长不降子序列,1问题描述 设有一个正整数的序列:b1,b2,,bn,对于下标i1i2im,若有
7、bi1bi2bim 则称存在一个长度为m的不下降序列。 例如,下列数列 13 7 9 16 38 24 37 18 44 19 21 22 63 15 对于下标i1=1,i2=4,i3=5,i4=9,i5=13,满足1316384463,则存在长度为5的不下降序列。 但是,我们看到还存在其他的不下降序列: i1=2,i2=3,i3=4,i4=8,i510,i6=11,i7=12,i8=13,满足:79161819212263,则存在长度为8的不下降序列。 问题为:当b1,b2,,bn给出之后,求出最长的不下降序列。,步骤1:用F(i)表示第i项到最后一项最长不下降序列的长度的值;,步骤2:状态
8、转移方程;,di表示数列中第i项的值;,步骤3:以自底向上的方法来计算最优解,15,拓展1: 拦截导弹 (vijos1303),某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 样例: INPUT OUTPUT 389 2
9、07 155 300 299 170 158 65 6(最多能拦截的导弹数) 2(要拦截所有导弹最少要配备的系统数),16,拓展2:低价购买,“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者,你必须遵循以下的问题建议:“低价购买;再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下,求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(216范围内的正整数),你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买;再低价购买”的原则。写一个程序计算最大购买次数。 这里是某支
10、股票的价格清单: 日期 1 2 3 4 5 6 7 8 9 10 11 12 价格 68 69 54 64 68 64 70 67 78 62 98 87 最优秀的投资者可以购买最多4次股票,可行方案中的一种是: 日期 2 5 6 10 价格 69 68 64 62 输入 第1行: N (1 = N = 5000),股票发行天数 第2行: N个数,是每天的股票价格。 输出 输出文件仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(=231)当二种方案“看起来一样”时(就是说它们构成的价格队列一样的时候),这2种方案被认为是相同的。,17,拓展3:合唱队形 (vijis1098),N位同
11、学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2,K,他们的身高分别为T1,T2,TK, 则他们的身高满足T1Ti+1TK(1=i=K)。 你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。,输入的第一行是一个整数N(2=N=100),表示同学的总数。第一行有n个整数,用空格分隔,第i个整数Ti(130=Ti=230)是第i位同学的身高(厘米)。,输出包括一行,这一行只包含一个整数,就是最少需要几位同学出列。,样例输入 8 186 186 150 20
12、0 160 130 197 220,样例输出: 4,18,例题五. 马拦过河卒,实例,问题描述: 如图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如上图的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点(图中的P1,P2 P8 和 C)。卒不能通过对方马的控制点。,棋盘用坐标表示,A 点(0,0)、B 点(n,m)(n,m 为不超过 20 的整数,并由键盘输入),同样马的位置坐标是需要给出的(约定: CA,同时CB)。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数
13、。 输入: 键盘输入 B点的坐标(n,m)以及对方马的坐标(X,Y)不用盘错 输出: 屏幕输出 一个整数(路径的条数)。 输入输出样例: 输入: 6 6 3 2 输出: 17,19,步骤1:用F(X,Y)表示到棋盘上每个阶段(X,Y)的路径条数;,步骤2:状态转移方程:,步骤3:以自底向上的方法来计算最优解,分析:阶段:棋盘上的每个可走的点; 每个阶段的求解;,F(X,Y)= F (X-1,Y)+ F(X, Y-1) 其中,F(0,0 )=1 F (0,Y)=1 F (X,0)=1,20,例题六:数字三角形问题,1问题描述 设有一个三角形的数塔,顶点结点称为根结点,每个结点有一个整数数值。从顶
14、点出发,可以向左走,也可以向右走。如图10一1所示。,问题:当三角形数塔给出之后,找出一条从第一层到达底层的路径,使路径的值最大。若这样的路径存在多条,任意给出一条即可。,21,步骤1,二维数组 D(X,y)描述问题,D(X,y)表示从顶层到达第X层第y个位置的最小路径得分。,步骤2:状态转移方程,阶段分析:D(1,1)=13 到第x层的第y个位置有两种可能,要么走右分支 得到,要么走左分支得到。,D(X,y)minD(X-1,y),D(X-1,y-1+a(X,y) D(1,1)a(1,1),22,拓展:栈(vijos 1122),【问题背景】栈是计算机中经典的数据结构,简单的说,栈就是限制在
15、一端进行插入删除操作的线性表。 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈)。,宁宁考虑的是这样一个问题:一个操作数序列,从1,2,一直到n(图示为1到3的情况),栈A的深度大于n。 现在可以进行两种操作, 1.将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的push操作) 2. 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的pop操作),23,使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由1 2 3生成序列2 3 1的过程。(原始状态如上图所示),24,你的程序将对给定的n,计算并输出由操作数序列1,2,n经过
16、操作可能得到的输出序列的总数。 【输入格式】 输入文件只含一个整数n(1n18) 【输出格式】 输出文件只有一行,即可能输出序列的总数目 【输入样例】 3 【输出样例】 5,25,例题七:最长公共子序列,一个给定序列的子序列是在该序列中删去若干元素后得到的序列。 给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。 最长公共子序列:公共子序列中长度最长的子序列。 最长公共子序列问题 给定两个序列X=x1,x2,xm和Y=y1,y2, yn,找出X和Y的一个最长公共子序列。 例如: X = (A, B, C, B, D, A, B) X的子序列: 所有X
17、的子集(集合中元素按原来在X中的顺序排列) (A, B, D), (B, C, D, B), 等等.,26,例子,X = (A, B, C, B, D, A, B) X = (A, B, C, B, D, A, B) Y = (B, D, C, A, B, A) Y = (B, D, C, A, B, A) (B, C, B, A)和(B, D, A, B)都是X和Y 的最长公共子序列(长度为4) 但是,(B, C, A)就不是X和Y的最长公共子序列,27,穷举法,对于每一个Xm的子序列,验证它是否是Yn的子序列. Xm有2m个子序列 每个子序列需要o(n)的时间来验证它是否是Yn的子序列.
18、从Yn的第一个字母开始扫描下去,如果不是则从第二个开始 运行时间: o(n2m),28,给定一个序列Xm = (x1, x2, , xm),我们定义Xm的第i个前缀为: Xi = ( x1, x2, , xi ) i = 0, 1, 2, , m ci, j为序列Xi = (x1, x2, , xi)和Yj = (y1, y2, , yj)的最长公共子序列的长度.,分析:,最优子结构性质: 设序列Xm=x1,x2,xm和Yn=y1,y2,yn的一个最长公共子序列为Zk=z1,z2,zk,则 1.若xm=yn,则zk=xm=yn,且Zk-1是Xm-1和Yn-1的最长公共子序列。 2.若xmyn,
19、且zkxm,则Zk是Xm-1和Yn的最长公共子序列。 3.若xmyn,且zk yn ,则Zk是Xm和Yn-1的最长公共子序列。,步骤1,步骤2,29,状态转移方程,yj:,xm,y1,y2,yn,x1,x2,xi,i,0,1,2,n,m,1,2,0,步骤3,30,附加信息,yj:,D,A,C,F,A,B,xi,j,i,0,1,2,n,m,1,2,0,矩阵 bi, j: 它告诉我们要获得最优结果应该如何选择 如果 xi = yj bi, j = 1 如果 ci - 1, j ci, j-1 bi, j = 2 否则 bi, j = 3,3,3,C,D,31,LCS-LENGTH(X, Y, m,
20、 n) 1 for i 1 to m do ci, 0 0 2 for j 0 to n do c0, j 0 3 for i 1 to m do 4 for j 1 to n do 5 if xi = yj 6 then ci, j ci - 1, j - 1 + 1 7 bi, j “” 8 else if ci - 1, j ci, j - 1 9 then ci, j ci - 1, j 10 bi, j “” 11 else ci, j ci, j - 1 12 bi, j “” 13 return c and b,运行时间: (nm),32,例子,X = (B, D, C, A,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 全民
链接地址:https://www.31doc.com/p-2519901.html