《《动态规划初步》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《动态规划初步》PPT课件.ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、动态规划初步动态规划初步 JSOI2007夏令营夏令营B层次（泰州）层次（泰州）问题：城市交通问题：城市交通 有有n n个城市，编号个城市，编号1n1n，有些城市之间有路相连，有些则没，有些城市之间有路相连，有些则没有，有路则当然有一个距离。现在规定只能从编号小的城市走有，有路则当然有一个距离。现在规定只能从编号小的城市走到编号大的城市，问你从编号为到编号大的城市，问你从编号为1 1的城市走到编号为的城市走到编号为n n的城市要的城市要花费的最短距离是多少？花费的最短距离是多少？输入格式：输入格式：先输入一个先输入一个n n，表示城市数，表示城市数，n100n100。下面的下面的n n行，是一
2、个行，是一个n*nn*n的邻接矩阵的邻接矩阵map1.n,1.nmap1.n,1.n。mapi,j=0 mapi,j=0，表示城市，表示城市i i和城市和城市j j之间没有路相连，否则为之间没有路相连，否则为两者之间的距离。两者之间的距离。输出格式：输出格式：一个数，表示从城市一个数，表示从城市1 1走到城市走到城市n n的最短距离。的最短距离。输入数据保证可以从城市输入数据保证可以从城市1 1走到城市走到城市n n。动态规划的引入动态规划的引入输入样例：输入样例：110 5 3 0 0 0 0 0 0 0 05 0 0 1 6 3 0 0 0 0 03 0 0 0 8 0 4 0 0 0 0
3、0 1 0 0 0 0 0 5 6 0 00 6 8 0 0 0 0 5 0 0 00 3 0 0 0 0 0 0 0 8 00 0 4 0 0 0 0 0 0 3 00 0 0 5 5 0 0 0 0 0 30 0 0 6 0 0 0 0 0 0 40 0 0 0 0 8 3 0 0 0 30 0 0 0 0 0 0 3 4 3 0动态规划的引入动态规划的引入 设一个数组设一个数组dis1.n，disi表示城市表示城市1到城市到城市i的最短距离。的最短距离。题目就是要求题目就是要求disn。根据题目的限制条件：只能从编号小的城市到编号大的城市。根据题目的限制条件：只能从编号小的城市到编号大的
4、城市。显然，我们可以从城市显然，我们可以从城市1、城市、城市2、城市、城市n-1到城市到城市n，前提，前提是城市是城市i与城市与城市n之间有路，其中之间有路，其中i=1，2，3，n-1。所以，所以，disn就应该取就应该取disi+mapi，n中的中的最小值最小值，且要，且要求求mapi，n0，i=1，2，3，n-1。也就是说要求也就是说要求disn，就必须先求出，就必须先求出dis1disn-1，类，类似于递推算法中的似于递推算法中的“倒推法倒推法”，那么如何求，那么如何求disn-1呢？呢？disn-1=min disi+mapi，n-1 且要求且要求mapi，n-10，in-1。城市交通
5、分析城市交通分析现在我们把问题一般化，如何求现在我们把问题一般化，如何求disi呢？其中，呢？其中，i=1.n。Disi=min disj+mapj，i要满足：要满足：mapj，i0，j=1.i-1 这是一个类似于递归的公式，意思为：要求这是一个类似于递归的公式，意思为：要求disn就要先求就要先求disn-1 dis1，要求，要求disn-1就要先求就要先求disn-2 dis1，而要求而要求disi，就要先求，就要先求disi-1 dis1，而，而dis1=0。在具体计算的时候，只要从在具体计算的时候，只要从dis1开始开始“顺推顺推”下去，依次求出下去，依次求出dis2、dis3、dis
6、n-1、disn即可。即可。城市交通分析城市交通分析dis1:=0;for i:=2 to n dobegin min:=maxint;用打擂台的方法求出最小值用打擂台的方法求出最小值 for j:=1 to i-1 do if mapj,i0 then if disj+mapj,i1，j=1.i-1，且，且hj=hi第一问的答案就是第一问的答案就是a1a8中的最大值。中的最大值。“拦截导弹拦截导弹”问题分析问题分析 longest1:=1;for i:=2 to n do 分阶段求出每步的最优值分阶段求出每步的最优值 begin maxlong:=1;for j:=1 to i-1 do i
7、f himaxlong then maxlong:=longestj+1;longesti:=maxlong end;maxlong:=longest1;以下打擂台求出最大值以下打擂台求出最大值 for i:=2 to n do if longestimaxlong then maxlong:=longesti;writeln(max=,maxlong);这种解题方法就称为这种解题方法就称为“动态规划动态规划”“拦截导弹拦截导弹”问题分析问题分析“拦截导弹拦截导弹”问题分析问题分析关于第二问：关于第二问：由于它紧接着第一问，所以很容易受前面的影响，多次采用由于它紧接着第一问，所以很容易受前面的
8、影响，多次采用第一问的办法，然后得出总次数，其实这是不对的。要举反例并第一问的办法，然后得出总次数，其实这是不对的。要举反例并不难，比如长为不难，比如长为7的高度序列的高度序列“7 5 4 1 6 3 2”，最长不上升序列最长不上升序列为为“7 5 4 3 2”，用多次求最长不上升序列的结果为，用多次求最长不上升序列的结果为3套系统；但套系统；但其实只要其实只要2套，分别击落套，分别击落“7 5 4 1”与与“6 3 2”。所以不能用多次。所以不能用多次“动态规划动态规划”的方法做，那么，正确的做法又是什么呢？的方法做，那么，正确的做法又是什么呢？我们的目标是用最少的系统击落所有导弹，至于系统
9、之间我们的目标是用最少的系统击落所有导弹，至于系统之间怎么分配导弹数目则无关紧要，上面错误的想法正是承袭了怎么分配导弹数目则无关紧要，上面错误的想法正是承袭了“一套系统尽量多拦截导弹一套系统尽量多拦截导弹”的思维定势，忽视了最优解中各个的思维定势，忽视了最优解中各个系统拦截数较为平均的情况，本质上是一种系统拦截数较为平均的情况，本质上是一种贪心算法贪心算法，但贪心，但贪心的策略不对。如果从每套系统拦截的导弹方面来想行不通的话，的策略不对。如果从每套系统拦截的导弹方面来想行不通的话，我们就应该换一个思路，我们就应该换一个思路，从拦截某个导弹所选的系统入手从拦截某个导弹所选的系统入手。“拦截导弹拦
10、截导弹”问题分析问题分析 题目告诉我们，已有系统目前的瞄准高度必须不低于来犯导题目告诉我们，已有系统目前的瞄准高度必须不低于来犯导弹高度，所以，当已有的系统均无法拦截该导弹时，就不得不弹高度，所以，当已有的系统均无法拦截该导弹时，就不得不启启用新系统用新系统。如果已有系统中有一个能拦截该导弹，我们是应该继。如果已有系统中有一个能拦截该导弹，我们是应该继续使用它，还是另起炉灶呢？事实是：无论用哪套系统，只要拦续使用它，还是另起炉灶呢？事实是：无论用哪套系统，只要拦截了这枚导弹，那么系统的瞄准高度就等于导弹高度，这一点对截了这枚导弹，那么系统的瞄准高度就等于导弹高度，这一点对旧的或新的系统都适用。
11、而新系统能拦截的导弹高度最高，即新旧的或新的系统都适用。而新系统能拦截的导弹高度最高，即新系统的性能优于任意一套已使用的系统。既然如此，我们当然应系统的性能优于任意一套已使用的系统。既然如此，我们当然应该选择已有的系统。该选择已有的系统。如果已有系统中有多个可以拦截该导弹，究如果已有系统中有多个可以拦截该导弹，究竟选哪一个呢？竟选哪一个呢？当前瞄准高度较高的系统的当前瞄准高度较高的系统的“潜力潜力”较大，而瞄较大，而瞄准高度较低的系统则不同，它能打下的导弹别的系统也能打下，准高度较低的系统则不同，它能打下的导弹别的系统也能打下，它够不到的导弹却未必是别的系统所够不到的。所以，当有多个它够不到的
12、导弹却未必是别的系统所够不到的。所以，当有多个系统供选择时，要选瞄准高度最低的使用，当然瞄准高度同时也系统供选择时，要选瞄准高度最低的使用，当然瞄准高度同时也要大于等于来犯导弹高度。要大于等于来犯导弹高度。“拦截导弹拦截导弹”问题分析问题分析 解题时用一个数组解题时用一个数组sys记下当前已有系统的各个当前瞄准记下当前已有系统的各个当前瞄准高度，该数组中实际元素的个数就是第二问的解答。高度，该数组中实际元素的个数就是第二问的解答。sys1:=h1;tail:=1;for i:=2 to n dobegin minheight:=maxint;for j:=1 to tail do 找一套最适合
13、的系统找一套最适合的系统 if sysjhi then if sysjminheight then begin minheight:=sysj;select:=j end;if minheight=maxint 开一套新系统开一套新系统 then begin tail:=tail+1;systail:=hi end else sysselect:=hiend;writeln(total=,tail);动态规划简介动态规划简介 数字三角形（数字三角形（IOI1994IOI1994）问题描述问题描述 如下所示为一个数字三角形：如下所示为一个数字三角形：73 88 1 02 7 4 44 5 2 6
14、 5 请编一个程序计算从顶至底的某处的一条路径，使该路径所请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。规定：经过的数字的总和最大。规定：每一步可沿直线向下或右斜线向下走；每一步可沿直线向下或右斜线向下走；1三角形行数三角形行数100；三角形中的数字为整数三角形中的数字为整数0，1，99；样例输出：样例输出：30动态规划简介动态规划简介 分析分析数字三角形数字三角形1、穷举法：最多、穷举法：最多100行，有行，有299条路径，超时；条路径，超时；2、贪心法：不正确；、贪心法：不正确；3、动态规划：、动态规划：假设从顶至数字三角形的某一位置的所有路径中，所经过假设从顶
15、至数字三角形的某一位置的所有路径中，所经过的数字的总和最大的那条路径，我们称之为的数字的总和最大的那条路径，我们称之为该位置的最大路径该位置的最大路径。由于问题规定每一步只能沿直线向下或沿斜线向右下走，若要由于问题规定每一步只能沿直线向下或沿斜线向右下走，若要走到该位置，则其前一位置必为其左上方或正上方两个位置之走到该位置，则其前一位置必为其左上方或正上方两个位置之一，由此可知，一，由此可知，当前位置的最优路径必定与其左上方或正上方当前位置的最优路径必定与其左上方或正上方两个位置的最优路径有关两个位置的最优路径有关，且来自于其中更优的一个。，且来自于其中更优的一个。动态规划简介动态规划简介 设
16、设ai，j表示数字三角形中第表示数字三角形中第i行第行第j列的数，再设一个二维列的数，再设一个二维数组数组sum记录每个位置的最优路径的数字总和，则：记录每个位置的最优路径的数字总和，则：sumi，j=maxsumi-1，j，sumi-1，j-1+ai，j 其中：其中：2=i=n，2=jsumi-1,j then sumi,j:=sumi-1,j-1+ai,j else sumi,j:=sumi-1,j+ai,j;ans:=0;打擂台求最优值打擂台求最优值for j:=1 to n do if sumn,jans then ans:=sumn,j;writeln(ans);Var sum:ar
17、ray1.maxn,0.maxn of longint;思考题思考题 假如本题还要你输出最大值的那条路径，即不仅要求出最假如本题还要你输出最大值的那条路径，即不仅要求出最优值、还要你构造出最优方案，你怎么办呢？优值、还要你构造出最优方案，你怎么办呢？用用1个三维数组个三维数组 sum1.maxn,0.maxn,1.2来记忆最优来记忆最优值及最优值的来源，在递推的同时记下路径，即：值及最优值的来源，在递推的同时记下路径，即：sumx,y,1表示第表示第x行、行、y列能够取得的最大值，列能够取得的最大值，sumx,y,2表示该最大值表示该最大值是从上一行的哪个位置得来的（如是从上一行的哪个位置得来
18、的（如-1表示从左上方得到的，表示从左上方得到的，0表表示从正上方得到的）。最后输出时，从下往上倒过来推即可！示从正上方得到的）。最后输出时，从下往上倒过来推即可！动态规划简介动态规划简介 动态规划的基本概念动态规划的基本概念 1、阶段、阶段 用动态规划求解一个问题时，需要将问题的全过程恰当地划用动态规划求解一个问题时，需要将问题的全过程恰当地划分成若干个相互联系的阶段，以便按一定的次序去求解。阶段的分成若干个相互联系的阶段，以便按一定的次序去求解。阶段的划分一般是根据时间和空间的自然特征来定的，一般要便于把问划分一般是根据时间和空间的自然特征来定的，一般要便于把问题转化成多阶段决策的过程。题
19、转化成多阶段决策的过程。2、状态、状态 状态表示的是事物某一阶段的性质，状态通过一个变量来描状态表示的是事物某一阶段的性质，状态通过一个变量来描述，这个变量称为状态变量。各个状态之间是可以相互转换的。述，这个变量称为状态变量。各个状态之间是可以相互转换的。3、决策、决策 对问题的处理中做出某种选择性的行动就是决策。一个实际对问题的处理中做出某种选择性的行动就是决策。一个实际问题可能要有多次决策，在每一个阶段中都需要有一次决策。问题可能要有多次决策，在每一个阶段中都需要有一次决策。一次决策就会从一个阶段进入另一个阶段，状态也就发生了转移。一次决策就会从一个阶段进入另一个阶段，状态也就发生了转移。
20、动态规划的基本概念动态规划的基本概念 4、策略和最优策略、策略和最优策略 所有阶段按照约定的决策方法，依次排列构成问题的求解全所有阶段按照约定的决策方法，依次排列构成问题的求解全过程。这些决策的总体称为策略。在实际问题中，从决策允许集过程。这些决策的总体称为策略。在实际问题中，从决策允许集合中找出最优效果的策略称为最优策略。合中找出最优效果的策略称为最优策略。5、状态转移方程、状态转移方程 前一阶段的终点就是后一阶段的起点，这种关系描述了由前一阶段的终点就是后一阶段的起点，这种关系描述了由K阶段到阶段到K+1阶段状态的演变规律，是关于两个相邻阶段状态的阶段状态的演变规律，是关于两个相邻阶段状态
21、的方程，称为状态转移方程，是动态规划的核心。方程，称为状态转移方程，是动态规划的核心。6、指标函数和最优化概念、指标函数和最优化概念 用来衡量多阶段决策过程优劣的一种数量指标，称为指标用来衡量多阶段决策过程优劣的一种数量指标，称为指标函数。它应该在全过程和所有子过程中有定义、并且可度量。函数。它应该在全过程和所有子过程中有定义、并且可度量。指标函数的最优值，称为最优值函数。指标函数的最优值，称为最优值函数。动态规划的基本概念动态规划的基本概念 动态规划所处理的问题是一个动态规划所处理的问题是一个“多阶段决策问题多阶段决策问题”目的是得到一个最优解（方案）目的是得到一个最优解（方案）大概思想如下
22、图所示：大概思想如下图所示：运用动态规划的条件运用动态规划的条件 1 1、最优化原理、最优化原理 作为整个过程的最优策略具有：无论过去的状态和决策如作为整个过程的最优策略具有：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。也可以通俗地理解为：子问题的局部最优将最优策略的性质。也可以通俗地理解为：子问题的局部最优将导致整个问题的全局最优，即问题具有导致整个问题的全局最优，即问题具有最优子结构最优子结构的性质。也的性质。也就是说一个问题的最优解只取决于其子问题的最优解，非最优就是说一个问题的最优解只
23、取决于其子问题的最优解，非最优解对问题的求解没有影响。解对问题的求解没有影响。比如前面的数字三角形问题，如果我们想求走到某一位置比如前面的数字三角形问题，如果我们想求走到某一位置的最优路径，我们只需要知道其左上方或正上方两个位置之一的最优路径，我们只需要知道其左上方或正上方两个位置之一的最优值，而不用考虑其它的路径，因为其它的非最优路径肯的最优值，而不用考虑其它的路径，因为其它的非最优路径肯定对当前位置的结果没有影响。定对当前位置的结果没有影响。运用动态规划的条件运用动态规划的条件 1 1、最优化原理、最优化原理 在数字三角形问题中，如果我们把问题稍微改变一下：将在数字三角形问题中，如果我们把
24、问题稍微改变一下：将三角形中的数字改为三角形中的数字改为-100100之间的整数，计算从顶至底的之间的整数，计算从顶至底的某处的一条路径，使该路径所经过的数字的某处的一条路径，使该路径所经过的数字的总和最接近于零总和最接近于零。这个问题就不具有最优子结构性质了，因为子问题最优，这个问题就不具有最优子结构性质了，因为子问题最优，即最接近于零，反而可能造成问题的解远离零，这样的反例是即最接近于零，反而可能造成问题的解远离零，这样的反例是不难构造的，本问题就不能用动态规划的方法解决了。不难构造的，本问题就不能用动态规划的方法解决了。因此，并不是所有的因此，并不是所有的“决策问题决策问题”都可以用都可
25、以用“动态规划动态规划”来解决。只有当一个问题呈现出最优子结构时，来解决。只有当一个问题呈现出最优子结构时，“动态规划动态规划”才可能是一个合适的侯选方法。才可能是一个合适的侯选方法。运用动态规划的条件运用动态规划的条件 2 2、无后效性原则、无后效性原则1 1、最优化原理、最优化原理 所谓无后效性原则，指的是这样一种性质：某一阶段的状所谓无后效性原则，指的是这样一种性质：某一阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说响。也就是说“未来与过去无关未来与过去无关”。当前的状态是此前历史的。当前的状态是此前历史的
26、一个完整总结，此前的历史只能通过当前的状态去影响过程未一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段具体地说，如果一个问题被划分各个阶段之后，阶段I中中的状态只能由阶段的状态只能由阶段I+1中的状态转移方程得来，与其他没有关中的状态转移方程得来，与其他没有关系，特别是与未发生的状态没有关系，这就是无后效性。系，特别是与未发生的状态没有关系，这就是无后效性。运用动态规划的条件运用动态规划的条件 2 2、无后效性原则、无后效性原则1 1、最优化原理、最优化原理例如：给定一个平面上的例如：给定一个平面上的n个点的坐标，规定必须
27、个点的坐标，规定必须从最左边一个点开始，严从最左边一个点开始，严格地从左至右访问到最右格地从左至右访问到最右边的点，再严格地由右向边的点，再严格地由右向左访问到出发点，编程确左访问到出发点，编程确定一条连接各个点的闭合定一条连接各个点的闭合的游历路线，要求整个路的游历路线，要求整个路程最短的路径长度。程最短的路径长度。分析：分析：本题可以根据本题可以根据起点，终点起点，终点划划分阶段，且满足无后效性原则，可分阶段，且满足无后效性原则，可以考虑用动态规划做。以考虑用动态规划做。但如果把但如果把“规定必须从最左边规定必须从最左边一个点开始，严格地从左至右访问一个点开始，严格地从左至右访问到最右边的
28、点，再严格地由右向左到最右边的点，再严格地由右向左访问到出发点访问到出发点”这个限制条件去掉，这个限制条件去掉，则阶段与阶段之间没有什么必然的则阶段与阶段之间没有什么必然的“顺序顺序”，而且把各个阶段画成一，而且把各个阶段画成一个图后会出现个图后会出现“环路环路”，所以有，所以有“后效性后效性”，就不能用动态规划做了。，就不能用动态规划做了。动态规划的实质是分治思想和解决冗余，动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题分解为更小的、因此，动态规划是一种将问题分解为更小的、相似的子问题，并存储子问题的解而避免计算相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优
29、化问题的算法策略。重复的子问题，以解决最优化问题的算法策略。这类问题会有多种可能的解，每个解都有一个这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值，而动态规划找出其中最优（最大或最小）解。若存在多个最优解的话，它只取其中的一解。若存在多个最优解的话，它只取其中的一个。个。动态规划的基本概念动态规划的基本概念 动态规划应用举例动态规划应用举例 例例1、挖地雷（、挖地雷（NOIP1996）在一个地图上有在一个地图上有N个地窖（个地窖（N=200），每个地窖中埋有一），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都定数量的地雷。同时，给出
30、地窖之间的连接路径，并规定路径都是单向的。某人可以从任一处开始挖地雷，然后沿着指出的连接是单向的。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。计一个挖地雷的方案，使他能挖到最多的地雷。输入输入 N 地窖的个数地窖的个数 W1 W2WN 每个地窖中的地雷数每个地窖中的地雷数 X1 Y1 表示可从表示可从X1到到Y1 X2 Y2 0 0 表示输入结束表示输入结束输出输出 K1K2Kv 挖地雷的顺序挖地雷的顺序 MAX 最多挖出的地雷数最多挖出的
31、地雷数输入：65 10 20 5 4 51 21 42 43 44 54 65 60 0输出：3-4-5-634挖地雷问题分析挖地雷问题分析 设设W（i）为第）为第i个地窖所藏有的地雷数，个地窖所藏有的地雷数，A（i,j）表示第）表示第i个个地窖与第地窖与第j个地窖之间是否有通路，个地窖之间是否有通路，F（i）为从第）为从第i个地窖开始最多个地窖开始最多可以挖出的地雷数。可以挖出的地雷数。动态规划应用举例动态规划应用举例 F（i）=MAX F(j)+W(i)(ij=n,A(i,j)=1)边界：边界：F（n）=W(n)于是就可以通过递推的方法，从后（即于是就可以通过递推的方法，从后（即F（n）往
32、前逐个）往前逐个找出所有的找出所有的F（i），再从中找一个最大的即为第），再从中找一个最大的即为第2问的解。问的解。对于具体所走的路径（第对于具体所走的路径（第2问），可以通过一个向后的链接问），可以通过一个向后的链接来实现。来实现。动态规划应用举例动态规划应用举例 例例2、接苹果、接苹果(apples)农场的夏季是收获的好季节。在农场的夏季是收获的好季节。在John的农场，他们用一种特的农场，他们用一种特别的方式来收苹果：别的方式来收苹果：Bessie摇苹果树，苹果落下，然后摇苹果树，苹果落下，然后John尽尽力接到尽可能多的苹果。作为一个有经验的农夫，力接到尽可能多的苹果。作为一个有经验的
33、农夫，John将这个过将这个过程坐标化。他清楚地知道什么时候程坐标化。他清楚地知道什么时候(1=t=1,000,000)什么位置什么位置(用二维坐标表示，用二维坐标表示，-1000=x,y=1000)会有苹果落下。他只会有苹果落下。他只有提前到达那个位置，才能接到那个位置掉下的苹果。一个单位有提前到达那个位置，才能接到那个位置掉下的苹果。一个单位时间，时间，John能走能走s(1=s=1000)个单位。假设他开始时个单位。假设他开始时(t=0)站在站在(0,0)点，他最多能接到多少个苹果？点，他最多能接到多少个苹果？输入：第一行是两个整数输入：第一行是两个整数N(苹果个数，苹果个数，N=500
34、0)和和S(速度速度)；第第2.N+1行：每行行：每行3个整数个整数Xi,Yi,Ti，表示每个苹果掉下，表示每个苹果掉下 的位置和落下的时间。的位置和落下的时间。输出：仅一行，一个数，表示最多能接到几个苹果。输出：仅一行，一个数，表示最多能接到几个苹果。动态规划应用举例动态规划应用举例 样例样例5 30 0 10 3 2-5 12 6-1 0 3-1 1 23说明：说明：John可以接到第可以接到第1,5,4个苹果。个苹果。动态规划应用举例动态规划应用举例 接苹果问题分析接苹果问题分析 首先划分阶段，很明显，按照苹果掉落的时间先后顺序来划首先划分阶段，很明显，按照苹果掉落的时间先后顺序来划分阶
35、段，所以有必要按时间从小到大给各个苹果排个序，并按顺分阶段，所以有必要按时间从小到大给各个苹果排个序，并按顺序标上序标上1.n的编号。的编号。假如假如John现在正站在某个位置上接苹果，为了使他到当前为现在正站在某个位置上接苹果，为了使他到当前为止接到的苹果数最大，我们想要知道的是他前一步在哪个位置接止接到的苹果数最大，我们想要知道的是他前一步在哪个位置接苹果，并且要知道到那个位置为止接到的苹果最多是多少。苹果，并且要知道到那个位置为止接到的苹果最多是多少。假设假设dis(i，j)表示第表示第i个苹果与第个苹果与第j个苹果之间的直线距离。个苹果之间的直线距离。time(i)表示第表示第i个苹果
36、掉落的时刻。个苹果掉落的时刻。F(i)表示表示John当前站在第当前站在第i个个苹果的位置上最多能接到的苹果总数（包括他以前接的）。苹果的位置上最多能接到的苹果总数（包括他以前接的）。F(i)=max F(j)+1 其中其中0=j=i-1，且，且dis(i,j)=(time(i)-time(j)*S 初始条件：初始条件：F(0)=0表示表示John站在出发点站在出发点(0,0)时一个苹果也没接到。时一个苹果也没接到。动态规划应用举例动态规划应用举例 例例3、低价购买（、低价购买（buylow）“低价购买低价购买”这条建议是在股票市场取得成功的一半规则。要想被认为是这条建议是在股票市场取得成功的
37、一半规则。要想被认为是伟大的投资者，你必须遵循以下的购买建议：低价购买，再低价购买。每次你伟大的投资者，你必须遵循以下的购买建议：低价购买，再低价购买。每次你购买一支股票，你必须用低于你上次购买它的价格购买它。买的次数越多越好购买一支股票，你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价你将被给出一段时间内一支股票每天的出售价(216范围内的正整数范围内的正整数)，你，你可以选择在哪些天购买这支股票。每次购买都必须遵循可以选择在
38、哪些天购买这支股票。每次购买都必须遵循“低价购买，再低价购低价购买，再低价购买买”的原则。的原则。写一个程序计算最大购买次数。写一个程序计算最大购买次数。这里是某支股票的价格清单：这里是某支股票的价格清单：日期日期 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行为行为
39、 N(1=N=5000)，表示股票发行天数；，表示股票发行天数；第第2行行:N个数，是每天的股票价格。个数，是每天的股票价格。输出输出 输出两个数输出两个数:最大购买次数和拥有最大购买次数的方案数最大购买次数和拥有最大购买次数的方案数(=231)当两种方案当两种方案“看起来一样看起来一样”时（就是说它们构成的价格队列一样时），这时（就是说它们构成的价格队列一样时），这两两种方案被认为是相同的。种方案被认为是相同的。样例样例1269 68 54 70 68 64 70 67 78 62 98 874 4先探索一下样例，最大购先探索一下样例，最大购买次数为买次数为4次，共有次，共有4种方种方案，分
40、别为：案，分别为：69、68、64、6269、68、67、6270、68、64、6270、68、67、62动态规划应用举例动态规划应用举例 我们发现，这道题和我们发现，这道题和“导弹问题导弹问题”的几乎完全相同！实际上是在的几乎完全相同！实际上是在一个数列中选出一个序列，使得这个序列是一个下降序列（即序一个数列中选出一个序列，使得这个序列是一个下降序列（即序列中的任意一个数必须大于它后面的任何一个数），且要使这个列中的任意一个数必须大于它后面的任何一个数），且要使这个序列的长度最长。但是这道题要输出总的方案数，这就需要对原序列的长度最长。但是这道题要输出总的方案数，这就需要对原有的求解过程作一
41、些变动。求方案总数最主要的是要剔除重复方有的求解过程作一些变动。求方案总数最主要的是要剔除重复方案。在样例中，第案。在样例中，第2和第和第5个数都是个数都是68。以第一个。以第一个68结尾的最长结尾的最长下降序列的方案为下降序列的方案为69、68；以第二个；以第二个68结尾的最长下降序列的结尾的最长下降序列的方案为方案为69、68 和和70、68这时候就产生了方案的重复，即产这时候就产生了方案的重复，即产生了两个生了两个69、68。显然后面的。显然后面的68要比前面一个更优，因为后面要比前面一个更优，因为后面的的68位置更靠后，以这个位置更靠后，以这个68结尾的最长下降序列的总数肯定要结尾的最
42、长下降序列的总数肯定要比前面一个多，而且其方案必定囊括了前面一个比前面一个多，而且其方案必定囊括了前面一个68的所有方案。的所有方案。因此，在解题过程中，我们就可以只考虑后面一个因此，在解题过程中，我们就可以只考虑后面一个68。推广开来，。推广开来，如果当前状态之前存在重复的状态，我们只要考虑离当前状态位如果当前状态之前存在重复的状态，我们只要考虑离当前状态位置最近的那一个即可。置最近的那一个即可。动态规划应用举例动态规划应用举例 设设F（i）表示到第）表示到第i天，能够购买的最大次数。天，能够购买的最大次数。其中：其中：1=j=i-1，且，且OKj=trueOKj=true表示相同价格时，该
43、位置更优。表示相同价格时，该位置更优。F（1）=1F（i）=max F(j)+1 总总 结结1 1、递推的边界条件一般很明显，而动态规划的边界条件比较隐蔽，、递推的边界条件一般很明显，而动态规划的边界条件比较隐蔽，容易被忽视；容易被忽视；2 2、递推的数学性一般较强，而动态规划的数学性相对较弱；、递推的数学性一般较强，而动态规划的数学性相对较弱；3 3、递推一般不划分阶段，而动态规划一般有较为明显的阶段；、递推一般不划分阶段，而动态规划一般有较为明显的阶段；4 4、动态规划往往是用来求一个最优值，而一般的递推往往是用来、动态规划往往是用来求一个最优值，而一般的递推往往是用来计数或是求一个值。计数或是求一个值。动态规划和一般递推的不同点？动态规划和一般递推的不同点？动态规划和一般递推的相同点？动态规划和一般递推的相同点？无后效性和有边界条件。无后效性和有边界条件。上机调试所有课堂上的例题。