《第9章第1-2节动态规划基础(C++版).ppt》由会员分享，可在线阅读，更多相关《第9章第1-2节动态规划基础(C++版).ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第九章第九章 动态规划动态规划第一节第一节 动态规划的基本模型动态规划的基本模型第二节第二节 动态规划与递推动态规划与递推第三节第三节 背包问题背包问题第四节第四节 动态题动态题 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必
2、须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。第一节第一节 动态规划的基本模型动态规划的基本模型w多阶段决策过程的最优化问题多阶段决策过程的最优化问题 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，这种把一个问题看作是一
3、个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。如下图所示： 多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。【例【例1】最短路径问题。最短路径问题。下图给出了一个地图，地图中的每个顶点代表一个城市，两个城市间的一条连线代表道路，连线上的数值代表道路的长度。现在想从城市A到达城市E，怎样走路程最短？最短路程的长度是多少？【算法分析】【算法分析】 把A到E的全过程分成四个阶段，用K表示阶段变量，第1阶段有一个初始状态A，有两条可供选择的支路A-B1、A-B2；第
4、2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路。用DK（XI，X+1J）表示在第K阶段由初始状态XI到下阶段的初始状态X+1J的路径距离，FK（XI）表示从第K阶段的XI到终点E的最短距离，利用倒推的方法，求解A到E的最短距离。 具体计算过程如下：S1： K = 4 有 F4（D1）= 3， F4（D2）= 4， F4（D3）= 3；S2： K = 3 有 F3（C1）= MIN D3（C1，D1）+ F4（D1），D3（C1，D2）+ F4（D2） = MIN 5+3，6+4 = 8 F3（C2）= D3（C2，D1）+ F4（D1）= 5+3 = 8 F
5、3（C3）= D3（C3，D3）+ F4（D3）= 8+3 = 11 F3（C4）= D3（C4，D3）+ F4（D3）= 3+3 = 6S3： K = 2 有 F2（B1）= MIN D2（B1，C1）+ F3（C1），D2（B1，C2）+ F3（C2）， D2（B1，C3）+ F3(C3) = MIN 1+8,6+8,3+11 = 9 F2（B2）= MIN D2（B2，C2）+ F3（C2），D2（B2，C4）+ F3（C4） = MIN 8+8，4+6 = 10S4： K = 1 有 F1（A）= MIN D1（A，B1）+ F2（B1），D1（A，B2）+ F2（B2） = MIN
6、5+9，3+10 = 13 因此由A点到E点的全过程最短路径为AB2C4D3E；最短路程长度为13。 从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到终点E的最短距离，当逆序倒推到过程起点A时，便得到了全过程的最短路径和最短距离。 在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与阶段有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。w动态规划的基本概念和基本模型构成动态规划的基本概念和基本模型构成 现在我们来介绍动态规划的基本概念。1. 阶段和阶段变量
7、： 用动态规划求解一个问题时，需要将问题的全过程恰当地分成若干个相互联系的阶段，以便按一定的次序去求解。描述阶段的变量称为阶段变量，通常用K表示，阶段的划分一般是根据时间和空间的自然特征来划分，同时阶段的划分要便于把问题转化成多阶段决策过程，如例题1中，可将其划分成4个阶段，即K = 1，2，3，4。2. 状态和状态变量： 某一阶段的出发位置称为状态，通常一个阶段包含若干状态。一般地，状态可由变量来描述，用来描述状态的变量称为状态变量。如例题1中，C3是一个状态变量。3. 决策、决策变量和决策允许集合： 在对问题的处理中作出的每种选择性的行动就是决策。即从该阶段的每一个状态出发，通过一次选择性
8、的行动转移至下一阶段的相应状态。一个实际问题可能要有多次决策和多个决策点，在每一个阶段的每一个状态中都需要有一次决策，决策也可以用变量来描述，称这种变量为决策变量。在实际问题中，决策变量的取值往往限制在某一个范围之内，此范围称为允许决策集合。如例题1中，F3（C3）就是一个决策变量。4策略和最优策略： 所有阶段依次排列构成问题的全过程。全过程中各阶段决策变量所组成的有序总体称为策略。在实际问题中，从决策允许集合中找出最优效果的策略成为最优策略。5. 状态转移方程 前一阶段的终点就是后一阶段的起点，对前一阶段的状态作出某种决策，产生后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律
9、，称为状态转移方程。w最优化原理与无后效性最优化原理与无后效性 上面已经介绍了动态规划模型的基本组成，现在需要解决的问题是：什么样的“多阶段决策问题”才可以采用动态规划的方法求解。 一般来说，能够采用动态规划方法求解的问题，必须满足最优化原理和无后效性原则： 1、动态规划的最优化原理。作为整个过程的最优策略具有：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。也可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，而非最优解对问题的求解没有影响。在例题1最短路径问题中，
10、A到E的最优路径上的任一点到终点E的路径，也必然是该点到终点E的一条最优路径，即整体优化可以分解为若干个局部优化。 2、动态规划的无后效性原则。所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整的总结，此前的历史只能通过当前的状态去影响过程未来的演变。在例题1最短路径问题中，问题被划分成各个阶段之后，阶段K中的状态只能由阶段K+1中的状态通过状态转移方程得来，与其它状态没有关系，特别与未发生的状态没有关系，例如从Ci到E的最短路径，只与Ci的位置有关，它是由Di中的状态通过状态转
11、移方程得来，与E状态，特别是A到Ci的路径选择无关，这就是无后效性。 由此可见，对于不能划分阶段的问题，不能运用动态规划来解；对于能划分阶段，但不符合最优化原理的，也不能用动态规划来解；既能划分阶段，又符合最优化原理的，但不具备无后效性原则，还是不能用动态规划来解；误用动态规划程序设计方法求解会导致错误的结果。w动态规划设计方法的一般模式动态规划设计方法的一般模式 动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态；或倒过来，从结束状态开始，通过对中间阶段决策的选择，达到初始状态。这些决策形成一个决策序列，同时确定了完成整个过程的一条活动路线，
12、通常是求最优活动路线。动态规划的设计都有着一定的模式，一般要经历以下几个步骤：1、划分阶段 按照问题的时间或空间特征，把问题划分为若干个阶段。在划分阶段时，注意划分后的阶段一定是有序的或者是可排序的，否则问题就无法求解。2、确定状态和状态变量 将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。3、确定决策并写出状态转移方程 因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可以写出。但事实上常常是反过来做，根据相邻两段的各个状态之间的关系来确定决策。4、寻找边界条件 给出的
13、状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。【例1】对应的C+程序如下：#include#includeusing namespace std;int main() long d555,f1010; memset(d,42,sizeof(d); /有些路径是不通的,赋值为较大值，用于判断 d111=5;d112=3;d211=1; /以下给可通路径赋正常值 d212=6;d213=3;d222=8 d224=4;d311=5;d312=6; d321=5;d333=8;d343=3; d411=3;d421=4;d431=3; for (int i=0;i=9;+i) for
14、(int j=0;j=1;-i) for (int j=1;j=4;+j) for (int k=1;kdijk+fi+1k) /即使走非法路径，也不影响答案 fij=dijk+fi+1k; coutf11endl;第二节第二节 动态规划与递推动态规划与递推 动态规划是最优化算法动态规划是最优化算法 由于动态规划的“名气”如此之大，以至于很多人甚至一些资料书上都往往把一种与动态规划十分相似的算法，当作是动态规划。这种算法就是递推。实际上，这两种算法还是很容易区分的。 按解题的目标来分，信息学试题主要分四类：判定性问题、构造性问题、计数问题和最优化问题。我们在竞赛中碰到的大多是最优化问题，而动态
15、规划正是解决最优化问题的有力武器，因此动态规划在竞赛中的地位日益提高。而递推法在处理判定性问题和计数问题方面也是一把利器。下面分别就两个例子，谈一下递推法和动态规划在这两个方面的联系。【例例2】数塔问题（数塔问题（IOI94）有形如图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。 这道题如果用枚举法，在数塔层数稍大的情况下（如40），则需要列举出的路径条数将是一个非常庞大的数目。如果用贪心法又往往得不到最优解。在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值
16、还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。 一般说来，很多最优化问题都有着对应的计数问题；反过来，很多计数问题也有着对应的最优化问题。因此，我们在遇到这两类问题时，不妨多联系、多发展，举一反三，从比较中更深入地理解动态规划的思想。 其实递推和动态规划这两种方法的思想本来就很相似，也不必说是谁借用了谁的思想。关键在于我们要掌握这种思想，这样我们无论在用动态规划法解最优化问题，或是在用递推法解判
17、定型、计数问题时，都能得心应手、游刃有余了。【解法一】（逆推法）【解法一】（逆推法）【算法分析】【算法分析】 贪心法往往得不到最优解：本题若采用贪心法则：13-11-12-14-13，其和为63,但存在另一条路：13-8-26-15-24，其和为86。 贪心法问题所在：眼光短浅。 动态规划求解：动态规划求解问题的过程归纳为：自顶向下的分析，自底向上计算。 其基本方法是： 划分阶段：按三角形的行，划分阶段，若有n行，则有n-1个阶段。 A从根结点13出发，选取它的两个方向中的一条支路，当到倒数第二层时，每个结点其后继仅有两个结点，可以直接比较，选择最大值为前进方向，从而求得从根结点开始到底端的最
18、大路径。 B自底向上计算：（给出递推式和终止条件） 从底层开始，本身数即为最大数； 倒数第二层的计算，取决于底层的数据：12+6=18，13+14=27，24+15=39，24+8=32； 倒数第三层的计算，取决于底二层计算的数据：27+12=39，39+7=46，39+26=65 倒数第四层的计算，取决于底三层计算的数据：46+11=57，65+8=73 最后的路径：138261524 C数据结构及算法设计 图形转化：直角三角形，便于搜索：向下、向右 用三维数组表示数塔：ax,y,1表示行、列及结点本身数据,ax,y,2能够取得最大值,ax,y,3表示前进的方向0向下，1向右； 算法： 数组
19、初始化，输入每个结点值及初始的最大路径、前进方向为0； 从倒数第二层开始向上一层求最大路径，共循环N-1次； 从顶向下，输出路径：究竟向下还是向右取决于列的值，若列的值比原先多1则向右，否则向下。 参考程序参考程序#include#includeusing namespace std;int main()int n,x,y;int a51513;coutn;memset(a,0,sizeof(0);for (x=1;x=n;x+) /输入数塔的初始值输入数塔的初始值 for (y=1;yaxy1;axy2=axy1;axy3=0; /路径走向，默认向下路径走向，默认向下 for (x=n-1;
20、x=1;x-) for (y=1;yax+1y+12) /选择路径，保留最大路径值选择路径，保留最大路径值 axy2=axy2+ax+1y2; axy3=0; else axy2=axy2+ax+1y+12; axy3=1; coutmax=a112endl; /输出数塔最大值输出数塔最大值 y=1; for (x=1;x=n-1;x+) /输出数塔最大值的路径输出数塔最大值的路径 coutaxy1; y=y+axy3; /下一行的列数下一行的列数 coutany18-26-15-24【解法二】（顺推法）【解法二】（顺推法）【算法分析】【算法分析】 此题贪心法往往得不到最优解，例如13-11-
21、12-14-13其路径的值为63，但这不是最优解。 穷举搜索往往是不可能的，当层数N = 100时，路径条数P = 299这是一个非常大的数，即使用世界上最快的电子计算机，也不能在规定时间内计算出来。 对这道题唯一正确的方法是动态规划。如果得到一条由顶到底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶点至该中间点的路径所经过的数字和也为最大。因此本题是一个典型的多阶段决策最优化问题。在本题中仅要求输出最优解，为此我们设置了数组Ai,j保存三角形数塔，Bi,j保存状态值，按从上往下方式进行求解。 阶段i：以层数来划分阶段，由从上往下方式计算；因此可通过第一重循环: for (in
22、t i=1;i=n;i+) 枚举每一阶段； 状态Bij：由于每个阶段中有多个状态，因此可通过第二重循环: for (int j=1;j=i;j+)求出每个阶段的每个状态的最优解Bij； 决 策：每个状态最多由上一层的两个结点连接过来，因此不需要做循环。 【参考程序】【参考程序】#include#includeusing namespace std;int main()int n,i,j,a200200,b200200,maxx; cinn; memset(a,0,sizeof(a); memset(b,0,sizeof(b); for (i=1;i=n;+i)for (j=1;jaij; bi
23、j=aij; for (i=2;i=n;+i) /选择路径，保留最大路径值 for (j=1;jbi-1j) bij=bij+bi-1j-1; else bij=bij+bi-1j; maxx=0; for (j=1;jmaxx) /在第n行中找出数塔最大值 maxx=bnj; coutMax=maxxendl; /输出数塔最大值 【例【例3】求最长不下降序列】求最长不下降序列问题描述： 设有由n个不相同的整数组成的数列，记为:b(1)、b(2)、b(n)且b(i)b(j) (ij)，若存在i1i2i3 ie 且有b(i1)b(i2) b(ie)则称为长度为e的不下降序列。程序要求，当原数列出
24、之后，求出最长的不下降序列。 例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，19，21，22，63长度为8的不下降序列。算法分析： 根据动态规划的原理，由后往前进行搜索(当然从前往后也一样)。 1对b(n)来说，由于它是最后一个数，所以当从b(n)开始查找时，只存在长度为1的不下降序列； 2若从b(n-1)开始查找，则存在下面的两种可能性： 若b(n-1)b(n)则存在长度为1的不下降序列b(n-1)或b(n)。 3一般若从b(i)开始，此时最长不下降序
25、列应该按下列方法求出:在b(i+1),b(i+2),b(n)中，找出一个比b(i)大的且最长的不下降序列，作为它的后继。数据结构： 为算法上的需要，定义一个整数类型二维数组b(N,3) 1b(I,1)表示第I个数的数值本身； 2b(I,2)表示从I位置到达N的最长不下降序列长度 3b(I,3)表示从I位置开始最长不下降序列的下一个位置，若bI,3=0则表示后面没有连接项。 求解过程： 从倒数第二项开始计算，后面仅有1项，比较一次，因6315，不符合要求，长度仍为1。 从倒数第三项开始其后有2项，需做两次比较，得到目前最长的不下降序列为2，如下表：111213141112131422631521
26、22631521132111300121300 一般处理过程是： 在i+1,i+2,n项中，找出比bI,1大的最长长度L以及位置K; 若L0，则bI,2:=L+1;bI,3:=k; 最后本题经过计算，其数据存储表如下：123456789101112131413791638243718441921226315787634352432114348979101311121300初始化:for (i=1;ibi1; bi2=1;bi3=0;下面给出求最长不下降序列的算法:for (i=n-1;i=1;i-) l=0;k=0; for (j=i+1;jbi1)&(bj2l) l=bj2; k=j; if
27、 (l0) bi2=l+1; bi3=k; 下面找出最长不下降序列：k=1;for (j=1;jbk2) k=j;最长不下降序列长度为bk2序列while (k!=0) coutbk1; k=bk3;#includeusing namespace std;int main() int n,i,j,l,k,b20010; coutinput n:n; for (i=1;ibi1; bi2=1;bi3=0; 程序运行结果：输入：1413 7 9 16 38 24 37 18 44 19 21 22 63 15输出：max=87 9 16 18 19 21 22 63 for (i=n-1;i=1;
28、i-) /求最长不下降序列 l=0;k=0; for (j=i+1;jbi1)&(bj2l) l=bj2; k=j; if (l0) bi2=l+1;bi3=k; k=1; for (j=1;jbk2) k=j; coutmax=bk2endl; /输出结果 while (k!=0) /输出最长不下降序列 cout bk1; k=bk3; 【例例4】拦截导弹拦截导弹(Noip1999)某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每拦截系统有一个缺
29、陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，的正整数，导弹数不超过导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配
30、备多少套这种导弹拦截系统。弹最少要配备多少套这种导弹拦截系统。样例：样例：INPUT OUTPUT389 207 155 300 299 170 158 65 6（最多能拦截的导弹数）（最多能拦截的导弹数） 2（要拦截所有导弹最少要配备的系统数）（要拦截所有导弹最少要配备的系统数）【算法分析算法分析】 第一问即经典的最长不下降子序列问题，可以用一般的第一问即经典的最长不下降子序列问题，可以用一般的DP算法，也可以用高算法，也可以用高效算法，但这个题的数据规模不需要。效算法，但这个题的数据规模不需要。用用ax表示原序列中第表示原序列中第x个元素，个元素，bx表示长度为表示长度为x的不下降子序列的
31、长的不下降子序列的长度，。当处理第度，。当处理第ax时，可查找它可以连接到长度最大为多少的不下降子序列时，可查找它可以连接到长度最大为多少的不下降子序列后（即与部分后（即与部分bx比较）。假设可以连到长度最大比较）。假设可以连到长度最大为为maxx的的不下降子序列后，不下降子序列后，则则bx:=maxx+1。b数组被赋值的最大值就是第一问的答案。数组被赋值的最大值就是第一问的答案。第二问用贪心法即可。每颗导弹来袭时，使用能拦截这颗导弹的防御系统第二问用贪心法即可。每颗导弹来袭时，使用能拦截这颗导弹的防御系统中上一次拦截导弹高度最低的那一套来拦截。若不存在符合这一条件的系统，中上一次拦截导弹高度
32、最低的那一套来拦截。若不存在符合这一条件的系统，则使用一套新系统。则使用一套新系统。【参考程序参考程序】（顺推法）（顺推法）#include#include#includeusing namespace std;int main() freopen(in.txt, r, stdin); freopen(out.txt, w, stdout); int i,j,k,x,n,maxx,m,a10000,b10000,h10000; i=1;n=0;m=0; memset(a,0,sizeof(a); memset(b,0,sizeof(b); memset(h,0,sizeof(h); while
33、 (cinai) maxx=0; for (j=1;j=ai) if (bjmaxx) maxx=bj; bi=maxx+1; if (bim) m=bi; x=0; for (k=1;k=ai) if (x=0) x=k; else if (hkhx) x=k; /如果有多套系统可拦截，则选择上一次拦截高度最低的 if (x=0) n+;x=n; /新增一套导弹拦截系统 hx=ai; i+; coutmendlnE。试用动态规划的最优化原理求出A-E的最省费用。交通图1 交通图2 如图：求v1到v10的最短路径长度及最短路径。【样例输入】short.in100 2 5 1 0 0 0 0 0
34、 00 0 0 0 12 14 0 0 0 00 0 0 0 6 10 4 0 0 00 0 0 0 13 12 11 0 0 00 0 0 0 0 0 0 3 9 00 0 0 0 0 0 0 6 5 00 0 0 0 0 0 0 0 10 00 0 0 0 0 0 0 0 0 50 0 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0【样例输出】short.outminlong=191 3 5 8 10【算法分析】逆推法 设fi表示点i到v10的最短路径长度，则 f10=0 fi=min aix+fx 当aix0 ,ix=n时#includeusing namespac
35、e std;#include#includeint main() long n,i,j,x,f100,c100,a100100; memset(a,0,sizeof(a); memset(c,0,sizeof(c); cinn; for (i=1;i=n;i+) /输入各个城市之间距离输入各个城市之间距离 for (j=1;jaij; for (i=1;i=1;i-) /从终点往前逆推，计算最短路径从终点往前逆推，计算最短路径 for (x=i+1;x0)&(fx!=1000000)&(fiaix+fx) /aix0表示城市表示城市i和城市和城市x通路通路 fi=aix+fx; /城市城市i到
36、终点最短路径的值到终点最短路径的值 ci=x; coutminlong=f1endl; /输出最短路径的值输出最短路径的值 x=1;wwhile (x!=0) /输出路过的各个城市输出路过的各个城市w w coutx ;w x=cx;w w coutendl; ww【例6】挖地雷w【问题描述】w在一个地图上有N个地窖（N=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，
37、使他能挖到最多的地雷。w【输入格式】w N /地窖的个数w W1，W2，WN /每个地窖中的地雷数w X1，Y1 /表示从X1可到Y1w X2，Y2w w 0，0 /表示输入结束w【输出格式】w K1-K2-Kv /挖地雷的顺序w MAX /最多挖出的地雷数w【输入样例】Mine.inw 6w 5 10 20 5 4 5w 1 2w 1 4w 2 4w 3 4w 4 5w w 4 6w 5 6w 0 0w【输出样例】Mine.outw 3-4-5-6w 34w【算法分析】w本题是一个经典的动态规划问题。很明显，题目规定所有路径都是单向的，所以满足无后效性原则和最优化原理。设Wi为第i个地窖所藏
38、有的地雷数，Aij表示第i个地窖与第j个地窖之间是否有通路，Fi为从第i个地窖开始最多可以挖出的地雷数，则有如下递归式：wFi=max Wi+ Fj (ij=n , Aij=true)w边界：Fn=Wnw于是就可以通过递推的方法，从后F(n)往前逐个找出所有的Fi，再从中找一个最大的即为问题2的解。对于具体所走的路径（问题1），可以通过一个向后的链接来实现。w【参考程序】w#includew#includewusing namespace std;wint main()ww long f201=0,w201,c201=0;w bool a201201=0;w long i,j,n,x,y,l,
39、k,maxx;w memset(f,0,sizeof(f);w wmemset(c,0,sizeof(c);w memset(a,false,sizeof(a);w cinn;w for (i=1;iwi; /输入每个地窖中的地雷数w dow w cinxy; /表示从X可到Yw if (x!=0)&(y!=0) axy=true;w while (x!=0)|(y!=0);w fn=wn; /从后Fn往前逐个找出所有的Fiw for (i=n-1;i=1;i-)w w l=0;k=0;w for (j=i+1;jl)w l=fj; k=j; w fi=l+wi; /保存从第i个地窖起能挖到最
40、大地雷数w ci=k; /k地窖是i地窖最优路径w w k=1;w for (j=2;jfk) k=j;w maxx=fk;w coutk;w k=ck;w while (k!=0) /输出挖地雷的顺序w w cout-k;w k=ck;w w coutendl;w coutmaxxendl; /输出最多挖出的地雷数w【例【例7】友好城市友好城市 【问题描述】【问题描述】 Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。 每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但
41、是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。【输入格式】【输入格式】 第1行，一个整数N(1=N=5000)，表示城市数。 第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。(0=xi=10000)【输出格式】【输出格式】 仅一行，输出一个整数，表示政府所能批准的最多申请数。【输入样例】【输入样例】 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2【输出样例】【算法分析】 我们将每对友好城市看成一条线段，则这道题的
42、描述化为：有N条线段，问最少去掉多少条线，可以使剩下的线段互不交叉？第一，以北岸为线的起点而南岸为线的终点；先将所有的线按照起点坐标值从小到大排序，按照每条线的终点坐标计算交叉数：求线I的交叉数AI，则检查所有1.I-1条线，若线J( 1= J I)的终点值大于线I的终点值，则线I与线J相交。AI与AJ同时加1。整个搜索量最大为5000*5000。第二，将A数组从大到小排序，每删除一条线，则将与之相交的线的A值减1，重复这个过程，直到所有A值都为0。此时剩下的线则全不交叉。 4如上数据，则可得下面结果：编号 南岸 北岸 交叉数11322242331244515523 此时，1、2、3航线的交叉
43、数都一样，如果删去的是3、5线，则剩下的1、2、4线互不相交，最多航线数为3；但如果删去的是2、3，则还要删去第5线才符合要求，此时的最多航线数为2，不是最优解。 于是，我们从上面的分析中再深入，将航线按起点坐标排好序后，如上所述，在本题中，只要线J的起点小于线I的起点，同时它的终点也小于线I的终点，则线J和线I不相交。因此，求所有线中最多能有多少条线不相交，实际上是从终点坐标值数列中求一个最长不下降序列。这就把题目转化为一个非常典型的动态规划题目了。 求最长不下降序列的规划方程如下： L(Si)=maxL(Sj)+1；1 = j i且 Sj Si。Si为航线的终点坐标值。从以上分析过程可以得
44、出：当我们拿到一道题时，不要急于求解，而应先将题目的表面现象一层层象剥竹笋一样去掉，只留下最实质的内容。这时再来设计算法，往往能事半功倍。【例8】合唱队形【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, , K，他们的身高分别为T1, T2, , TK，则他们的身高满足T1 T2 Ti+1 TK (1iK)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【输入文件】输入文件chorus.in的第一行是一个整数N（2 N 100）
45、，表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti（130 Ti 230）是第i位同学的身高（厘米）。【输出文件】输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。【样例输入】8186 186 150 200 160 130 197 220【样例输出】4【数据规模】对于50%的数据，保证有n 20；对于全部的数据，保证有n100。【算法分析】我们按照由左而右和由右而左的顺序，将n个同学的身高排成数列。如何分别在这两个数列中寻求递增的、未必连续的最长子序列，就成为问题的关键。设a 为身高序列，其中ai为同学i的身高；b 为由左而右身高递增的人数序列
46、，其中 bi为同学1同学i间（包括同学i）身高满足递增顺序的最多人数。显然bi=bj|同学j的身高同学i的身高+1；c为由右而左身高递增的人数序列，其中ci为同学n同学i间（包括同学i）身高满足递增顺序的最多人数。显然ci=cj|同学j的身高同学i的身高+1；由上述状态转移方程可知，计算合唱队形的问题具备了最优子结构性质(要使bi和ci最大，子问题的解bj和ck必须最大(1ji-1 ，i+1kn)和重迭子问题的性质(为求得bi和ci，必须一一查阅子问题的解b1bi-1和ci+1cn)，因此可采用动态程序设计的方法求解。显然，合唱队的人数为(公式中同学i被重复计算，因此减1)，n减去合唱队人数即
47、为解。具体算法如下：#include#includeusing namespace std;int a200,b200,c200;main() int n,i,j,maxx; cinn; /读学生数 memset(b,0,sizeof(b); /身高满足递增顺序的两个队列初始化 memset(c,0,sizeof(c); for (i=1;iai; for (i=1;i=n;i+) /按照由左而右的顺序计算b序列 bi=1; for (j=1;jaj)&(bj+1bi) bi=bj+1; wfor (i=n;i=1;i-) /按照由右而左的顺序计算c序列w w ci=1;w for (j=i+
48、1;j=n;j+)w if (ajci)w ci=cj+1;w w maxx=0; /计算合唱队的人数max（其中1人被重复计算w for (i=1;imaxx)w maxx=bi+ci;w coutn-maxx+1endl; /输出出列人数ww这个算法的时间复杂度为O(n2)，在1秒时限内可解决n100范围内的问题。【例【例9】机器分配】机器分配【问题描述】【问题描述】总公司拥有高效设备总公司拥有高效设备M台，准备分给下属的台，准备分给下属的N个分公司。各分公司若获得个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这这些设备，可以为国家提供一定的盈利。问：如何分配这M
49、台设备才能使国家台设备才能使国家得到的盈利最大？求出最大盈利值。其中得到的盈利最大？求出最大盈利值。其中M15，N10。分配原则：每个公司。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数有权获得任意数目的设备，但总台数不超过设备数M。输入数据文件格式为：第一行有两个数，第一个数是分公司数输入数据文件格式为：第一行有两个数，第一个数是分公司数N，第二个，第二个数是设备台数数是设备台数M。接下来是一个接下来是一个N*M的矩阵，表明了第的矩阵，表明了第 I个公司分配个公司分配 J台机器的盈利。台机器的盈利。【输入样例】【输入样例】assigned.in3 3 /3个分公司分个分公司分
50、3台机器台机器30 40 5020 30 5020 25 30【输出样例】【输出样例】assigned.out70 /最大盈利值为最大盈利值为701 1 /第一分公司分第一分公司分1台台2 1 /第二分公司分第二分公司分1台台3 1 /第三分公司分第三分公司分1台台【算法分析算法分析】按照公司的顺序来分配机器，即按照公司的顺序划分阶段，第一个阶段把按照公司的顺序来分配机器，即按照公司的顺序划分阶段，第一个阶段把M台设备分给台设备分给第一个公司，记录下来获得的各个盈利值，然后把第一个公司，记录下来获得的各个盈利值，然后把M台设备分给前两个公司，和第一个阶段台设备分给前两个公司，和第一个阶段比较记