第二次课动态规划精选文档.ppt

《第二次课动态规划精选文档.ppt》由会员分享，可在线阅读，更多相关《第二次课动态规划精选文档.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二次课动态规划本讲稿第一页，共八十四页本周POJ上做题：动态规划n1037 A decorative fence1037 A decorative fence、1050 To the Max1050 To the Max、1088 1088 滑雪、滑雪、1125 Stockbroker Grapevine1125 Stockbroker Grapevine、1141 Brackets Sequence1141 Brackets Sequence、1159 Palindrome1159 Palindrome、1160 Post Office1160 Post Office、1163 The T

2、riangle1163 The Triangle、1458 Common Subsequence1458 Common Subsequence、1579 Function Run Fun1579 Function Run Fun、1887 Testing the CATCHER1887 Testing the CATCHER、1953 World Cup Noise1953 World Cup Noise、2386 Lake Counting2386 Lake Counting本讲稿第二页，共八十四页 动动态态规规划划是是19511951年年由由美美国国数数学学家家贝贝尔尔曼曼（Richard

3、 Richard Bellman)Bellman)提提出出，它它是解决一类多阶段决策问题的优化方法，也是考察问题的一种途径。是解决一类多阶段决策问题的优化方法，也是考察问题的一种途径。动动态态规规划划方方法法是是现现代代企企业业管管理理中中的的一一种种重重要要决决策策方方法法。如如果果一一个个问问题题可可将将其其过过程程划划分分为为若若干干个个相相互互联联系系的的阶阶段段问问题题，且且它它的的每每一一阶阶段段都都需需进进行决策，则这类问题均可用动态规划方法进行求解。行决策，则这类问题均可用动态规划方法进行求解。根根据据多多阶阶段段决决策策过过程程的的时时序序和和决决策策过过程程的的演演变变，动

4、动态态规规划划方方法法有有以以下下四四种种类类型型：离离散散确确定定型型、离离散散随随机机型型、连连续续确确定定型型和和连续随机型连续随机型。本讲稿第三页，共八十四页几类算法的经典名言n n动态规划：不做重复的事；动态规划：不做重复的事；n n贪心法：只选最好的；贪心法：只选最好的；贪心法：只选最好的；贪心法：只选最好的；n n分支定界法：没戏的就杀掉；分支定界法：没戏的就杀掉；分支定界法：没戏的就杀掉；分支定界法：没戏的就杀掉；n n回溯法：碰壁就回头。回溯法：碰壁就回头。回溯法：碰壁就回头。回溯法：碰壁就回头。作人生规划要善于利用动态规划；作人生规划要善于利用动态规划；找女朋友要善于利用好

5、贪心算法；找女朋友要善于利用好贪心算法；人生重大决策要活学活用回溯法；人生重大决策要活学活用回溯法；本讲稿第四页，共八十四页算法总体思想n动态规划算法与分治法类似，其基本思想也是将待求解问题分解成动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)=本讲稿第五页，共八十四页为什么动态规划比递归算法有效？n但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解

6、时，有些子问题被重复计算了许多次，因此利多项式量级。在用分治法求解时，有些子问题被重复计算了许多次，因此利用递归算法得到的算法往往是指数复杂度的算法。用递归算法得到的算法往往是指数复杂度的算法。n如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。可以避免大量重复计算，从而得到多项式时间算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/

7、4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)本讲稿第六页，共八十四页POJ 2753 Fibonacci数列例子：n确定确定Fibonacci sequence fnFibonacci sequence fn项的值项的值:n考虑考虑Fibonacci sequenceFibonacci sequence的递归定义的递归定义:n我们将得到如下的递归算法我们将得到如下的递归算法:在POJ上递交之后，返回的结果是：Time Limited。而不是可爱的ACWhy？本讲稿第七页，共八十四页子问题的重叠性 n将上述递归算法展开将

8、上述递归算法展开:n可以看出可以看出 f(n-1)f(n-1)被调用被调用 1 1次次,f(n-2),f(n-2)被调用被调用 2 2次次,等等等等.n这将导致大量的调用这将导致大量的调用 n最终解为：最终解为：本讲稿第八页，共八十四页树形递归计算过程中存在冗余计算过程中存在冗余计算，为了除去冗余计算，为了除去冗余计算，可以从已知条计算，可以从已知条件开始计算，并记录件开始计算，并记录计算过程中的中间结计算过程中的中间结果。果。f(5)f(3)f(2)f(1)f(2)f(4)f(0)f(1)f(0)f(3)f(2)f(1)f(1)f(0)f(1)11001010冗余计算冗余计算本讲稿第九页，共

9、八十四页动态规划n例：例：POJ 2753 FibonacciPOJ 2753 Fibonacci数列数列int fn+1;int fn+1;f1=f2=1;f1=f2=1;int I;int I;for(i=3;i=n;i+)for(i=3;i=n;i+)fi=fi-1+fi-2;fi=fi-1+fi-2;cout fn endl;cout fn endl;用空间换时间用空间换时间本讲稿第十页，共八十四页动态规划算法的基本要素一、最优子结构一、最优子结构一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状

10、态而言，余下的诸决策必须构成最优策略。简而言之，一个策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其为最优化策略的子策略总是最优的。一个问题满足最优化原理又称其为最优最优子结构性质子结构性质。同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）例如：最短路径问题。a b c在分析问题的最优子结构性质时，所用的方法具有普遍性：首先在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法假设由问题的最优解导出的子问题的解不是

11、最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。矛盾。本讲稿第十一页，共八十四页动态规划算法的基本要素二、重叠子问题二、重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为问题被反复计算多次。这种性质称为子问题的重叠性质子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间

12、查看一表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。划算法只需要多项式时间，从而获得较高的解题效率。本讲稿第十二页，共八十四页一、例子（最短路问题）一、例子（最短路问题）假如上图是一个线路网络，两点之间连线上的数字表示两点间的距假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从离（或费用），我们的问题是要将货物从A A地运往地运往E E地，中间通过地，中间通过B

13、 B、C C、D D三个区域，在区域内有多条路径可走，现求一条由三个区域，在区域内有多条路径可走，现求一条由A A到到E E的线路，的线路，使总距离最短（或总费用最小）。使总距离最短（或总费用最小）。AB1B2B3C1C2C3D1D2E24374632426534633334本讲稿第十三页，共八十四页将该问题划分为将该问题划分为4 4个阶段的决策问题个阶段的决策问题第一阶段为从第一阶段为从A A到到B Bj j（j=1j=1，2 2，3 3），有三种决策方案可供选择；），有三种决策方案可供选择；第二阶段为从第二阶段为从B Bj j到到C Cj j（j=1,2,3j=1,2,3），也有三种方案可

14、供选择；），也有三种方案可供选择；第第三三阶阶段段为为从从C Cj j到到D Dj j(j=1,2)(j=1,2)，有有两两种种方方案案可可供供选选择择；第第四四阶阶段段为为从从D Dj j到到E E，只有一种方案选择。，只有一种方案选择。AB1B2B3C1C2C3D1D2E24374632426534633334本讲稿第十四页，共八十四页如如果果用用完完全全枚枚举举法法，则则可可供供选选择择的的路路线线有有3321=183321=18（条条），将其一一比较才可找出最短路线：，将其一一比较才可找出最短路线：ABAB1 1CC2 2DD3 3EE其长度为其长度为1212。AB1B2B3C1C2C

15、3D1D2E24374632426534633334本讲稿第十五页，共八十四页n显然，这种方法是不经济的，特别是当阶段数很多，显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。上完成也是不现实的。n由于我们考虑的是从全局上解决求由于我们考虑的是从全局上解决求A A到到E E的最短路问题，的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至阶段开始计算，由后向前逐步推至A A点：点：本讲稿第十六页，共八

16、十四页第四阶段，由第四阶段，由D D1 1到到E E只有一条路线，其长度只有一条路线，其长度f f4 4（D D1 1）=3=3，同理同理f f4 4（D D2 2）=4=4。第三阶段，由第三阶段，由C Cj j到到D Di i分别均有两种选择，即分别均有两种选择，即，决策点为D1AB1B2B3C1C2C3D1D2E24374632426534633334本讲稿第十七页，共八十四页,决 策 点 为D1，决策点为D2AB1B2B3C1C2C3D1D2E24374632426534633334本讲稿第十八页，共八十四页第二阶段，由Bj到Cj分别均有三种选择，即：决策点为C2 AB1B2B3C1C2

17、C3D1D2E24374632426534633334本讲稿第十九页，共八十四页决策点为C1或C2决策点为C2 AB1B2B3C1C2C3D1D2E24374632426534633334本讲稿第二十页，共八十四页第一阶段，由A到B，有三种选择，即：决策点为B3f1（A）=15说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得。即AB3C2D2E上述最短路线问题的计算过程，也可借助于图形直观的表示出来：AB1B2B3C1C2C3D1D2E24374632426534633334本讲稿第二十一页，共八十四页图图中中各各点点上上方方框框的的数数，表表示示该该点点到到E E的的最最短短

18、距距离离。图图中中红红箭箭线线表表示从示从A A到到E E的最短路线。的最短路线。从引例的求解过程可以得到以下启示：从引例的求解过程可以得到以下启示：对对一一个个问问题题是是否否用用上上述述方方法法求求解解，其其关关键键在在于于能能否否将将问问题题转转化化为相互联系的决策过程相同的多个阶段决策问题。为相互联系的决策过程相同的多个阶段决策问题。AB1B2B3C1C2C3D1D2E2437463242653463333434676991112本讲稿第二十二页，共八十四页所所谓谓多多阶阶段段决决策策问问题题是是：把把一一个个问问题题看看作作是是一一个个前前后后关关联联具具有有链状结构的多阶段过程，也

19、称为序贯决策过程。如下图所示：链状结构的多阶段过程，也称为序贯决策过程。如下图所示：在在处处理理各各阶阶段段决决策策的的选选取取上上，不不仅仅只只依依赖赖于于当当前前面面临临的的状状态态，而而且且还还要要注注意意对对以以后后的的发发展展。即即是是从从全全局局考考虑虑解解决决局局部部（阶阶段段）的的问问题。题。各各阶阶段段选选取取的的决决策策，一一般般与与“时时序序”有有关关，决决策策依依赖赖于于当当前前的的状状态态，又又随随即即引引起起状状态态的的转转移移，整整个个决决策策序序列列就就是是在在变变化化的的状状态态中中产产生生出出来来，故有故有“动态动态”含义。因此，把这种方法称为动态规划方法。

20、含义。因此，把这种方法称为动态规划方法。决策过程是与阶段发展过程逆向而行。决策过程是与阶段发展过程逆向而行。本讲稿第二十三页，共八十四页拦截导弹（poj1887）n某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。本讲稿第二十四页，共八十四页n输入输入数据为导弹依次飞来的高度，所有高度值均为不大于30000的正整数。n输出输出只有一行是这套系统最多能拦截的导弹数。本讲稿第二十五页

21、，共八十四页n输入样例389 207 155 300 299 170 158 65n输入样例6本讲稿第二十六页，共八十四页题目分析n因为只有一套导弹拦截系统，并且这套系统除了第一发炮弹能到达任意高度外，以后的每一发炮弹都不能高于前一发炮弹的高度；所以，被拦截的导弹应该按飞来的高度组成一个非递增序列。n题目要求我们计算这套系统最多能拦截的导弹数，并依次输出被拦截导弹的高度，实际上就是要求我们在导弹依次飞来的高度序列中寻找一个最长非递增子序列。本讲稿第二十七页，共八十四页n设X=x1,x2,xn为依次飞来的导弹序列，Y=y1,y2,yk为问题的最优解（即X的最长非递增子序列），s为问题的状态（表示

22、导弹拦截系统当前发送炮弹能够到达的最大高度，初值为s=第一发炮弹能够到达任意的高度）。本讲稿第二十八页，共八十四页n如果y1=x1，即飞来的第一枚导弹被成功拦截。那么，根据题意“每一发炮弹都不能高于前一发的高度”，问题的状态将由s=变成sx1（x1为第一枚导弹的高度）；本讲稿第二十九页，共八十四页n在当前状态下，序列Y1=y2,yk也应该是序列X1=x2,xn的最长非递增子序列（大家用反证法很容易证明）。n也就是说，在当前状态sx1下，问题的最优解Y所包含的子问题（序列X1）的解（序列Y1）也是最优的。这就是拦截导弹问题的最优子结构性质。本讲稿第三十页，共八十四页n设D(i)为第i枚导弹被拦截

23、之后，这套系统最多还能拦截的导弹数（包含被拦截的第i枚）。n我们可以设想，当系统拦截了第k枚导弹xk，而xk又是序列X=x1,x2,xn中的最小值，即第k枚导弹为所有飞来的导弹中高度最低的，则有D(k)=1；当系统拦截了最后一枚导弹xn，那么，系统最多也只能拦截这一枚导弹了，即D(n)=1；其它情况下，也应该有D(i)1。本讲稿第三十一页，共八十四页n根据以上分析，可归纳出问题的动态规划递归方程为：本讲稿第三十二页，共八十四页n假设系统最多能拦截的导弹数为dmax（即问题的最优值），则 ndmax （i为被系统拦截的第一枚导弹的顺序号）本讲稿第三十三页，共八十四页n所以，要计算问题的最优值dm

24、ax，需要分别计算出D（1）、D（2）、D（n）的值，然后将它们进行比较，找出其中的最大值。本讲稿第三十四页，共八十四页n根据上面分析出来的递归方程，我们完全可以设计一个递归函数，采用自顶向下的方法计算D（i）的值。然后，对i从1到n分别调用这个递归函数，就可以计算出D（1）、D（2）、D（n）。本讲稿第三十五页，共八十四页n但这样将会有大量的子问题被重复计算。比如在调用递归函数计算D（1）的时候，可能需要先计算D（5）的值；之后在分别调用递归函数计算D（2）、D（3）、D（4）的时候，都有可能需要先计算D（5）的值。如此一来，在整个问题的求解过程中，D（5）可能会被重复计算很多次，从而造成了

25、冗余，降低了程序的效率。本讲稿第三十六页，共八十四页n其实，通过以上分析，我们已经知道：D（n）=1。如果将n作为阶段对问题进行划分，根据问题的动态规划递归方程，我们可以采用自底向上的方法依次计算出D（n-1）、D（n-2）、D（1）的值。这样，每个D（i）的值只计算一次，并在计算的同时把计算结果保存下来，从而避免了有些子问题被重复计算的情况发生，提高了程序的效率。本讲稿第三十七页，共八十四页int main（）int h2000,d2000,count,c,max,i,j;/h表示高度值，d表示最优值，c是能拦截得最多导弹数 count=0;while（scanf（%d,h+count+）!

26、=EOF）;/输入高度 dcount-1=1;c=1;for（i=count-2;icount;j+）if（(hi=hj)&maxdj）max=dj;di=max+1;if(cdi)c=di;printf（%dn,c）;本讲稿第三十八页，共八十四页思考题n上述问题修改成：要求拦截所有导弹，则需要多少套上述系统？本讲稿第三十九页，共八十四页实例POJ2122：Flight PlanningYour job is to write a program that plans airplane flights.Each flight consists of a series of one or mor

27、e legs.Your program must choose the best altitude for each leg to minimize the amount of fuel consumption during the trip.本讲稿第四十页，共八十四页The airplane has a fixed airspeed,given by the constant VCRUISE,and a most-efficient cruising altitude,AOPT.When flying at altitude AOPT,fuel consumption in gallons

28、per hour is given by GPHOPT.When flying at an altitude that is different from AOPT,fuel consumption increases by GPHEXTRA for each 1000 feet above or below AOPT.本讲稿第四十一页，共八十四页The flight starts and finishes at an altitude of 0.Each 1000 foot climb burns an extra amount of fuel given by CLIMBCOST(ther

29、e is no reduction in fuel consumption when you descend).Make the approximation that all climbing and descending is done in zero time at the beginning of each flight leg.本讲稿第四十二页，共八十四页Thus each leg is flown at a constant airspeed and altitude.For this problem,the airplane characteristics are given by

30、 the following constants:本讲稿第四十三页，共八十四页 VCRUISE 400 knots(a knot is one nautical mile(1.852km)per hour)AOPT 30,000 feetGPHOPT 2000 gallons per hourGPHEXTRA 10 gallons per hour for each 1000 feetCLIMBCOST 50 gallons per 1000 feet of climb本讲稿第四十四页，共八十四页Before each flight,you are given the length of ea

31、ch leg and the tailwind expected for each leg.A positive tailwind increases the airplanes speed over the ground,and a negative tailwind decreases its speed over the ground.For example,if airspeed is 400 knots and the tailwind is-50 knots,speed over the ground is 350 knots.本讲稿第四十五页，共八十四页nBy policy,al

32、titude for each leg must be some integer multiple of 1000 feet,between 20,000 and 40,000 feet,inclusive.Your program must compute the best altitude for each leg to minimize overall fuel consumption for the trip,and must compute the fuel required for the trip.本讲稿第四十六页，共八十四页nInputThe first line contai

33、ns an integer N,representing the number of flights you are required to plan.Each flight consists of the following input lines:The first input line in a flight contains an integer K(0 K 10),representing the number of legs in the flight.The next K input lines each contain the following three integers:

34、(1)The length of the leg,in nautical miles(2)The expected tailwind at 20,000 feet,in knots(3)The expected tailwind at 40,000 feet,in knots本讲稿第四十七页，共八十四页nThe expected tailwind at altitudes between 20,000 and 40,000 feet is computed by linear interpolation.For example,the expected tailwind at 30,000 f

35、eet is halfway between the expected tailwind at 20,000 feet and the expected tailwind at 40,000 feet.本讲稿第四十八页，共八十四页nOutputYour program must produce one output line for each flight.The output line must contain the flight number(counting from the beginning of the problem),the chosen altitude for each

36、leg(in thousands of feet),and the fuel required for the trip(in gallons,to the nearest gallon).本讲稿第四十九页，共八十四页Sample Input221500-50 501000 0 031000 50 02000 0 201800-50 100Output for the Sample InputFlight 1:35 30 13985Flight 2:20 30 40 23983本讲稿第五十页，共八十四页图例：本讲稿第五十一页，共八十四页转换为多段图问题nFlight PlanFlight Pl

37、an可以转换为多段图问题，每一条边代表某段由前一段可以转换为多段图问题，每一条边代表某段由前一段飞行高度飞到本段的某一飞行高度的燃油消耗量飞行高度飞到本段的某一飞行高度的燃油消耗量本讲稿第五十二页，共八十四页Analysis n一、计算飞机在地域一、计算飞机在地域i i的耗油量的耗油量 假设飞机在地域假设飞机在地域i-1i-1（2ik+12ik+1）的海拔高度为）的海拔高度为l l，飞到地域，飞到地域i i的海拔高度为的海拔高度为m m，计算飞机在地域，计算飞机在地域i i的耗油量的耗油量gi,l,mgi,l,m必须考必须考虑如下几个因素虑如下几个因素：（注意：为了方便计算，飞行高度和风速以：

38、（注意：为了方便计算，飞行高度和风速以1000feet1000feet为单位）为单位）n1.1.上升过程增加的耗油量上升过程增加的耗油量a a 由于飞机每上升一个单位，需要增加由于飞机每上升一个单位，需要增加climbcostclimbcost的耗油量，因此的耗油量，因此 本讲稿第五十三页，共八十四页Analysis n2.2.每小时的实际耗油量每小时的实际耗油量b b 飞机在海拔高度飞机在海拔高度aoptaopt飞行时每小时耗油飞行时每小时耗油gphopt.gphopt.当飞机在当飞机在m m高度飞行时，与高度飞行时，与aoptaopt的垂直距离为的垂直距离为 个单个单位。每垂直偏离位。每垂

39、直偏离aoptaopt高度一个单位，需要增加耗油量高度一个单位，需要增加耗油量gphextra.gphextra.因此因此本讲稿第五十四页，共八十四页n3.3.在地域在地域i i的实际飞行时间的实际飞行时间c c c=c=地域地域i i的长度的长度/地域地域i i的实际飞行速度的实际飞行速度 由于地域由于地域i i的风速垂直反向线性变化，的风速垂直反向线性变化，m m单位处的风速单位处的风速为在为在2020单位处的风速与单位处的风速与4040单位处的风速的平均数，因此单位处的风速的平均数，因此地域地域i i的等高风速为的等高风速为 本讲稿第五十五页，共八十四页 而飞机的实际速度为而飞机的实际速

40、度为VCRUISEVCRUISE与地域与地域i i等高风速的矢量和，等高风速的矢量和，因此因此 c=c=地域地域i i的长度的长度/(/(地域地域i i的等高风速的等高风速VCRUISE)VCRUISE)显而易见，显而易见，本讲稿第五十六页，共八十四页n二规划飞行方案二规划飞行方案 设设 为在确定地域为在确定地域i i的飞行高度为的飞行高度为j j的情况下，的情况下，飞机由地域飞机由地域l l飞至地域飞至地域i i所耗费的最小总耗油量；所耗费的最小总耗油量；为记忆表。飞机由地域为记忆表。飞机由地域i-li-l的的 高度到达地域高度到达地域i i的的j j高度，可使总耗油量最小，即高度，可使总耗

41、油量最小，即 本讲稿第五十七页，共八十四页n问题是怎么才能计算问题是怎么才能计算 呢？呢？首先我们必须明确，按最优性要求确定了飞机首先我们必须明确，按最优性要求确定了飞机在地域在地域i-1i-1的飞行为高度为的飞行为高度为 ;由于由于 为一个定值，因此为一个定值，因此 的值必须最小。不然的话，将它替换到的值必须最小。不然的话，将它替换到 表达式中，则可使表达式值变得更小，出现矛盾，表达式中，则可使表达式值变得更小，出现矛盾，这就说明问题的最优解包含了子问题的最优解，即这就说明问题的最优解包含了子问题的最优解，即该问题具备了最优子结构。该问题具备了最优子结构。本讲稿第五十八页，共八十四页 下面我

42、们来分析一下最优表达式的构造：n飞机由地域1起飞，因此data1,j=g1,0,j(20j40).n然后顺序计算，data2,20 data2,40,data3,20,data3,40,.datak,20,datak,40.本讲稿第五十九页，共八十四页 在计算datai,j时，我们无法预计飞机在地域i-1应以怎样的高度飞行方可使表达式的值最小。因此只能一一假设飞机在地域i-1的高度为20,21,40,即分别求出n从上述21个表达式中选出值最小的一个，即：将满足上式的飞行高度L存入记忆表data2i,j本讲稿第六十页，共八十四页 n由此可见，在求datai,j的过程中不断查阅子问题的解datai

43、-1,20.datai-1,40。显然这个最优化问题包含了重叠子问题，采用动态程序设计方法是最合适不过的了，按照上述分析，我们可以直接写出动态规划的方程：1ik 20j40 20l40本讲稿第六十一页，共八十四页 n求解data表和data2表的算法十分简单：for j:=20 to 40 do data1,j g1,0,j;/*构造记忆表*/for i:=2 to k do for j:=20 to 40 do for i:=20 to 40 do begin 计算datai,j=mindatai-1,l,gi,l,j;将满足上式的l记入记忆表data2i,j;end:for本讲稿第六十二页

44、，共八十四页三三.输出飞行计划输出飞行计划 有了记忆表有了记忆表data2data2我们便可以从地域我们便可以从地域k k出发倒推飞机在各地域的飞行高出发倒推飞机在各地域的飞行高度度data3:data3:for j:=20 to 40 do data3k for j:=20 to 40 do data3k 计算满足计算满足mindatak,jmindatak,j的的j;j;for i:=k downto 2 do data3i-l for i:=k downto 2 do data3i-ldata2i,data3i;data2i,data3i;最后输出飞行计划：最后输出飞行计划：for i=

45、1 to k do for i=1 to k do 输出飞机在地域输出飞机在地域i i的飞行高度的飞行高度data3i;data3i;输出最小的总耗油量输出最小的总耗油量datak,data3k;datak,data3k;每输入一条航线信息，我们便使用上述方法规划该航线的飞行方每输入一条航线信息，我们便使用上述方法规划该航线的飞行方案，直至案，直至n n条航线规划完毕条航线规划完毕本讲稿第六十三页，共八十四页Uxuhul的表决 nUxuhul印第安人是世界上最古老的文明之一。在中美洲丛林中，大约从公元前3200年的黄金时代，Uxuhul文化繁荣了近千年。每年代表各阶层的高级牧师都会聚集在首都，

46、投票表决重要事情。每次严格限定表决三个议案，每个议案只有是/否的回答。三个议案在议论表决中同时决定，遵循下列形式：本讲稿第六十四页，共八十四页n所有牧师聚集在一大房间，房间中央有一张桌子。在桌子上放了三片石块，一面黑，一面白。每个石块代表一个议案，黑表示“否”，白表示“是”。最初所有的石块都是黑色的面朝上，表示所有的议案都是否定的结果。根据年龄，从年轻的到年长者，每位牧师通过翻动一块石块来表决，也就是改变某个议案的结果。不允许不表决。最年长的牧师做出选择后，石块朝上的颜色决定了三个议案的最终结果。本讲稿第六十五页，共八十四页nUxuhul的政治相当复杂，大量代表不同利益的游说（和行贿），影响三

47、个议案的八种结果。宗教规则强制每位牧师在投票表决前公开他们对三个议案的八种结果的表决倾向。由于彼此间都知道表决倾向，每位牧师都争取对自己最有利的结果，而且Uxuhul人具有高超的逻辑推理能力，对游戏规则又很了解，每个牧师都能找到最理想的方法！本讲稿第六十六页，共八十四页n最后，复杂刻板行政系统导致Uxuhul文明的崩溃。只留下他们的城市和庙宇，历史学家和考古学家试图通过研究每年议案的表决结果来弄清他们的历史。不管怎么说，只有牧师们的表决倾向留下来了，没有实际的表决结果。那么你的任务就是揭示出表决结果。本讲稿第六十七页，共八十四页输入n输入从一个整数n开始,1=n=100，代表表决的次数。后面跟

48、着n个问题。每次表决由一个整数m开始，1=m=100，表示牧师的数目。后面m行，按照顺序代表每位投票者的表决倾向。对于每种结果（NNN,NNY,NYN,NYY,YNN,YNY,YYN,YYY,N表示否，Y表示是）,给一个18之间的数，越小的数字表示选择可能性越大。对8种结果的表决倾向按照前面列举的顺序的给出。本讲稿第六十八页，共八十四页输出n对于每个问题，输出三个议案的表决结果。N表示否，Y表示是。本讲稿第六十九页，共八十四页输入样例2 48 7 6 5 4 3 2 18 6 3 1 2 4 5 78 3 6 5 1 2 7 41 2 3 4 5 6 7 811 2 3 4 5 6 7 8本讲

49、稿第七十页，共八十四页输出样例NYYNNY本讲稿第七十一页，共八十四页解题思路n这个题似乎可以采用贪心来做。每一个牧师都从可能的结果中选择对自己最有利的结果，最后的结果似乎就是人人都满意的结果？仔细分析就发现这种思路不正确。假如有两个人来选择，选择倾向是：2 1 7 4 5 8 3 63 8 6 4 5 1 2 7本讲稿第七十二页，共八十四页n如果按照贪心的思想去做，第一个人应该选择NNY,但第二个人肯定会选择成YNY，结果是第一个人最不满意的。n如果第一个人选择NYN，表面上是他不满意的选择（排在第七位的结果），但第二个人会选择YYN（这是他在这种情况下的最好选择，排在第二位）,而对于第一个

50、人来说，YYN也是一个不错的结果。本讲稿第七十三页，共八十四页n所以，贪心的思路不行。n在解决这个题之前，让我们先看看海盗的传说：本讲稿第七十四页，共八十四页n有5个海盗，多年的海上生活使他们积攒了100颗宝石。他们决定将宝石分掉之后就分手，洗手不干了。他们商量许久，最后决定：首先抽签，每个人抽得一个号码（1号到5号），然后1号海盗提出一个分配方案，所有海盗举手表决，如果过半数的海盗同意该分配方案，则按此方案分配，否则将1号海盗扔到大海。再由2号海盗提出他的分配方案，重复以上过程，直到找到分配方案止。海盗都是很聪明的，而且彼此知道别人的聪明，每个海盗都希望得到最多的宝石。如果你是1号海盗，你会