基本的算法策略.ppt

《基本的算法策略.ppt》由会员分享，可在线阅读，更多相关《基本的算法策略.ppt（117页珍藏版）》请在三一办公上搜索。

1、第 四 章 基本的算法策略,贪婪法又叫登山法,它的根本思想是逐步到达山顶,即逐步获得最优解。贪婪算法没有固定的算法框架，算法设计的关键是贪婪策略的选择。一定要注意，选择的贪婪策略要具有无后向性。某状态以后的过程和不会影响以前的状态,只与当前状态或以前的状态有关,称这种特性为无后效性。上节 下节,4.4 贪婪算法,【例1】键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输入数据均不需判错。输出应包括所去掉的数字的位置和组成的新的正整数（N不超过240位）。数据结构设计：对高精度正整数的运

2、算在上一节我们刚刚接触过，和那里一样，将输入的高精度数存储为字符串格式。根据输出要求设置数组，在删除数字时记录其位置。上节 下节,4.4.1 可绝对贪婪问题,问题分析 在位数固定的前提下，让高位的数字尽量小其值就较小，依据此贪婪策略就可以解决这个问题。怎么样根据贪婪策略删除数字呢？总目标是删除高位较大的数字，具体地相邻两位比较若高位比低位大则删除高位。我们通过“枚举归纳”设计算法的细节，看一个实例（s=3）：n1=“1 2 4 3 5 8 6 3”4比3大 删除“1 2 3 5 8 6 3”8比6大 删除“1 2 3 5 6 3”6比3大 删除“1 2 3 5 3”只看这个实例，有可能“归纳”

3、出不正确的算法，先看下一个实例，我们再进一步解释：n2=”2 3 1 1 8 3”3比1大 删除“2 1 1 8 3”2比1大 删除“1 1 8 3”8比3大 删除“1 1 3”,由实例n1，相邻数字只需要从前向后比较；而从实例n2中可以看出当第i位与第i+1位比较，若删除第i位后，必须向前考虑第i-1位与第i+1位进行比较，才能保证结果的正确性。由此可知通过实例设计算法时，枚举的实例一定要有全面性，实例最好要能代表所有可能的情况，或者在必要时多列举几个不同的实例。再看以下两个实例又可总结出一些需要算法特殊处理的情况。n3=”1 2 3 4 5 6 7”s=3 由这个实例看出，经过对n3相邻比

4、较一个数字都没有删除，这就要考虑将后三位进行删除，当然还有可能，在相邻比较的过程中删除的位数小于s时，也要进行相似的操作。n4=”1 2 0 0 8 3”3比0大 删除“1 0 0 8 3”2比0大 删除“0 0 8 3”8比3大 删除“0 0 3”得到的新数数据是3,由这个实例子又能看出，当删除掉一些数字后，结果的高位有可能出现数字“0”，直接输出这个数据不合理，要将结果中高位的数字“0”全部删除掉，再输出。特别地还要考虑若结果串是“0000”时，不能将全部“0”都删除，而要保留一个“0”最后输出。由此可以看出进行算法设计时，从具体到抽象的归纳一定要选取大量不同的实例，充分了解和体会解决问题

5、的过程、规律和各种不同情况，才能设计出正确的算法。算法设计1：根据以上实例分析，算法主要由四部分组成：初始化、相邻数字比较（必要时删除）、处理比较过程中删除不够s位的情况和结果输出。其中删除字符的实现方法很多，如：,1）物理进行字符删除，就是用后面的字符覆盖已删除的字符，字符串长度改变。这样可能会有比较多字符移动操作，算法效率不高。1）可以利用数组记录字符的存在状态，元素值为“1”表示对应数字存在，元素值为“0”表示对应数字已删除。这样避免了字符的移动，字符串长度不会改变，可以省略专门记录删除数字的位置。但这样做前后数字的比较过程和最后的输出过程相对复杂一些。2）同样还是利用数组，记录未删除字

6、符的下标，粗略的过程如下：n=“1 2 4 3 5 8 3 3”0 0 0 0 0 0 4比3大 删除“1 2 3 5 8 3 3”1 2 4 5 0 0 8比3大 删除“1 2 3 5 3 3”1 2 4 5 0 5比3大 删除“1 2 3 3 3”1 2 4 7 8这时数组好象是数据库中的索引文件。此方式同样存在操作比较复杂的问题。,我们采用方法1）。一种简单的控制相邻数字比较的方法是每次从头开始，最多删除s次，也就从头比较s次。按题目要求设置数组data记录删除的数字所在位置delete(char n,int b,int k)int i;for(i=b;ilen)print(“data

7、error”);return;,j1=0;for(i=0;inj+1)/贪婪选择 delete(n,j,1);if(jj1)datai=j+i;/记录删除数字位置 else/实例2向前删除的情况实例 datai=datai-1-1;j1=j;break;if(jlength(n)break;for(i=i;i=s;i=i+1)j=len-i+1;delete(n,j,1);datai=j;,while(n1=0 and length(n)1)delete(n,1,1);/将字符串首的若干个“0”去掉 print(n);for(i=1;i=s;i=i+1)print(datai,);算法说明1：

8、注意记录删除位置不一定是要删除数字d的下标，因为有可能d的前或后有可能已经有字符被删除，d的前面已经有元素删除容易想到，但一定不要忽略了其后也有可能已删除了字符，实例2中删除1时，其后的2已被删除。要想使记录删除的位置操作简便，使用算法设计1中的介绍第二种删除方式最简单，请读者尝试实现这个设计。,算法设计2：删除字符的方式同算法1，只是删除字符后不再从头开始比较，而是向前退一位进行比较，这样设计的算法2的效率较算法1要高一些。delete()函数同前不再重复。算法2如下：Delete_digit（）char n100;int s,i,j,c,data100,len;input(n);input

9、(s);len=length(n);if(slen)print(“data error”);return;i=0;j=1;j1=0;while(ij1)datai=j+i;else datai=datai-1-1;i=i+1;j1=j;j=j-1;,for(i=i;i1)delete(n,1,1);print(n);for(i=1;i=s;i=i+1)print(datai,);算法说明2：同算法1一样，变量i控制删除字符的个数，变量j控制相邻比较操作的下标，当删除了第j个字符后，j赋值为j-1，以保证实例2（字符串n2）出现的情况得到正确的处理。,【例2】数列极差问题 在黑板上写了N个正整数

10、作成的一个数列，进行如下操作:每一次擦去其中的两个数a和b，然后在数列中加入一个数ab+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的记作max，最小的记作min，则该数列的极差定义为M=max-min。问题分析 算法设计 数据结构设计 算法分析 上节 下节,问题分析 和上一个例题一样，我们通过实例来认识题目中描述的计算过程。对三个具体的数据3，5，7讨论，可能有以下三种结果：（3*5+1）*7+1=113、（3*7+1）*5+1=111、（5*7+1）*3+1=109 由此可见，先运算小数据得到的是最大值，先运算大数据得到的是最小值。上节 下节,下面再以三个数为

11、例证明此题用贪心策略求解的合理性,不妨假设：a0，则有以下几种组合计算结果：1)(a*b+1)*c+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+k2+12)(a*c+1)*b+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+13)(b*c+1)*a+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+1 显然此问题适合用贪婪策略,不过在求最大值时，要先选择较小的数操作。反过来求最小值时，要先选择较大的数操作。这是一道两次运用贪心策略解决的问题。上节 下节,算法设计 1）由以上分析，大家可以发现这个问题的解决方法

12、和哈夫曼树的构造过程相似，不断从现有的数据中，选取最大和最小的两个数，计算后的结果继续参与运算，直到剩余一个数算法结束。2)选取最大和最小的两个数较高效的算法是用二分法完成，这里仅仅用简单的逐个比较的方法来求解。注意到由于找到的两个数将不再参与其后的运算，其中一个自然地是用它们的计算结果代替，另一个我们用当前的最后一个数据覆盖即可。所以不但要选取最大和最小，还必须记录它们的位置，以便将其覆盖。3）求max、min的过程必须独立，也就是说求max和min都必须从原始数据开始,否则不能找到真正的max和min。上节 下节,数据结构设计 1)由设计2）、3）知，必须用两个数组同时存储初始数据。2)求

13、最大和最小的两个数的函数至少要返回两个数据，为方便起见我们用全局变量实现。int s1,s2;main（）int j,n,a100,b100,max,min;print(“How mang data?”);input(n);print(“input these data”);for(j=1;j=n;j=j+1)input(aj);bj=aj;min=calculatemin(a,n);max=calculatemax(b,n);print(“max-min=”,max-min),calculatemin(int a,int n)int j;while(n2)max2(a,n);as1=as1*

14、as2+1;as2=an;n=n-1;return(a1*a2+1);max2(int a,int n)int j;if(a1=a2)s1=1;s2=2;else s1=2;s2=1;for(j=3;jas1)s2=s1;s1=j;else if(ajas2)s2=j;上节 下节,calculatemax(int a,int n)int j;while(n2)min2(a,n);as1=as1*as2+1;as2=an;n=n-1;return(a1*a2+1);min2(int a,int n)int j;if(a1=a2)s1=1;s2=2;else s1=2;s2=1;for(j=3;j

15、=n;j+)if(ajas1)s2=s1;s1=j;else if(ajas2)s2=j;上节 下节,算法分析 算法中的主要操作就是比较查找和计算，它们都是线性的，因此算法的时间复杂度为O(n)。由于计算最大结果和计算最小结果需要独立进行,所以算法的空间复杂度为O(2n)。贪婪策略不仅仅可以应用于最优化问题中，有时在解决构造类问题时，用这种策略可以尽快地构造出一组解，如下面的例子：上节 下节,【例3】:设计一个算法，把一个真分数表示为埃及分数之和的形式。所谓埃及分数，是指分子为1的形式。如：7/8=1/2+1/3+1/24。问题分析 数学模型 算法设计 算法 上节 下节,问题分析 基本思想是，

16、逐步选择分数所包含的最大埃及分数，这些埃及分数之和就是问题的一个解。如：7/81/2，7/8-1/21/3，7/8-1/2-1/3=1/24。过程如下：1)找最小的n（也就是最大的埃及分数），使分数f1/n；2)输出1/n；3)计算f=f-1/n；4)若此时的f是埃及分数，输出f,算法结束,否则返回1）。上节 下节,数学模型 记真分数F=A/B；对B/A进行整除运算,商为D,余数为0KA，它们之间的关系及导出关系如下：B=A*D+K，B/A=D+K/AD+1，A/B1/(D+1)，记C=D+1。这样我们就找到了分数F所包含的“最大的”埃及分数就是1/C。进一步计算：A/B-1/C=（A*C-B

17、）/B*C 也就是说继续要解决的是有关分子为A=A*C-B,分母为B=B*C的问题。上节 下节,算法设计 由以上数学模型，真正的算法过程如下：1)设某个真分数的分子为A(1），分母为B；2)把B除以A的商的整数部分加1后的值作为埃及 分数的一个分母C;3)输出1/C；4)将A乘以C减去B作为新的A；5)将B乘以C作为新的B；6)如果A大于1且能整除B,则最后一个分母为B/A；7)如果A1,则最后一个分母为B;否则转步骤(2).上节 下节,例：7/8=1/2+1/3+1/24的解题步骤：同样用变量A表示分子，变量B表示分母；C=8+1=2/说明7/81/2，打印1/2 A=7*2-8=6，B=B

18、*C=16/在计算7/8-1/2=(7*2-8)/(7*2)=6/16=A/B C=16/6+1=3/说明16/61/3，打印1/3 A=6*3-16=2，B=B*C=16*3=48/在计算6/16-1/3=(6*3-16)/(16*3)=2/48=A/B A1但B/A为整数24，打印1/24 结束.上节 下节,算法,main（）int a,b,c;print(“input element”);input(a);print(“input denominator”);input(b);if(ab)print(“input error”);else if(a=1 or b mod a=0)prin

19、t(a,/,b,=1,/,b/a);else 上节 下节,while(a1)c=b a+1 a=a*c-b:b=b*c print(1/,c);if(b mod a=0)print(+1/;b/a);a=1;if(a 1)print(+);,【例4】币种统计问题【例5】取数游戏 上节 下节,4.4.2 相对或近似贪婪问题,4.4.1节的三个例子对于输入的任何数据，贪婪策略都是适用的，因此我们称它们为“可绝对贪婪问题”。看下一节的例子就明白，有的问题就不一定如此了。,【例4】币种统计问题 某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱,且取款的张数最少，取工资前要统计出所有职工的工

20、资所需各种币值(100,50,20,10,5,2,1元共七种)的张数。请编程完成。算法设计 算法说明 算法分析 贪婪策略 上节 下节,算法设计 1)从键盘输入每人的工资。2)对每一个人的工资，用“贪婪”的思想，先尽量多地取大面额的币种，由大面额到小面额币种逐渐统计。3)利用数组应用技巧,将七种币值存储在数组B。这样，七种 币值就可表示为Bi,i=1,2,3,4,5,6,7。为了能实现贪婪策略，七种币应该从大面额的币种到小面额的币种依次存储。4)利用数组技巧,设置一个有7个元素的累加器数组S。上节 下节,算法,main()int i,j,n,GZ,A；int B8=0,100,50,20,10,

21、5,2,1,S8;input(n);for(i=1;i=n;i+)input(GZ);for(j=1,j=7;j+)A=GZ/Bj;Sj=Sj+A;GZ=GZ-A*Bj;for(i=1;i=7;i+)print(Bi,“-”,Si);上节 下节,算法说明 每求出一种面额所需的张数后，一定要把这部分金额减去：“GZ=GZ-A*Bj;”,否则将会重复计算。算法分析 算法的时间复杂性是O（n）。上节 下节,解决问题的贪婪策略：以上问题的背景是在我国,题目中不提示我们也知道有哪些币种,且这样的币种正好适合使用贪婪算法(感兴趣的读者可以证明这个结论)。假若,某国的币种是这样的,共9种:100,70,50

22、,20,10,7,5,2,1。在这样的币值种类下,再用贪婪算法就行不通了,比如某人工资是140,按贪婪算法140=100*(1张)+20*(2张)共需要3张,而事实上,只要取2张70面额的是最佳结果,这类问题可以考虑用动态规划算法来解决。由此，在用贪婪算法策略时，最好能用数学方法证明每一步的策略是否能保证得到最优解。上节 下节,【例5】取数游戏 有2个人轮流取2n个数中的n个数，取数之和大者为胜。请编写算法，让先取数者胜，模拟取数过程。问题分析 算法设计 算法说明 算法分析 上节 下节,问题分析 这个游戏一般假设取数者只能看到2n个数中两边的数,用贪婪算法的情况:若一组数据为：6,16,27,

23、6,12,9,2,11,6,5。用贪婪策略每次两人都取两边的数中较大的一个数,先取者胜.以A先取为例：取数结果为：A 6,27,12,5,11=61 胜 B 16,6,9,6,2=39 上节 下节,但若选另一组数据：16,27,7,12,9,2,11,6。仍都用贪婪算法，先取者A败。取数结果为：A 16,7,9,11=43 B 27,12,6,2=47 胜 其实，若我们只能看到两边的数据，则此题无论先取还是后取都无必胜的策略。这时一般的策略是用近似贪婪算法。但若取数者能看到全部2n个数，则此问题可有一些简单的方法，有的虽不能保证所取数的和是最大，但确是一个先取者必胜的策略。上节 下节,数学模型

24、建立：N个数排成一行，我们给这N个数从左到右编号，依次为1，2，N，因为N为偶数，又因为是我们先取数，计算机后取数，所以一开始我们既可以取到一个奇编号的数（最左边编号为1的数）又可以取到一个偶编号的数（最右边编号为N的数）。如果我们第一次取奇编号（编号为1）的数，则接着计算机只能取到偶编号（编号为2或N）的数；如果我们第一次取偶编号（编号为N）的数，则接着计算机只能取到奇编号（编号为1或N-1）的数；即无论我们第一次是取奇编号的数还是取偶编号的数，接着计算机只能取到另一种编号（偶编号或奇编号）的数。,这是对第一个回合的分析，显然对以后整个取数过程都适用。也就是说，我们能够控制让计算机自始自终只

25、取一种编号的数。这样，我们只要比较奇编号数之和与偶编号数之和谁大，以决定最开始我们是取奇编号数还是偶编号数即可。（如果奇编号数之和与偶编号数之和同样大，我们第一次可以任意取数，因为当两者所取数和相同时，先取者为胜。,算法设计：有了以上建立的高效数学模型，算法就很简单了，算法只需要分别计算一组数的奇数位和偶数位的数据之和，然后就先了取数者就可以确定必胜的取数方式了。以下面一排数为例：1 2 3 10 5 6 7 8 9 4奇编号数之和为25（=1+3+5+7+9），小于偶编号数之和为30（=2+10+6+8+4）。我们第一次取4，以后，计算机取哪边的数我们就取哪边的数（如果计算机取1，我们就取2

26、；如果计算机取9，我们就取8）。这样可以保证我们自始自终取到偶编号的数，而计算机自始自终取到奇编号的数。,main()int i,s1,s2,data;input(n);s1=0；s2=0;for(i=1;is2)print(“first take left”);else print(“first take right”);这个例题又一次说明，解决问题时数学模型的选择是非常重要的。,1.贪心法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策,尽可能地求得最好的解。当达到某算法中的某一步不需要再继续前进时，算法停止。上节 下节,4.4.3 关于贪婪策略讨论,2

27、.该算法适用的问题：贪婪算法对问题只需考虑当前局部信息就要做出决策，也就是说使用贪婪算法的前提是“局部最优策略能导致产生全局最优解”。该算法的适用范围较小,若应用不当,不能保证求得问题的最佳解。一般情况下通过一些实际的数据例子(当然要有一定的普遍性),就能从直观上就能判断一个问题是否可以用贪婪算法，如本节的例2。更准确的方法是通过数学方法证明问题对贪婪策略的选用性。上节 下节,3.该策略下的算法框架：从问题的某一初始解出发；while能朝给定总目标前进一步do;利用可行的决策，求出可行解的一个解元素;由所有解元素组合成问题的一个可行解。上节 下节,4.贪婪策略选择:首先贪婪算法的原理是通过局部

28、最优来达到全局最优,采用的是逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的（在一定的标准下），决策一旦作出，就不可再更改。用贪婪算法只能解决通过局部最优的策略能达到全局最优的问题。因此一定要注意判断问题是否适合采用贪婪算法策略，找到的解是否一定是问题的最优解。上节 下节,在动态规划算法策略中，体现在它的决策不是线性的而是全面考虑不同的情况分别进行决策,并通过多阶段决策来最终解决问题。在各个阶段采取决策后,会不断决策出新的数据,直到找到最优解.每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义。所以，这种多阶段决策最优化的解决问题

29、的过程称为动态规划。上节 下节,4.5 动态规划,我们通过一个简单的例子来说明动态规划的多阶段决策与贪婪算法有什么区别。【例1】数塔问题 上节 下节,4.5.1 认识动态规划,【例1】数塔问题 有形如图4-11所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。,问题分析算法设计算法小结,问题分析 这个问题用贪婪算法有可能会找不到真正的最大和。以图4-11为例就是如此。用贪婪的策略，则路径和分别为：9+15+8+9+10=51（自上而下），19+2+10+12+9=52（自下而上）。都得不到最优解，真正的最大和是：9+12+10

30、+18+10=59。在知道数塔的全貌的前提下，可以用枚举法或下一章将学习的搜索算法来完成。上节 下节,算法设计 动态规划设计过程如下：1.阶段划分：第一步对于第五层的数据，我们做如下五次决策：对经过第四层2的路径选择第五层的19，对经过第四层18的路径选择第五层的10，对经过第四层9的路径也选择第五层的10，对经过第四层5的路径选择第五层的16。上节 下节,以上的决策结果将五阶数塔问题变为4阶子问题，递推出第四层与第五层的和为:21(2+19),28(18+10),19(9+10),21(5+16)。用同样的方法还可以将4阶数塔问题,变为3阶数塔问题。最后得到的1阶数塔问题，就是整个问题的最优

31、解。上节 下节,2存储、求解：1)原始信息存储 原始信息有层数和数塔中的数据，层数用一个整型 变量n存储，数塔中的数据用二维数组data，存储成如 下的下三角阵:9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 上节 下节,2)动态规划过程存储 必需用二维数组a存储各阶段的决策结果。二维数组a的存储内容如下：dnj=datanj j=1,2,n；i=n-1,n-2,1，j=1,2,i；时 dij=max(di+1j，di+1j+1)+dataij 最后a11存储的就是问题的结果。上节 下节,3)最优解路径求解及存储 仅有数组data和数组a可以找到最优解的路径，但需要自

32、顶向下比较数组data和数组a是可以找到。如图4.5.2求解和输出过程如下：上节 下节,输出a119 b=d11-data11=59-9=50 b与d21,d22 比较 b与d21相等输出data2112 b=d21-data21=50-12=38 b与d31,d32 比较 b与d31相等输出data3110 b=a31-data31=38-10=28 b与d41,d42 比较 b与d42相等输出data4218 b=d42-data42=28-18=10 b与d52,d53 比较 b与d53相等输出data5310“上节 下节,数组data 数组d 9 59 12 15 50 49 10 6

33、 8 38 34 29 2 18 9 5 21 28 19 21 19 7 10 4 16 19 7 10 4 16 图4-12 数塔及动态规划过程数据 上节 下节,为了设计简洁的算法，我们最后用三维数组a50503存储以上确定的三个数组的信息。a50501代替数组data，a50502代替数组d,a50503记录解路径。上节 下节,数塔问题的算法,main()int a50503,i,j,n;print(please input the number of rows:);input(n);for(i=1;i=n;i+)for j=1 to i do input(aij1);aij2=aij1

34、;aij3=0;上节 下节,for(i=n-1;i=1;i-)for(j=1;j=i;j+)if(ai+1j2ai+1j+12)aij2=aij2+ai+1j2;aij3=0;else aij2=aij2+ai+1j+12;aij3=1;print(max=,a112);j=1;for(i=1;i);j=j+aij3;print(anj1);上节 下节,从例子中可以看到：动态规划=贪婪策略+递推(降阶)+存储递推结果 贪婪策略、递推算法都是在“线性”地解决问题，而动态规划则是全面分阶段地解决问题。可以通俗地说动态规划是“带决策的多阶段、多方位的递推算法”。上节 下节,1.适合动态规划的问题特征

35、 动态规划算法的问题及决策应该具有三个性质：最优 化原理、无后向性、子问题重叠性质。1)最优化原理(或称为最佳原则、最优子结构)。2)无后向性(无后效性)。3)有重叠子问题。上节 下节,算法框架,2.动态规划的基本思想 动态规划方法的基本思想是，把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。最后一个子问题就是初始问题的解。由于动态规划的问题有重叠子问题的特点，为了减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。上节 下节,3.设计动态规划算法的基本步骤 设计一个标准的动态规划算法的步骤：1)划分阶段 2)选择状态 3)确定决策并写出状态转移方程

36、 但是,实际应用当中的简化步骤：1)分析最优解的性质，并刻划其结构特征。2)递推地定义最优值。3)以自底向上的方式或自顶向下的记忆化方法(备忘录 法)计算出最优值.4)根据计算最优值时得到的信息，构造问题的最优解。上节 下节,4.标准动态规划的基本框架for(j=1;j=1;i=i-1)/其它n-1个阶段 for(j=1;j=f(i);j=j+1)/f(i)与 i有关的表达式 xij=j=max(或min)g(xi-1j1j2)，g(xi-1jkjk+1)；t=g(x1j1j2);/由最优解求解最优解的方案print(x1j1);for(i=2;i=f(i);j=j+1)if(t=xiji)b

37、reak;上节 下节,【例2】资源分配问题。【例3】n个矩阵连乘的问题。上节 下节,4.5.3 突出阶段性的动态规划应用,【例2】资源分配问题。设有资源a,分配给n个项目,gi(x)为第i个项目分得资源x所得到的利润。求总利润最大的资源分配方案，也就是解下列问题：max z=g1(x1)+g2(x2)+gn(xn)x1+xx2+x3+xn=a,xi0,i=1，2,3,n函数gi(x)以数据表的形式给出.例如：现有7万元投资到A，B，C 三个项目，利润见表,求问题总利润最大的资源分配方案。上节 下节,算法设计1阶段划分及决策 比较直观的阶段划分就是逐步考虑每一个项目在不 同投资额下的利润情况。3

38、.数据结构设计：1)开辟一维数组q来存储原始数据。2)另开辟一维数组f存储当前最大收益情况。3)开辟记录中间结果的一维数组数组temp，记录正在计 算的最大收益。4)开辟二维数组a。5)数组gain存储第i个工程投资数的最后结果。上节 下节,对于一般问题设计算法如下：,main()int i,j,k,m,n,rest;int a100100，gain100;float q100,f100,temp100;print(“How mang item?”);input(m);print(“How mang money?”);input(n);print(“input gain table:”);fo

39、r(j=0;j=n;j+)input(qj);fj=qj;for(j=0;j=n;j+)a1,j=j;上节 下节,for(k=2;ktempj）tempj=fj-i+qi;ak,j=i;for(j=0;j=1;i-)gaini=airest;rest=rest-gaini;for(i=1;i=m;i+)print(gaini,”);print(fn);,【例3】n个矩阵连乘的问题。问题分析 算法设计 算法1(递归算法)算法1说明 算法2(递归算法)算法3(非递归算法)输出算法 上节 下节,问题分析 多个矩阵连乘运算是满足结合律的。例:M15*20*M220*50*M350*1*M41*100分

40、别按(M1*M2)*M3)*M4，M1*(M2*(M3*M4)，(M1*(M2*M3)*M4 的次序相乘,各需进行 5750,115000,1600次乘法。这个问题要用“动态规划”算法来完成:首先,从两个矩阵相乘的情况开始；然后,尝试三个矩阵相乘的情况；最后,等到n个矩阵相乘所用的最少的乘法次数及结合方式。上节 下节,算法设计 1.阶段划分 1）初始状态为一个矩阵相乘的计算量为0;2）第二阶段,计算两个相邻矩阵相乘的计算量,共n-1组3）第三阶段,计算两个相邻矩阵相乘的计算量,共n-2组 4）最后一个阶段,是n个相邻矩阵相乘的计算量,共1组,是问题解。上节 下节,2.阶段决策 一般地，计算M1

41、*M2*M3*Mn 其中M1，M2，,Mi分别是 r1*r2，r2*r3，,ri*ri+1阶矩阵，i=1,2,3,n。设mi,j是计算Mi*Mi+1*Mj的最少乘法次数(1ijn),对 mi,j有公式：0 当i=j时 ri-1*ri*ri+1 当j=i+1时 min(mi,k+mk+1,j+rirk+1rj+1)ikj 当ij时 以上动态规划方法是按s=0,1,2,3,.,n-1的顺序计算mi,i+s的。3.记录最佳期方案 用二维矩阵comij(n*n)来存储使mij为最小值时的 k 值。上节 下节,算法1(递归算法),int r100,com100100;main（）int n,i;prin

42、t(“How mang matrixes?”);input(n);peint(“How size every matrixe?”);for(i=1;i=n+1;i+)input(ri);print(“The least calculate quantity：”,course(1,n);for(i=1;i=n;i+)print(“换行符”);for(j=1;j=n;j+)print(comij);上节 下节,int course(int i,int j)int u,t;if(i=j)return 0;if(i=j-1)comii+1=i;return（ri*ri+1*rr+2）;u=course

43、(i,i)+course(i+1,j)+ri*ri+1*rj+1;comij=i;for(int k=i+1;k j;k+)t=course(i,k)+course(k+1,j)+ri*rk+1*rj+1;if(tu)u=t;comij=k;return u;上节 下节,算法1说明 以上的递归算法虽然解决了问题，但效率很低，有子问题重叠，n=4时的递归过程如下图：上节 下节,算法2(改进后递归算法),int m100100,com100100,r100;matrix2（）int n,;print(“How mang matrixes?”);input(n);print(“How size ev

44、ery matrixe?”);for(i=1;i=n+1;i+)input(ri);for(i=1;i=n;i+)/初始化化数组com和m。/for(j=1;j=n;j+)comij=0;mij=0;course(1,n)；print(“The least calculate quantity：”m1n);for(i=1;i=n;i+)print(“换行符”);for(j=1;j=n;j+)print(comij);上节 下节,course(int i,int j)if（mij0）return mij;if(i=j)return 0;if(i=j-1)comii+1=i;mij=ri*ri+1

45、*ri+2;return mij;int u=course(i,i)+course(i+1,j)+ri*ri+1*rj+1;comij=i;for(int k=i+1;kj;k+)int t=course(i,k)+course(k+1,j)+ri*rk+1*rj+1;if(tu)u=t;comij=k;mij=u;return u;上节 下节,算法3(非递归算法),main（）int n,r100,m100100,com100100;peint(“How mang matrixes?”);input(n);peint(“How size every matrixe?”);for(i=1;i=

46、n+1;i+)input(ri);for(i=1;i=n;i+)/初始化化数组com和m。/for(j=1;j=n;j+)comij=0;for(i=1;in;i+)mii=0;s=0 mii+1=ri*ri+1*ri+2;s=1 comii+1=i+1;上节 下节,mnn=0;for(s=2;s=n-1;s+)/动态规划过程/for(i=1;in-s+1;i+)j=i+s;mij=mii+mi+1j+ri*ri+1*rj+1;comij=i;for(k=i+1;kj;k+)t=mik+mk+1j+ri*rk+1*rj+1;if(t mij)mij=t;comij=k;print(“The l

47、east calculate quantity：”m1n);for(i=1;i=n;i+)print(“换行符”);for(j=1;j=n;j+)print(comij);上节 下节,输出部分的算法设计以上算法中关于矩阵相乘的结合方式，只是简单的输出了数组com的内容，不容易直观地被利用，还需要继续进行必要的人工处理，才能真正找到矩阵相乘的结合方式。怎么样更直观、合理地输出结合过程？即算法的输出能使用户直接了解计算矩阵的过程。首先看一下com数组存储的信息意义，它是一个二维数组，元素comij存储的是MiMj相乘的组合点k1，也就是说：Mi*Mi+1*Mj是由 Mi*Mi+1*Mk和Mk+1*

48、Mj同样，在数组com中我们也能找到MiMk相乘的组合点k2，Mk+1Mj相乘的组合点k3，。从数组信息中找到了大规模问题与小规模问题的递归关系：,输出算法 记k1=com1n，则最后一次运算的结合过程是 M1*Mk1和Mk1+1*Mn 记k2=com1k1，M1*Mk1的结合过程是 M1*Mk2和Mk2+1*Mk1,combine(int i,int j)if(i=j)return;combine(i,comij);combine(comij+1,j);print（M,i,“*M”，comij）;print（and M,comij+1,“*M”，j）;上节 下节,这一节问题的设计角度是从递推

49、思想进行的,设计中只要找出大规模问题与小规模问题(子问题)之间的递推关系,最后一个子问题所得最优解就是原问题的最优解。【例4】求两个字符序列的最长公共字符子序列。【例5】最长不降子序列。上节 下节,4.5.4 突出递推的动态规划应用,【例4】求两个字符序列的最长公共字符子序 列。问题分析 算法设计 算法(递归形式)算法(非递归)上节 下节,问题分析 若A的长度为n，若B的长度为m，则 A的子序列共有：Cn1+Cn2+Cn3+Cnn=2n-1 B的子序列共有：Cm1+Cm2+Cm3+Cmm=2m-1 如采用枚举策略，当m=n时，共进行串比较：Cn1*Cm1+Cn2*Cm2+Cn3*Cm3+Cnn

50、*Cnn22n 次，耗时太多,不可取。此问题不可能简单地分解成几个独立的子问题，也不能用分治法来解。所以，我们只能用动态规划的方法去解决。上节 下节,算法设计1递推关系分析 设 A=“a0，a1，am-1”，B=“b0，b1，bn-1”，Z=“z0,z1,zk-1”为它们的最长公共子序列。有以下结论：1）如果am-1=bn-1,则zk-1=am-1=bn-1,且“z0,z1,zk-2”是“a0,a1,am-2”和“b0,b1,bn-2”的一个最长公共子序列；2）如果am-1bn-1，则若zk-1am-1，蕴涵“z0，z1，zk-1”是a0,a1,am-2和b0,b1,bn-1的一个最长公共子