第四章(贪心、动态)

《第四章(贪心、动态)》由会员分享，可在线阅读，更多相关《第四章(贪心、动态)（116页珍藏版）》请在金锄头文库上搜索。

1、第第 四四 章章 基本的算法策略基本的算法策略 贪贪婪婪法法又又叫叫登登山山法法, , 它它的的根根本本思思想想是是逐逐步步到到达达山山顶顶, ,即即逐逐步步获获得得最最优优解解。贪贪婪婪算算法法没没有有固固定定的的算算法法框框架架，算算法法设设计计的的关关键键是是贪贪婪婪策策略略的的选选择择。一一定定要要注注意意，选选择择的的贪贪婪婪策策略略要要具具有有无无后后向向性性。某某状状态态以以后后的的过过程程和和不不会会影影响响以以前前的的状状态态, ,只只与与当当前前状状态态或或以以前前的的状状态态有有关关, ,称称这这种种特特性性为为无无后效性后效性。 上节上节 下节下节4.4 4.4 贪婪算

2、法贪婪算法 【例例1 1】键键盘盘输输入入一一个个高高精精度度的的正正整整数数N N，去去掉掉其其中中任任意意S S个个数数字字后后剩剩下下的的数数字字按按原原左左右右次次序序将将组组成成一一个个新新的的正正整整数数。编编程程对对给给定定的的N N和和S S，寻寻找找一一种种方方案案使使得得剩剩下下的的数数字字组组成成的的新新数最小。数最小。 输输入入数数据据均均不不需需判判错错。输输出出应应包包括括所所去去掉掉的的数数字字的的位位置置和组成的新的正整数（和组成的新的正整数（N N不超过不超过240240位）。位）。数数据据结结构构设设计计：对对高高精精度度正正整整数数的的运运算算在在上上一一

3、节节我我们们刚刚刚刚接接触触过过，和和那那里里一一样样，将将输输入入的的高高精精度度数数存存储储为为字字符符串串格格式式。根据输出要求设置数组，在删除数字时记录其位置。根据输出要求设置数组，在删除数字时记录其位置。 上节上节 下节下节4.4.1 4.4.1 可绝对贪婪问题可绝对贪婪问题问题分析问题分析 在在位位数数固固定定的的前前提提下下，让让高高位位的的数数字字尽尽量量小小其其值值就就较较小小，依依据据此贪婪策略就可以解决这个问题。此贪婪策略就可以解决这个问题。 怎怎么么样样根根据据贪贪婪婪策策略略删删除除数数字字呢呢？总总目目标标是是删删除除高高位位较较大大的的数数字字，具具体体地地相相邻

4、邻两两位位比比较较若若高高位位比比低低位位大大则则删删除除高高位位。我我们们通通过过“枚举归纳枚举归纳”设计算法的细节，看一个实例（设计算法的细节，看一个实例（s=3）：n1=“12435863”4比比3大大删除删除“1235863”8比比6大大删除删除“123563”6比比3大大删除删除“12353”只只看看这这个个实实例例，有有可可能能“归归纳纳”出出不不正正确确的的算算法法，先先看看下下一一个个实实例，我们再进一步解释：例，我们再进一步解释：n2=”231183”3比比1大大删除删除“21183”2比比1大大删除删除“1183”8比比3大大删除删除“113”由由实实例例n1，相相邻邻数数

5、字字只只需需要要从从前前向向后后比比较较；而而从从实实例例n2中中可可以以看看出出当当第第i位位与与第第i+1位位比比较较，若若删删除除第第i位位后后，必必须须向向前前考考虑第虑第i-1位与第位与第i+1位进行比较，才能保证结果的正确性。位进行比较，才能保证结果的正确性。由由此此可可知知通通过过实实例例设设计计算算法法时时，枚枚举举的的实实例例一一定定要要有有全全面面性性，实实例例最最好好要要能能代代表表所所有有可可能能的的情情况况，或或者者在在必必要要时时多多列列举举几几个个不不同同的的实实例例。再再看看以以下下两两个个实实例例又又可可总总结结出出一一些些需需要要算算法法特特殊殊处理的情况。

6、处理的情况。n3=”1234567”s=3由由这这个个实实例例看看出出，经经过过对对n3相相邻邻比比较较一一个个数数字字都都没没有有删删除除，这这就就要要考考虑虑将将后后三三位位进进行行删删除除，当当然然还还有有可可能能，在在相相邻邻比比较较的的过程中删除的位数小于过程中删除的位数小于s时，也要进行相似的操作。时，也要进行相似的操作。n4=”120083”3比比0大大删除删除“10083”2比比0大大删除删除“0083”8比比3大大删除删除 “003”得得到的新数数据是到的新数数据是3 由这个实例子又能看出，当删除掉一些数字后，结果的高位有由这个实例子又能看出，当删除掉一些数字后，结果的高位有

7、可能出现数字可能出现数字“0”，直接输出这个数据不合理，要将结果中高位，直接输出这个数据不合理，要将结果中高位的数字的数字“0”全部删除掉，再输出。特别地还要考虑若结果串是全部删除掉，再输出。特别地还要考虑若结果串是“0000”时，不能将全部时，不能将全部“0”都删除，而要保留一个都删除，而要保留一个“0”最后最后输出。输出。 由此可以看出进行算法设计时，从具体到抽象的归纳一定要选由此可以看出进行算法设计时，从具体到抽象的归纳一定要选取大量不同的实例，充分了解和体会解决问题的过程、规律和各取大量不同的实例，充分了解和体会解决问题的过程、规律和各种不同情况，才能设计出正确的算法。种不同情况，才能

8、设计出正确的算法。算法设计算法设计1：根据以上实例分析，算法主要由四部分组成：初始化、相邻根据以上实例分析，算法主要由四部分组成：初始化、相邻数字比较（必要时删除）、处理比较过程中删除不够数字比较（必要时删除）、处理比较过程中删除不够s位的情况和位的情况和结果输出。结果输出。 其中删除字符的实现方法很多，如：其中删除字符的实现方法很多，如： 1 1）物理进行字符删除，就是用后面的字符覆盖已删除的字符，字）物理进行字符删除，就是用后面的字符覆盖已删除的字符，字符串长度改变。这样可能会有比较多字符移动操作，算法效率不高。符串长度改变。这样可能会有比较多字符移动操作，算法效率不高。1）可可以以利利用

9、用数数组组记记录录字字符符的的存存在在状状态态，元元素素值值为为“1”表表示示对对应应数数字字存存在在，元元素素值值为为“0”表表示示对对应应数数字字已已删删除除。这这样样避避免免了了字字符符的的移移动动，字字符符串串长长度度不不会会改改变变，可可以以省省略略专专门门记记录录删删除除数数字字的的位位置置。但这样做前后数字的比较过程和最后的输出过程相对复杂一些。但这样做前后数字的比较过程和最后的输出过程相对复杂一些。2）同样还是利用数组，记录未删除字符的下标，粗略的过程如下：同样还是利用数组，记录未删除字符的下标，粗略的过程如下：n=“12435833”0000004比比3大大删除删除“1235

10、833”1245008比比3大大删除删除“123533”124505比比3大大删除删除“12333”12478这这时时数数组组好好象象是是数数据据库库中中的的索索引引文文件件。此此方方式式同同样样存存在在操操作作比比较较复复杂的问题。杂的问题。我们采用方法我们采用方法1）。）。 一种简单的控制相邻数字比较的方法是每次从头开始，最多一种简单的控制相邻数字比较的方法是每次从头开始，最多删除删除s s次，也就从头比较次，也就从头比较s s次。按题目要求次。按题目要求设置数组设置数组data记录删记录删除的数字所在位置除的数字所在位置delete(charn,intb,intk)inti;for(i=

11、b;ilen)print(“dataerror”);return;j1=0;for(i=0;i=s;i=i+1)for(j=1;jnj+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)for (i=i;i1)delete(n,1,1);/将字符串首的若干个将字符串首的若干个“0”去掉去掉 print(n);for(i=1;ilen)print

12、(“dataerror”);return;i=0;j=1;j1=0;while(isandj=length(n)-1)while(nj=nj+1)j=j+1;if(jj1)datai=j+i;elsedatai=datai-1-1;i=i+1;j1=j;j=j-1;for (i=i;i=s;i=i+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控制控制相邻比较操作的下标，当删除了第相邻比较操作的下标

13、，当删除了第j个字符后，个字符后，j赋值为赋值为j-1，以保以保证实例证实例2（字符串（字符串n2）出现的情况得到正确的处理。出现的情况得到正确的处理。【例例2 2】数列极差问题数列极差问题 在在黑黑板板上上写写了了N N个个正正整整数数作作成成的的一一个个数数列列，进进行行如如下下操操作作: :每每一一次次擦擦去去其其中中的的两两个个数数a a和和b b，然然后后在在数数列列中中加加入入一一个个数数ab+1ab+1，如如此此下下去去直直至至黑黑板板上上剩剩下下一一个个数数，在在所所有有按按这这种种操操作作方方式式最最后后得得到到的的数数中中，最最大大的的记记作作maxmax，最最小小的的记记

14、作作minmin，则该数列的极差定义为则该数列的极差定义为M=max-minM=max-min。 问题分析问题分析 算法设计算法设计 数据结构设计数据结构设计 算法分析算法分析 上节上节 下节下节问题分析问题分析和和上上一一个个例例题题一一样样，我我们们通通过过实实例例来来认认识识题题目目中中描描述述的的计计算算过过程程。对对三个具体的数据三个具体的数据3，5，7讨论讨论，可能有以下三种，可能有以下三种结结果：果：（3*5+1）*7+1=113、（3*7+1）*5+1=111、（5*7+1）*3+1=109由由此此可可见见，先先运运算算小小数数据据得得到到的的是是最最大大值值，先先运运算算大大

15、数数据据得得到到的的是最小是最小值值。 上节上节 下节下节下下面面再再以以三三个个数数为为例例证证明明此此题题用用贪贪心心策策略略求求解解的的合合理理性性, ,不不妨妨假假设设：ab=a+k1c=a+k1+k2ab=a+k10k1,k20，则则有有以以下下几几种种组组合合计计算结果：算结果：1)(a*b+1)*c+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+k2+11)(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

16、)*a+k1+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+13)(b*c+1)*a+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+1 显显然然此此问问题题适适合合用用贪贪婪婪策策略略, ,不不过过在在求求最最大大值值时时，要要先先选选择择较较小小的的数数操操作作。反反过过来来求求最最小小值值时时，要要先先选选择择较较大大的的数数操操作作。这是一道两次运用贪心策略解决的问题。这是一道两次运用贪心策略解决的问题。 上

17、节上节 下节下节算法设计算法设计 1 1）由由以以上上分分析析，大大家家可可以以发发现现这这个个问问题题的的解解决决方方法法和和哈哈夫夫曼曼树树的的构构造造过过程程相相似似，不不断断从从现现有有的的数数据据中中，选选取取最最大大和和最最小小的的两两个个数数，计计算算后后的的结结果果继继续续参参与与运运算算，直直到到剩剩余余一一个个数数算算法结束。法结束。 2) 2) 选选取取最最大大和和最最小小的的两两个个数数较较高高效效的的算算法法是是用用二二分分法法完完成成， 这这里里仅仅仅仅用用简简单单的的逐逐个个比比较较的的方方法法来来求求解解。 注注意意到到由由于于找找到到的的两两个个数数将将不不再

18、再参参与与其其后后的的运运算算，其其中中一一个个自自然然地地是是用用它它们们的的计计算算结结果果代代替替，另另一一个个我我们们用用当当前前的的最最后后一一个个数数据据覆覆盖盖即即可可。所所以以不不但但要要选选取取最最大大和和最最小小，还还必必须须记记录录它它们们的的位位置置，以以便将其覆盖。便将其覆盖。 3 3）求求maxmax、minmin的的过过程程必必须须独独立立，也也就就是是说说求求maxmax和和minmin都都必须从原始数据开始必须从原始数据开始, ,否则不能找到真正的否则不能找到真正的maxmax和和minmin。 上节上节 下节下节数据结构设计数据结构设计 1) 1) 由设计由

19、设计2 2）、）、3 3）知，必须用两个数组同时存储初始数据。）知，必须用两个数组同时存储初始数据。 2) 2) 求求最最大大和和最最小小的的两两个个数数的的函函数数至至少少要要返返回回两两个个数数据据，为为方方便起见我们用全局变量实现。便起见我们用全局变量实现。ints1,s2;main（）intj,n,a100,b100,max,min;print(“Howmangdata?”);input(n);print(“inputthesedata”);for(j=1;j2) while (n2) max2(a,n); as1= as1* as2+1; max2(a,n); as1= as1* a

20、s2+1; as2=an; n=n-1; as2=an; n=n-1; return(a1* a2+1); return(a1* a2+1); max2(inta,intn)intj;if(a1=a2)s1=1;s2=2;elses1=2;s2=1;for(j=3;jas1)s2=s1;s1=j;elseif(ajas2)s2=j; 上节上节 下节下节calculatemaxcalculatemax( (intint a, a,intint n) n) intint j; j; while (n2) while (n2) min2(a,n); as1= as1* as2+1; min2(a,n

21、); as1= as1* as2+1; as2=an; n=n-1; as2=an; n=n-1; return(a1* a2+1); return(a1* a2+1); min2(inta,intn)intj;if(a1=a2)s1=1;s2=2;elses1=2;s2=1;for(j=3;j=n;j+)if(ajas1)s2=s1;s1=j;elseif(aj181/2/2， 7/8-1/7/8-1/2121/3/3， 7/8-1/2-1/3=1/247/8-1/2-1/3=1/24。过程如下：过程如下： 1)1)找最小的找最小的n n（也就是最大的埃及分数），使分数也就是最大的埃及分数）

22、，使分数f f1/n1/n； 2)2)输出输出1/n1/n； 3)3)计算计算f=f-1/nf=f-1/n； 4)4)若此时的若此时的f f是埃及分数，输出是埃及分数，输出f,f,算法结束算法结束, ,否则返回否则返回1 1）。）。 上节上节 下节下节数学模型数学模型 记记真真分分数数F=A/BF=A/B；对对B/AB/A进进行行整整除除运运算算, ,商商为为D, D, 余余数数为为0 0K KA A，它们之间的关系及导出关系如下：它们之间的关系及导出关系如下： B=A*D+KB=A*D+K，B/A=D+K/AB/A=D+K/AD+1D+1，A/BA/B1/(D+1)1/(D+1)，记，记C=

23、D+1C=D+1。 这这样样我我们们就就找找到到了了分分数数F F所所包包含含的的“最最大大的的”埃埃及及分分数数就就是是1/C1/C。进一步计算：进一步计算： A/B-1/C=A/B-1/C=（A*C-BA*C-B）/B*C/B*C 也也就就是是说说继继续续要要解解决决的的是是有有关关分分子子为为A=A*C-B,A=A*C-B,分分母母为为B=B*CB=B*C的的问题。问题。 上节上节 下节下节算法设计算法设计 由以上数学模型，真正的算法过程如下：由以上数学模型，真正的算法过程如下： 1)1)设某个真分数的分子为设某个真分数的分子为A(1A(1），），分母为分母为B B； 2)2)把把B B

24、除以除以A A的商的整数部分加的商的整数部分加1 1后的值作为埃及后的值作为埃及 分数的一个分母分数的一个分母C;C; 3) 3)输出输出1/C1/C； 4)4)将将A A乘以乘以C C减去减去B B作为新的作为新的A A； 5)5)将将B B乘以乘以C C作为新的作为新的B B； 6)6)如果如果A A大于大于1 1且能整除且能整除B,B,则最后一个分母为则最后一个分母为B/AB/A； 7)7)如果如果A A1,1,则最后一个分母为则最后一个分母为B;B;否则转步骤否则转步骤(2).(2). 上节上节 下节下节例：例：7/8=1/2+1/3+1/247/8=1/2+1/3+1/24的解题步骤

25、：的解题步骤： 同样用变量同样用变量A A表示分子，变量表示分子，变量B B表示分母；表示分母； C=8+1=2 /C=8+1=2 /说明说明7/81/27/81/2， 打印打印1/21/2 A=7*2-8=6 A=7*2-8=6，B=B*C=16 B=B*C=16 / /在计算在计算7/8-1/2=(7*2-8)/(7*2)=6/16=A/B7/8-1/2=(7*2-8)/(7*2)=6/16=A/B C=16/6+1=3 C=16/6+1=3 / /说明说明16/61/316/61/3， 打印打印1/31/3 A=6*3-16=2 A=6*3-16=2，B=B*C=16*3=48B=B*C

26、=16*3=48 / /在计算在计算6/16-1/3=(6*3-16)/(16*3)=2/48=A/B6/16-1/3=(6*3-16)/(16*3)=2/48=A/B A1 A1但但B/AB/A为整数为整数2424，打印，打印1/24 1/24 结束结束. . 上节上节 下节下节算法算法main（）（）inta,b,c;print(“inputelement”);input(a);print(“inputdenominator”);input(b);if(ab)print(“inputerror”);elseif(a=1orbmoda=0)print(a,/,b,=1,/,b/a);else

27、 上节 下节while(a1)c=ba+1a=a*c-b:b=b*cprint(1/,c);if(bmoda=0)print(+1/;b/a);a=1;if(a1)print(+); 【例例4 4】 币种统计问题 【例例5 5】 取数游戏 上节 下节4.4.2 相对或近似贪婪问题 4.4.14.4.1节节的的三三个个例例子子对对于于输输入入的的任任何何数数据据，贪贪婪婪策策略略都都是是适适用用的的，因因此此我我们们称称它它们们为为“可可绝绝对对贪贪婪婪问问题题”。看看下下一一节节的的例例子子就就明明白白，有的问题就不一定如此了。有的问题就不一定如此了。【例例4 4】币种统计问题币种统计问题 某

28、某单单位位给给每每个个职职工工发发工工资资（精精确确到到元元）。为为了了保保证证不不要要临临时时兑兑换换零零钱钱, , 且且取取款款的的张张数数最最少少，取取工工资资前前要要统统计计出出所所有有职职工工的的工工资资所所需需各各种种币币值值(100,50,20,10,5,2,1(100,50,20,10,5,2,1元元共共七七种种) )的的张张数数。请编程完成。请编程完成。 算法设计算法设计 算法说明算法说明 算法分析算法分析 贪婪策略贪婪策略 上节上节 下节下节算法设计算法设计 1 1) ) 从键盘输入每人的工资。从键盘输入每人的工资。 2 2) ) 对对每每一一个个人人的的工工资资，用用“贪

29、贪婪婪”的的思思想想，先先尽尽量量多多地地取取大大面额的币种，由大面额到小面额币种逐渐统计。面额的币种，由大面额到小面额币种逐渐统计。 3 3) ) 利用数组应用技巧利用数组应用技巧, ,将七种币值存储在数组将七种币值存储在数组B B。这样，七种这样，七种 币值就可表示为币值就可表示为Bi,i=1,2,3,4,5,6,7Bi,i=1,2,3,4,5,6,7。为了能实现贪为了能实现贪婪婪策略，策略，七种币应该从大面额的币种到小面额的币种依次存储。七种币应该从大面额的币种到小面额的币种依次存储。 4 4) ) 利用数组技巧利用数组技巧, ,设置一个有设置一个有7 7个元素的累加器数组个元素的累加器

30、数组S S。 上节上节 下节下节算法算法main( )main( ) intint i,j,n,GZ,A i,j,n,GZ,A； intint B8=0,100,50,20,10,5,2,1,S8; B8=0,100,50,20,10,5,2,1,S8; input(n); input(n); for(i=1;i=n;i+) for(i=1;i=n;i+) input(GZ); input(GZ); for(j=1,j=7;j+) for(j=1,j=7;j+) A=GZ/Bj; A=GZ/Bj; Sj=Sj+A; Sj=Sj+A; GZ=GZ-A*Bj; GZ=GZ-A*Bj; for(i=

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

32、 这这 个个 结结 论论 ) )。 假假 若若 , ,某某 国国 的的 币币 种种 是是 这这 样样 的的 , ,共共 9 9种种:100,70,50,20,10,7,5,2,1:100,70,50,20,10,7,5,2,1。在在这这样样的的币币值值种种类类下下, ,再再用用贪贪婪婪算算法法就就行行不不通通了了, ,比比如如某某人人工工资资是是140,140,按按贪贪婪婪算算法法140=100*(1140=100*(1张张)+20*(2)+20*(2张张) )共共需需要要3 3张张, ,而而事事实实上上, ,只只要要取取2 2张张7070面面额额的的是是最最佳佳结果结果, ,这类问题可以考虑

33、用动态规划算法来解决。这类问题可以考虑用动态规划算法来解决。 由由此此，在在用用贪贪婪婪算算法法策策略略时时，最最好好能能用用数数学学方方法法证证明明每每一一步的策略是否能保证得到最优解。步的策略是否能保证得到最优解。 上节上节 下节下节【例例5 5】取数游戏取数游戏 有2个人轮流取2n个数中的n个数，取数之和大者为胜。请编写算法，让先取数者胜，模拟取数过程。 问题分析 算法设计 算法说明 算法分析 上节 下节问题分析问题分析 这这个个游游戏戏一一般般假假设设取取数数者者只只能能看看到到2n2n个个数数中中两两边边的的数数, ,用贪婪算法的情况用贪婪算法的情况: : 若若一一组组数数据据为为：

34、6,16,27,6,12,9,2,11,6,56,16,27,6,12,9,2,11,6,5。用用贪贪婪婪策策略略每每次次两两人人都都取取两两边边的的数数中中较较大大的的一一个个数数, ,先先取取者者胜胜. .以以A先先取为例：取为例： 取数结果为：取数结果为： A 6,27,12,5,11=61 A 6,27,12,5,11=61 胜胜 B 16,6,9,6,2=39B 16,6,9,6,2=39 上节上节 下节下节但但若若选选另另一一组组数数据据：16,27,7,12,9,2,11,616,27,7,12,9,2,11,6。仍仍都都用用贪贪婪婪算法，先取者算法，先取者A A败。败。 取数结

35、果为：取数结果为： A 16,7,9,11=43A 16,7,9,11=43 B 27,12,6,2=47 B 27,12,6,2=47 胜胜 其其实实，若若我我们们只只能能看看到到两两边边的的数数据据，则则此此题题无无论论先先取取还还是是后取都无必胜的策略。这时一般的策略是用后取都无必胜的策略。这时一般的策略是用近似贪婪算法近似贪婪算法。 但但若若取取数数者者能能看看到到全全部部2n2n个个数数，则则此此问问题题可可有有一一些些简简单单的的方方法法，有有的的虽虽不不能能保保证证所所取取数数的的和和是是最最大大，但但确确是是一一个个先先取取者者必胜的策略。必胜的策略。 上节上节 下节下节数数学

36、学模模型型建建立立：N个个数数排排成成一一行行，我我们们给给这这N个个数数从从左左到到右右编编号号，依依次次为为1，2，N，因因为为N为为偶偶数数，又又因因为为是是我我们们先先取取数数，计计算算机机后后取取数数，所所以以一一开开始始我我们们既既可可以以取取到到一一个个奇奇编编号号的的数数（最最左左边边编编号号为为1的的数数）又又可可以以取取到到一一个个偶偶编编号号的的数数（最最右右边边编编号号为为N的数）。的数）。 如如果果我我们们第第一一次次取取奇奇编编号号（编编号号为为1）的的数数，则则接接着着计计算算机机只能取到偶编号（编号为只能取到偶编号（编号为2或或N）的数；的数； 如如果果我我们们

37、第第一一次次取取偶偶编编号号（编编号号为为N）的的数数，则则接接着着计计算算机机只能取到奇编号（编号为只能取到奇编号（编号为1或或N-1）的数；的数； 即即无无论论我我们们第第一一次次是是取取奇奇编编号号的的数数还还是是取取偶偶编编号号的的数数，接接着着计算机只能取到另一种编号（偶编号或奇编号）的数。计算机只能取到另一种编号（偶编号或奇编号）的数。 这是对第一个回合的分析，显然对以后整个取数过程都适这是对第一个回合的分析，显然对以后整个取数过程都适用。也就是说，我们能够控制让计算机自始自终只取一种编号用。也就是说，我们能够控制让计算机自始自终只取一种编号的数。这样，我们只要比较奇编号数之和与偶

38、编号数之和谁大，的数。这样，我们只要比较奇编号数之和与偶编号数之和谁大，以决定最开始我们是取奇编号数还是偶编号数即可。（如果奇以决定最开始我们是取奇编号数还是偶编号数即可。（如果奇编号数之和与偶编号数之和同样大，我们第一次可以任意取数，编号数之和与偶编号数之和同样大，我们第一次可以任意取数，因为当两者所取数和相同时，先取者为胜。因为当两者所取数和相同时，先取者为胜。算法设计算法设计：有了以上建立的高效数学模型，算法就很简单了，算：有了以上建立的高效数学模型，算法就很简单了，算法只需要分别计算一组数的奇数位和偶数位的数据之和，然后就法只需要分别计算一组数的奇数位和偶数位的数据之和，然后就先了取数

39、者就可以确定必胜的取数方式了。先了取数者就可以确定必胜的取数方式了。以下面一排数为例：以下面一排数为例：12310567894奇编号数之和为奇编号数之和为25（=1+3+5+7+9），小于偶编号数之和为），小于偶编号数之和为30（=2+10+6+8+4）。我们第一次取）。我们第一次取4，以后，计算机取哪边的，以后，计算机取哪边的数我们就取哪边的数（如果计算机取数我们就取哪边的数（如果计算机取1，我们就取，我们就取2；如果计算机；如果计算机取取9，我们就取，我们就取8）。这样可以保证我们自始自终取到偶编号的数，）。这样可以保证我们自始自终取到偶编号的数，而计算机自始自终取到奇编号的数。而计算机自

40、始自终取到奇编号的数。main( )main( ) intint i,s1,s2,data; i,s1,s2,data;input(n); s1=0input(n); s1=0； s2=0;s2=0; for(i=1;i=n;i=i+1) for(i=1;is2) if(s1s2) print(“first print(“first take take left”);left”); else else print(“first print(“first take take right”);right”); 这这个个例例题题又又一一次次说说明明，解解决决问问题题时时数数学学模模型型的的选选择择是

41、非常重要的。是非常重要的。 1.1.贪心法的基本思路贪心法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策,尽可能地求得最好的解。当达到某算法中的某一步不需要再继续前进时，算法停止。 上节 下节4.4.3 关于贪婪策略讨论2.2.该算法适用的问题该算法适用的问题： 贪婪算法对问题只需考虑当前局部信息就要做出决策，也就是说使用贪婪算法的前提是“局部最优策略能导致产生全局最优解”。 该算法的适用范围较小, 若应用不当, 不能保证求得问题的最佳解。一般情况下通过一些实际的数据例子(当然要有一定的普遍性),就能从直观上就能判断一个问题是否可以用贪婪算法，如本节的例

42、2。更准确的方法是通过数学方法证明问题对贪婪策略的选用性。 上节 下节3.3.该策略下的算法框架该策略下的算法框架： 从问题的某一初始解出发； while能朝给定总目标前进一步do; 利用可行的决策，求出可行解的一个解元素; 由所有解元素组合成问题的一个可行解。 上节 下节4.4.贪婪策略选择贪婪策略选择: : 首先贪婪算法的原理是通过局部最优来达到全局最优,采用的是逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的（在一定的标准下），决策一旦作出，就不可再更改。用贪婪算法只能解决通过局部最优的策略能达到全局最优的问题。因此一定要注意判断问题是否适合采用贪婪算法策略，找到的解是否一定是问

43、题的最优解。 上节 下节 在在动动态态规规划划算算法法策策略略中中，体体现现在在它它的的决决策策不不是是线线性性的的而而是是全全面面考考虑虑不不同同的的情情况况分分别别进进行行决决策策, , 并并通通过过多多阶阶段段决决策策来来最最终终解解决决问问题题。在在各各个个阶阶段段采采取取决决策策后后, , 会会不不断断决决策策出出新新的的数数据据, ,直直到到找找到到最最优优解解. .每每次次决决策策依依赖赖于于当当前前状状态态, , 又又随随即即引引起起状状态态的的转转移移。一一个个决决策策序序列列就就是是在在变变化化的的状状态态中中产产生生出出来来的的，故故有有“动动态态”的的含含义义。所所以以

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

45、为： 9+15+8+9+10=51 （自上而下）， 19+2+10+12+9=52（自下而上）。都得不到最优解，真正的最大和是： 9+12+10+18+10=59。 在知道数塔的全貌的前提下，可以用枚举法或下一章将学习的搜索算法来完成。 上节 下节算法设计算法设计 动态规划设计过程如下：动态规划设计过程如下： 1.1.阶段划分：阶段划分： 第一步对于第五层的数据，我们做如下五次决策：第一步对于第五层的数据，我们做如下五次决策： 对经过第四层对经过第四层2 2的路径选择第五层的的路径选择第五层的1919， 对经过第四层对经过第四层1818的路径选择第五层的的路径选择第五层的1010， 对经过第四

46、层对经过第四层9 9的路径也选择第五层的的路径也选择第五层的1010， 对经过第四层对经过第四层5 5的路径选择第五层的的路径选择第五层的1616。 上节上节 下节下节以上的决策结果将五阶数塔问题变为以上的决策结果将五阶数塔问题变为4 4阶子问题，递推阶子问题，递推出第四层与第五层的和为出第四层与第五层的和为: : 21(2+19),28(18+10),19(9+10),21(5+16) 21(2+19),28(18+10),19(9+10),21(5+16)。 用同样的方法还可以将用同样的方法还可以将4 4阶数塔问题阶数塔问题, ,变为变为3 3阶数塔问题。阶数塔问题。 最后得到的最后得到的

47、1 1阶数塔问题，就是整个问题的最优解。阶数塔问题，就是整个问题的最优解。 上节上节 下节下节 2 2存储、求解：存储、求解： 1) 1) 原始信息存储原始信息存储 原始信息有层数和数塔中的数据，层数用一个整型原始信息有层数和数塔中的数据，层数用一个整型 变量变量n n存储，数塔中的数据用二维数组存储，数塔中的数据用二维数组datadata，存储成如存储成如 下的下三角阵下的下三角阵: : 9 9 12 15 12 15 10 6 8 10 6 8 2 18 9 5 2 18 9 5 19 7 10 4 16 19 7 10 4 16 上节上节 下节下节2) 2) 动态规划过程存储动态规划过程

48、存储 必需用二维数组必需用二维数组a a存储各阶段的决策结果。二维数组存储各阶段的决策结果。二维数组a a的存储内容如下：的存储内容如下： dnj=datanj j=1,2,dnj=datanj j=1,2,n,n； i=n-1,n-2,i=n-1,n-2,1 1，j=1,2,j=1,2,i,i；时时 dij=max(di+1jdij=max(di+1j，di+1j+1)+dataijdi+1j+1)+dataij 最后最后a11a11存储的就是问题的结果。存储的就是问题的结果。 上节上节 下节下节3) 3) 最优解路径求解及存储最优解路径求解及存储 仅有数组仅有数组datadata和数组和数

49、组a a可以找到最优解的路径，可以找到最优解的路径， 但需要但需要自顶向下比较数组自顶向下比较数组datadata和数组和数组a a是可以找到。如图是可以找到。如图4.4.5.25.2求解求解和输出过程如下：和输出过程如下： 上节上节 下节下节 输出输出a119a119 b=d11-data11=59-9=50 b=d11-data11=59-9=50 b b与与d21,d22 d21,d22 比较比较 b b与与d21d21相等输出相等输出data2112data2112 b=d21-data21=50-12=38 b=d21-data21=50-12=38 b b与与d31,d32 d31

50、,d32 比较比较 b b与与d31d31相等输出相等输出data3110data3110 b=a31-data31=38-10=28 b=a31-data31=38-10=28 b b与与d41,d42 d41,d42 比比较较 b b与与d42d42相等输出相等输出data4218data4218 b=d42-data42=28-18=10 b b=d42-data42=28-18=10 b与与d52,d53 d52,d53 比较比较 b b与与d53d53相等输出相等输出data5310“data5310“ 上节上节 下节下节数组数组datadata 数组数组d d 9 59 9 59

51、12 15 50 49 12 15 50 49 10 6 8 38 34 29 10 6 8 38 34 29 2 18 9 5 21 28 19 21 2 18 9 5 21 28 19 21 19 7 10 4 16 19 7 10 4 16 19 7 10 4 16 19 7 10 4 16 图图4-4-12 12 数塔及动态规划过程数据数塔及动态规划过程数据 上节上节 下节下节为了设计简洁的算法，我们最后用三维数组为了设计简洁的算法，我们最后用三维数组a50503a50503存储以上确定的三个数组的信息。存储以上确定的三个数组的信息。 a50501a50501代替数组代替数组datad

52、ata， a50502a50502代替数组代替数组d, d, a50503 a50503记录解路径。记录解路径。 上节上节 下节下节 数塔问题的算法数塔问题的算法main( )main( ) intint a50503,i,j,n; a50503,i,j,n; print( please input the number of rows:); print( please input the number of rows:); input(n); input(n);for( i=1 ;i=n;i+)for( i=1 ;i=1;i-)for (i=n-1 ; i=1;i-) for (j=1 ;j

53、= i ;j+) for (j=1 ;j= i ;j+)if (ai+1j2ai+1j+12) if (ai+1j2ai+1j+12) aij2=aij2+ai+1j2; aij2=aij2+ai+1j2; aij3=0; aij3=0; elseelse aij2=aij2+ai+1j+12; aij2=aij2+ai+1j+12; aij3=1; aij3=1;print(max=,a112);print(max=,a112);j=1;j=1;for( i=1 ;i= n-1;i+)for( i=1 ;i); print(aij1,-); j=j+aij3; j=j+aij3; print

54、 (anj1);print (anj1); 上节上节 下节下节从例子中可以看到：从例子中可以看到： 动态规划动态规划= =贪婪策略贪婪策略+ +递推递推( (降阶降阶)+)+存储递推结果存储递推结果 贪贪婪婪策策略略、递递推推算算法法都都是是在在“线线性性”地地解解决决问问题题，而而动动态态规规划划则则是是全全面面分分阶阶段段地地解解决决问问题题。可可以以通通俗俗地地说说动动态态规规划划是是“带决策的多阶段、多方位的递推算法带决策的多阶段、多方位的递推算法”。 上节上节 下节下节1.适合动态规划的问题特征 动态规划算法的问题及决策应该具有三个性质：最优 化原理、无后向性、子问题重叠性质。1)

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

56、，并刻划其结构特征。 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=xi

57、ji)break; 上节 下节 【例例2 2】 资源分配问题。 【例例3 3】 n个矩阵连乘的问题。 上节 下节4.5.3 突出阶段性的动态规划应用【例例2 2】资源分配问题。资源分配问题。 设设有有资资源源a,a,分分配配给给n n个个项项目目, ,gigi(x)(x)为为第第i i个个项项目目分分得得资资源源x x所所得得到到的的利利润润。求求总总利利润润最最大大的的资资源源分分配配方方案案，也也就就是是解解下下列列问题：问题： max z=g1(x1)+ g2(x2)+max z=g1(x1)+ g2(x2)+gngn( (xnxn) ) x1+xx2+x3+ x1+xx2+x3+xnx

58、n=a, xi0,i=1=a, xi0,i=1，2,3,2,3,n,n函数函数gigi(x)(x)以数据表的形式给出以数据表的形式给出. .例例如如：现现有有7 7万万元元投投资资到到A A，B B，C C 三三个个项项目目，利利润润见见表表, ,求求问问题题总利润最大的资源分配方案。总利润最大的资源分配方案。 上节上节 下节下节算法设计算法设计1 1阶段划分及决策阶段划分及决策 比较直观的阶段划分就是比较直观的阶段划分就是逐步逐步考虑考虑每一个项目每一个项目在不在不 同投资额下的利润情况。同投资额下的利润情况。3. 3. 数据结构设计：数据结构设计： 1) 1) 开辟一维数组开辟一维数组q

59、q来存储原始数据。来存储原始数据。 2) 2) 另开辟一维数组另开辟一维数组f f存储当前最大收益情况。存储当前最大收益情况。 3) 3) 开辟记录中间结果的一维数组数组开辟记录中间结果的一维数组数组temptemp，记录正在计记录正在计 算的最大收益。算的最大收益。 4) 4) 开辟二维数组开辟二维数组a a。 5) 5) 数组数组gaingain存储第存储第i i个工程投资数的最后结果。个工程投资数的最后结果。 上节上节 下节下节对于一般问题设计对于一般问题设计算法算法如下如下：main( ) main( ) int int i,j,k,m,n,rest;i,j,k,m,n,rest; i

60、nt int a100100a100100，gain100;gain100; float q100,f100,temp100; float q100,f100,temp100; print(“How print(“How mangmang item? ”); input (m); item? ”); input (m); print(“How print(“How mangmang money? ”); input (n); money? ”); input (n); print(“input gain table:”); print(“input gain table:”); for( j=

61、0;j= n;j+) for( j=0;j= n;j+) input(qj); fj=qj; input(qj); fj=qj; for( j=0;j= n;j+) for( j=0;j= n;j+) a1,j=j; a1,j=j; 上节上节 下节下节for( k=2;k=m;k+)for( k=2;k=m;k+) for( j=0;j= n;j+) for( j=0;j= n;j+) tempj=qj; input(qj); akj=0; tempj=qj; input(qj); akj=0; for( j=0 ;j= n;j+) for( j=0 ;j= n;j+) for( i=0 ;i

62、=j;i+)for( i=0 ;itempjfj-i+qitempj） tempj=fj-i+qi; ak,j=i; tempj=fj-i+qi; ak,j=i; for(j=0;j= n;j+) for(j=0;j=1;i-) for(i=m;i=1;i-) gaini=airest; rest=rest-gaini; gaini=airest; rest=rest-gaini; for(i=1;i=m;i+) print(gaini,” ”); for(i=1;i=m;i+) print(gaini,” ”); print(fn); print(fn); 【例3】n个矩阵连乘的问题。 问题

63、分析 算法设计 算法1(递归算法) 算法1说明 算法2(递归算法) 算法3(非递归算法) 输出算法 上节 下节问题分析问题分析 多个矩阵连乘多个矩阵连乘运算是满足结合律的。运算是满足结合律的。例例: : M15*20 * M220*50 * M350*1 * M41*100 M15*20 * M220*50 * M350*1 * M41*100分别按分别按 (M1*M2)*M3)*M4(M1*M2)*M3)*M4，M1*(M2*(M3*M4)M1*(M2*(M3*M4)，(M1*(M2*M3)*M4(M1*(M2*M3)*M4 的次序相乘的次序相乘, ,各需进行各需进行 5750, 11500

64、0, 16005750, 115000, 1600次乘法。次乘法。 这个问题要用这个问题要用“动态规划动态规划”算法来完成算法来完成: : 首先首先, ,从两个矩阵相乘的情况开始；从两个矩阵相乘的情况开始； 然后然后, ,尝试三个矩阵相乘的情况；尝试三个矩阵相乘的情况； 最后最后, ,等到等到n n个矩阵相乘所用的最少的乘法次数及结合方式。个矩阵相乘所用的最少的乘法次数及结合方式。 上节上节 下节下节算法设计算法设计 1. 1. 阶段划分阶段划分 1 1）初始状态为一个矩阵相乘的计算量为）初始状态为一个矩阵相乘的计算量为0;0;2 2）第二阶段）第二阶段, ,计算两个相邻矩阵相乘的计算量计算两

65、个相邻矩阵相乘的计算量, , 共共n-1n-1组组3 3）第三阶段）第三阶段, ,计算两个相邻矩阵相乘的计算量计算两个相邻矩阵相乘的计算量, , 共共n-2n-2组组 4 4）最后一个阶段）最后一个阶段, ,是是n n个相邻矩阵相乘的计算量个相邻矩阵相乘的计算量, ,共共1 1组组, , 是问题解。是问题解。 上节上节 下节下节2. 2. 阶段决策阶段决策 一般地，计算一般地，计算M1*M2*M3*M1*M2*M3*Mn Mn 其中其中M1M1，M2M2，,Mi,Mi分别是分别是 r1*r2r1*r2，r2*r3r2*r3，,riri*ri+1*ri+1阶矩阵，阶矩阵，i=1,2,3,ni=1

66、,2,3,n。 设设mi,jmi,j是计算是计算Mi*Mi+1*Mi*Mi+1*MjMj的最少乘法次数的最少乘法次数(1ijn),(1ijn),对对 mi,jmi,j有公式：有公式： 0 0 当当i=ji=j时时 ri-1*ri-1*riri*ri+1 *ri+1 当当j=i+1j=i+1时时 min(mi,k+mk+1,j+rirk+1rj+1) ikj min(mi,k+mk+1,j+rirk+1rj+1) ikj 当当ijij时时 以上动态规划方法是按以上动态规划方法是按s=0,1,2,3,.,n-1s=0,1,2,3,.,n-1的顺序计算的顺序计算mi,i+smi,i+s的。的。3.3

67、.记录最佳期方案记录最佳期方案 用二维矩阵用二维矩阵comijcomij(n*n)(n*n)来存储使来存储使mijmij为最小值时的为最小值时的 k k 值。值。 上节上节 下节下节算法算法1 1( (递归算法递归算法) )intr100,com100100;main（）intn,i;print(“Howmangmatrixes?”);input(n);peint(“Howsizeeverymatrixe?”);for(i=1;i=n+1;i+)input(ri);print(“Theleastcalculatequantity：”,course(1,n);for(i=1;i=n;i+)pri

68、nt(“换行符”);for(j=1;j=n;j+)print(comij); 上节 下节intcourse(inti,intj)intu,t;if(i=j)return0;if(i=j-1)comii+1=i;return（ri*ri+1*rr+2）;u=course(i,i)+course(i+1,j)+ri*ri+1*rj+1;comij=i;for(intk=i+1;kj;k+)t=course(i,k)+course(k+1,j)+ri*rk+1*rj+1;if(tu)u=t;comij=k;returnu; 上节 下节算法算法1 1说明说明 以上的递归算法虽然解决了问题，但效率很低，

69、有子问题重叠，n=4时的递归过程如下图： 上节 下节算法算法2 2( (改进后递归算法改进后递归算法) )intm100100,com100100,r100;matrix2（）intn,;print(“Howmangmatrixes?”);input(n);print(“Howsizeeverymatrixe?”);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(“Theleastcalculatequantity：”m1n

70、);for(i=1;i=n;i+)print(“换行符换行符”);for(j=1;j0）returnmij;if(i=j)return0;if(i=j-1)comii+1=i;mij=ri*ri+1*ri+2;returnmij;intu=course(i,i)+course(i+1,j)+ri*ri+1*rj+1;comij=i;for(intk=i+1;kj;k+)intt=course(i,k)+course(k+1,j)+ri*rk+1*rj+1;if(tu)u=t;comij=k;mij=u;returnu; 上节 下节算法算法3 3( (非递归算法非递归算法) )main（）int

71、n,r100,m100100,com100100;peint(“Howmangmatrixes?”);input(n);peint(“Howsizeeverymatrixe?”);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;for(i=1;in;i+)mii=0;s=0mii+1=ri*ri+1*ri+2;s=1comii+1=i+1; 上节 下节mnn=0;for(s=2;s=n-1;s+)/动态规划过程动态规划过程/for(i=1;in-s+1;i+)j=i+s;mij=mii

72、+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(tmij)mij=t;comij=k;print(“Theleastcalculatequantity：”m1n);for(i=1;i=n;i+)print(“换行符换行符”);for(j=1;j=n;j+)print(comij); 上节 下节输出部分的算法设计以上算法中关于矩阵相乘的结合方式，只是简单的输出了数组com的内容，不容易直观地被利用，还需要继续进行必要的人工处理，才能真正找到矩阵相乘的结合方式。怎么样更直观、合理地输出结合过程？即算法的

73、输出能使用户直接了解计算矩阵的过程。首先看一下com数组存储的信息意义，它是一个二维数组，元素comij存储的是MiMj相乘的组合点k1，也就是说：Mi*Mi+1*Mj是由 Mi*Mi+1*Mk和Mk+1*Mj同样，在数组com中我们也能找到MiMk相乘的组合点k2，Mk+1Mj相乘的组合点k3，。从数组信息中找到了大规模问题与小规模问题的递归关系：输出算法输出算法 记记k1=com1nk1=com1n，则最后一次运算的结合过程是则最后一次运算的结合过程是 M1*M1*Mk1*Mk1和和Mk1+1*Mk1+1* *MnMn 记记k2=com1k1k2=com1k1，M1*M1*Mk1*Mk1的

74、结合过程是的结合过程是 M1*M1*Mk2*Mk2和和Mk2+1*Mk2+1*Mk1*Mk1 combine(inti,intj)if(i=j)return;combine(i,comij);combine(comij+1,j);print（M,i,“*M”，comij）;print（andM,comij+1,“*M”，j）; 上节 下节 这这一一节节问问题题的的设设计计角角度度是是从从递递推推思思想想进进行行的的, ,设设计计中中只只要要找找出出大大规规模模问问题题与与小小规规模模问问题题( (子子问问题题) )之之间间的的递递推推关关系系, ,最最后后一一个个子问题所得最优解就是原问题的最

75、优解。子问题所得最优解就是原问题的最优解。 【例例4 4】求两个字符序列的最长公共字符子序列求两个字符序列的最长公共字符子序列。 【例例5 5】最长不降子序列最长不降子序列。 上节上节 下节下节4.5.4 4.5.4 突出递推的动态规划应用突出递推的动态规划应用【例例4 4】求两个字符序列的最长公共字符子序 列。 问题分析 算法设计 算法(递归形式) 算法(非递归) 上节 下节问题分析问题分析 若若A A的长度为的长度为n n，若，若B B的长度为的长度为m m，则则 A A的子序列共有：的子序列共有： Cn1+Cn2+ Cn3+Cn1+Cn2+ Cn3+CnnCnn=2n-1=2n-1 B

76、B的子序列共有：的子序列共有： Cm1+Cm2+ Cm3+Cm1+Cm2+ Cm3+CmmCmm=2m-1=2m-1 如采用枚举策略，当如采用枚举策略，当m=nm=n时，共进行串比较：时，共进行串比较：Cn1*Cm1+Cn2*Cm2+Cn3*Cm3+Cn1*Cm1+Cn2*Cm2+Cn3*Cm3+CnnCnn* *CnnCnn22n 0,i,j0,且且ai-1=bj-1ai-1=bj-1； 3 3）cij=max(cij-1,ci-1j)cij=max(cij-1,ci-1j) 如果如果i,j0,i,j0,且且ai-1bj-1ai-1bj-1。 上节上节 下节下节算法算法( (递归形式递归形式

77、) )intNum=100charaNum,bNum,strNum;main()intm,n,k;print(“Entertwostring”);input(a,b);m=strlen(a);n=strlen(b),k=lcs_len(n,m);buile_lcs(k,n,m);print(str); 上节上节 下节下节lcs_len(inti，j)/计算最优值计算最优值if(i=0orj=0)cij=0;elseif(ai-1=bj-1)cij=lcs_len(i-1，j-1)+1;elsecij=max（lcs_len(i，j-1)，lcs_len(i-1，j);buile_lcs(k,i

78、,j);/构造最长公共子序列构造最长公共子序列if（i=0orj=0）return;if（cij=ci-1j）buile_lcs(k,i-1,j);elseif（cij=cij-1）buile_lcs(k,i,j-1);elsestrk=ai-1;buile_lcs(k-1,i-1,j-1); 上节上节 下节下节算法算法( (非递归非递归) )n=100charan,bn,strn;lcs_len(chara,charb,intcn)/计算最优值计算最优值intm,n,i,j;print(“Entertwostring”);input(a,b);m=strlen(a);n=strlen(b);

79、for(i=0;i=m;i+)ci0=0;for(i=0;i=n;i+)c0i=0;for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;elsecij=cij-1; buile_lcs()/构造最构造最长长公共子序列公共子序列intk,i=strlen(a),j=strlen(b);k=lcs_len();strk=;while(k0)if(cij=ci-1j)i=i-1;elseif(cij=cij-1)j=j-1;elsek=k-1;strk=ai-1;j=j-1; 上节上节 下节下节【例例5 5】最长不降子序列最长不降子序列 设有由设有由n n个不相同的整数

80、组成的数列，记为个不相同的整数组成的数列，记为: : a(1) a(1)、a(2)a(2)、a(n)a(n)且且a(i)a(j) (ij)a(i)a(j) (ij) 若若存存在在i1i2i3 i1i2i3 ik ik 且且有有a(i1)a(i2) a(i1)a(i2) a(a(ikik) )，则称为长度为则称为长度为k k的不下降序列。请求出一个数列的最长不下降序列。的不下降序列。请求出一个数列的最长不下降序列。 算法设计算法设计 算法算法( (逆推法逆推法) ) 上节上节 下节下节算法设计算法设计1. 1. 递推关系递推关系 1) 1) 对对a(n)a(n)来说，由于它是最后一个数，所以当从

81、来说，由于它是最后一个数，所以当从a(n)a(n)开始查找开始查找 时时, ,只存在长度为只存在长度为1 1的不下降序列；的不下降序列； 2) 2) 若从若从a(n-1)a(n-1)开始查找，则存在下面的两种可能性：开始查找，则存在下面的两种可能性： (1)(1)若若a(n-1)a(n)a(n-1)a(n)a(n-1)a(n)则存在长度为则存在长度为1 1的不下降序列的不下降序列a(n-1)a(n-1)或或a(n)a(n)。 3) 3) 一般若从一般若从a(i)a(i)开始开始, ,此时最长不下降序列应该按下列方法求出此时最长不下降序列应该按下列方法求出: : 在在a(i+1),a(i+2),

82、a(i+1),a(i+2),a(n),a(n)中，找出一个比中，找出一个比a(i)a(i)大的且最大的且最 长的不下降序列，作为它的后继。长的不下降序列，作为它的后继。 上节上节 下节下节算法算法( (逆推法逆推法) )int maxnint maxn=100;=100;intint a amaxnmaxn,b,bmaxnmaxn,c,cmaxnmaxn;main() main() intint n,i,j,max,p; n,i,j,max,p; input(n); input(n); for (i = 1;i n;i+) for (i = 1;i =1;i=i-1)max=0;p=0;for

83、(j=i+1;j=n;j=j+1)if(aimax)max=bj;p=j;if(p0)bi=bp+1;ci=p;max=0;p=0;for(i=1;imax)max:=bi;p:=i;print(maxlong=,max);print(resultis:);while(p0)print(ap);p:=cp; 上节 下节 算算法法策策略略和和算算法法是是有有区区别别的的, ,它它们们是是算算法法设设计计中中的的两两个个方方面面，算算法法策策略略是是面面向向问问题题的的, ,算算法法是是面面向向实实现现的的；但但二二者者又又是是不不可可分分的的, ,首首先先是是通通过过算算法法策策略略才才找找出出

84、解解决决问问题题的的算算法法，其其次次对于用不同算法求解的问题算法策略是自然不同的。对于用不同算法求解的问题算法策略是自然不同的。 本本章章共共介介绍绍了了五五种种算算法法策策略略, ,它它们们互互相相有有着着一一定定的的差差别别，适应的问题也有所差异。适应的问题也有所差异。 上节上节 下节下节4.6 4.6 算法策略间的比较算法策略间的比较“贪婪算法贪婪算法” “递推法递推法” “递归法递归法” “枚举法枚举法” “递归回朔法递归回朔法” “分治法分治法” “动态规划法动态规划法” 上节上节 下节下节4.6.1 4.6.1 不同算法策略特点小结不同算法策略特点小结“贪婪算法贪婪算法” 这这些

85、些策策略略求求解解的的是是最最简简单单的的一一类类问问题题，或或者者说说是是对对问问题题要要求求最最严严格格的的算算法法策策略略。“贪贪婪婪算算法法”解解决决这这类类问问题题是是按按一一定定顺顺序序（从从前前向向后后或或从从后后向向前前等等）一一定定的的策策略略，只只需需考考虑虑当当前前局局部部信信息息就就能能做做出出决决策策，即即所所谓谓局局部部最最优优就就是是全全局最优。局最优。 上节上节 下节下节“递推法递推法” “递递推推法法”和和贪贪婪婪算算法法一一样样也也是是由由当当前前问问题题的的逐逐步步解解决决从从而而得得到到整整个个问问题题的的解解，只只是是依依赖赖的的是是信信息息间间本本身

86、身的的递递推推关关系，每一步不需要策略参与到算法中，它们更多地用于计算。系，每一步不需要策略参与到算法中，它们更多地用于计算。 上节上节 下节下节“递归法递归法” 和和递递推推法法类类似似，递递归归法法是是利利用用大大问问题题与与其其子子问问题题间间的的递递归归关关系系来来解解决决问问题题的的。能能采采用用递递归归描描述述的的算算法法通通常常有有这这样样的的特特征征：为为求求解解规规模模为为N N的的问问题题，设设法法将将它它分分解解成成规规模模较较小小的的问问题题，然然后后从从这这些些小小问问题题的的解解方方便便地地构构造造出出大大问问题题的的解解，并并且且这这些些规规模模较较小小的的问问题

87、题也也能能采采用用同同样样的的分分解解和和综综合合方方法法，分分解解成成规规模模更更小小的的问问题题，并并从从这这些些更更小小问问题题的的解解构构造造出出规规模模较较大问题的解。特别地，当规模大问题的解。特别地，当规模N=1N=1时，能直接得解。时，能直接得解。 上节上节 下节下节“枚举法枚举法” 枚枚举举法法既既是是一一个个策策略略，也也是是一一个个算算法法，也也是是一一个个分分析析问问题题的的手手段段。枚枚举举法法的的求求解解思思路路很很简简单单, ,就就是是对对所所有有可可能能的的解解逐逐一一尝尝试试，从从而而找找出出问问题题的的真真正正解解。当当然然这这就就要要求求所所解解的的问问题题

88、可可能能的的解解是是有有限限的的、固固定定的的，不不会会产产生生组组合合爆爆炸炸、容容易易枚枚举举的的。多多用用于于决决策策类类问问题题。这这类类问问题题都都不不易易进进行行问问题题的的分分解解，只只能能整整体体来求解来求解。 上节上节 下节下节“递归回朔法递归回朔法” 类类似似于于枚枚举举法法的的思思想想, ,递递归归回回朔朔法法通通过过递递归归尝尝试试遍遍问问题题各各个个可可能能解解的的通通路路，发发现现此此路路不不通通时时回回朔朔到到上上一一步步继继续续尝尝试试别的通路。在下一章中对其应用做详细介绍。别的通路。在下一章中对其应用做详细介绍。 上节上节 下节下节“分治法分治法” 求求解解的

89、的则则是是较较复复杂杂的的问问题题，这这类类问问题题是是可可以以被被分分解解成成独独立立的的子子问问题题来来解解决决的的，将将两两个个或或两两个个以以上上的的独独立立子子问问题题的的解解“合合成成”，就就得得到到较较大大的的子子问问题题的的解解，最最后后合合成成为为总总问问题题的的解。解。 上节上节 下节下节“动态规划法动态规划法” 动动态态规规划划法法与与贪贪心心法法类类似似，是是通通过过多多阶阶段段决决策策过过程程来来解解决决问问题题的的。但但每每个个阶阶段段决决策策的的结结果果是是一一个个决决策策结结果果序序列列，这这个个结结果果序序列列中中最最后后采采用用哪哪一一个个结结果果取取决决于

90、于以以后后每每个个阶阶段段决决策策，因因此此称称为为“动动态态”规规划划法法。当当然然每每一一次次的的决决策策结结果果序序列列都都必必须须进进行行存存储储。因因此此，可可以以说说“动动态态规规划划是是高高效效率率、高高消消费费的的算法算法”。 另另一一方方面面，动动态态规规划划法法与与分分治治法法类类似似，当当问问题题不不能能分分解解为为独独立立的的子子问问题题, ,但但又又符符合合最最优优化化原原理理( (最最优优子子结结构构性性质质) )时时, ,用用动动态态规规划划，通通过过多多阶阶段段决决策策过过程程从从逐逐步步找找出出子子问问题题的的最最优优解，从而决策出问题的结果。解，从而决策出问

91、题的结果。 上节上节 下节下节 1. 1. 对问题进行分解的算法策略对问题进行分解的算法策略-分治法分治法 与与 动态规划法动态规划法 2. 2. 多阶段过程多阶段过程 贪婪算法贪婪算法 、 递推法递推法 、 递归法递归法 和和 动态规划法动态规划法 3. 3. 全面逐一尝试、比较全面逐一尝试、比较 蛮力法蛮力法 、 枚举法枚举法 、 递归回溯法递归回溯法 4 4算法策略的中心思想算法策略的中心思想 上节上节 下节下节4.6.2 4.6.2 算法策略间的关联算法策略间的关联1.对问题进行分解的算法策略 -“分治法”与“动态规划法” “分治法”与“动态规划法”都是递归思想的应用之一，是找出大问题

92、与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。区别在于： 上节 下节分治法分治法所能解决的问题一般具有以下几个特征：所能解决的问题一般具有以下几个特征： 1) 1) 该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决； 2) 2) 该问题可以分解为若干个规模较小的相同问题，即该问该问题可以分解为若干个规模较小的相同问题，即该问 题具有。题具有。 3) 3) 利用该问题分解出的子问题的解可以合并为该问题的解利用该问题分解出的子问题的解可以合并为该问题的解; ; 4) 4) 该问题所分解出的各个子问题是相互独立的，即子问

93、题该问题所分解出的各个子问题是相互独立的，即子问题 之间不包含公共的子问题。之间不包含公共的子问题。 上节上节 下节下节第一条特征是绝大多数问题都可以满足的第一条特征是绝大多数问题都可以满足的; ; 第二条特征是应用分治法的前提第二条特征是应用分治法的前提, ,它也是大多数问题可以满足的它也是大多数问题可以满足的; ; 第三条特征是关键。第三条特征是关键。 第四条特征涉及到分治法的效率。第四条特征涉及到分治法的效率。 动态规划的动态规划的实质实质是分治思想和解决冗余。是分治思想和解决冗余。 上节上节 下节下节2 2多阶段过程多阶段过程“贪婪算法贪婪算法”、“递推法递推法”、 “递归法递归法”和

94、和“动态规划法动态规划法” 多阶段过程就是按一定顺序多阶段过程就是按一定顺序( (从前向后或从后向前等从前向后或从后向前等) )一一定的策略定的策略, , 逐步解决问题的方法。逐步解决问题的方法。 “贪婪算法贪婪算法”每一步根据策略得到一个结果传递到下一每一步根据策略得到一个结果传递到下一步，自顶向下，一步一步地作出贪心选择。步，自顶向下，一步一步地作出贪心选择。 上节上节 下节下节“动态规划法动态规划法”则根据一定的决策则根据一定的决策, , 每一步决策出的不每一步决策出的不是一个结果，而只是使问题的规模不断的缩小，如果决策比是一个结果，而只是使问题的规模不断的缩小，如果决策比较简单较简单,

95、 ,是一般的算法运算是一般的算法运算, ,则可找到不同规模问题间的关系，则可找到不同规模问题间的关系，使算法演变成使算法演变成“递推法递推法”、“递归法递归法”算法算法, ,所以说动态规划所以说动态规划更侧重算法设计策略，而不是算法。更侧重算法设计策略，而不是算法。 “递推法递推法”、“递归法递归法”更注重每一步之间的关系更注重每一步之间的关系, ,决策决策的因素较少。的因素较少。“递推法递推法”根据关系从前向后推根据关系从前向后推, ,由小规模的结由小规模的结论论, ,推解出问题的解。推解出问题的解。“递归法递归法”根据关系先从后向前使大问根据关系先从后向前使大问题，转化为小问题，最后同样由

96、小规模结论，推解出问题的题，转化为小问题，最后同样由小规模结论，推解出问题的解。解。 上节上节 下节下节3 3全面逐一尝试、比较全面逐一尝试、比较“蛮力法蛮力法”、 “枚举法枚举法”、“递归回溯法递归回溯法” 考考虑虑到到有有这这样样一一类类问问题题，问问题题中中不不易易找找到到信信息息间间的的相相互互关关系系，也也不不能能分分解解为为独独立立的的子子问问题题, ,似似乎乎只只有有把把各各种种可可能能情情况况都都考考虑虑到到, ,并并把把全全部部解解都都列列出出来来之之后后, ,才才能能判判定定和和得得到到最最优优解解。对对于于规规模模不不大大的的问问题题，这这些些策策略略简简单单方方便便;

97、;而而当当问问题题的的计计算算复复杂杂度度高高且且计计算算量量很很大大时时, ,还还是是考考虑虑采采用用“动动态态规规划划法法”这这个个更更有有效的算法策略效的算法策略。 上节 下节枚举法算法的实现枚举法算法的实现依赖于循环依赖于循环, ,通过循环嵌套枚举问题中通过循环嵌套枚举问题中各种可能的情况各种可能的情况, ,如八皇后问题能用八重循环嵌套枚举。而对如八皇后问题能用八重循环嵌套枚举。而对于规模于规模不固定不固定的问题就无法用固定重数的循环嵌套来枚举了的问题就无法用固定重数的循环嵌套来枚举了, ,有的问题可能通过变换枚举对象也能用循环嵌套枚举实现有的问题可能通过变换枚举对象也能用循环嵌套枚举

98、实现, ,但但更多的任意指定规模的问题是靠递归回朔法来更多的任意指定规模的问题是靠递归回朔法来“枚举枚举”或或“遍历遍历”各种可能的情况。比如各种可能的情况。比如n n皇后问题只能用皇后问题只能用“递归回朔法递归回朔法”通过递归实现（当然可以通过栈通过递归实现（当然可以通过栈, ,而不用递归）。而不用递归）。 上节上节 下节下节4 4算法策略的中心思想算法策略的中心思想 所所有有算算法法策策略略的的中中心心思思想想就就是是用用算算法法的的基基本本工工具具循循环环机机制制和和递递归归机机制制实实现现算算法法。递递推推法法自自然然不不用用多多说说，贪贪婪婪算算法法就就是逐步决策解决问题，动态规划也

99、是。是逐步决策解决问题，动态规划也是。 上节 下节4.4.6.3 6.3 算法策略侧重的问题类型算法策略侧重的问题类型 一般我们在实际应用中遇到的问题主要分为四类一般我们在实际应用中遇到的问题主要分为四类: :判定性问题、判定性问题、计算问题、最优化问题和构造性问题。计算问题、最优化问题和构造性问题。 递推法递推法 、 递归法递归法 算法较适合解决判定性问题、计算问题。算法较适合解决判定性问题、计算问题。 “贪婪算法贪婪算法”、“分治法分治法” ” 、“动态规划法动态规划法” ” 与与“枚举法枚举法” ” 较适合较适合解最优化问题。解最优化问题。 构造性问题更多地依赖于人的经验和抽象能力，算法

100、一般是构造性问题更多地依赖于人的经验和抽象能力，算法一般是人类智能充分对问题解决步骤细化后才能得到算法，少有通用的人类智能充分对问题解决步骤细化后才能得到算法，少有通用的算法策略。当然也有一些问题在构造过程中使用通用的算法策略。算法策略。当然也有一些问题在构造过程中使用通用的算法策略。 上节 下节下面就最优化问题讨论如下：下面就最优化问题讨论如下： 在现实生活中，有这样的问题：他有在现实生活中，有这样的问题：他有n n个输入个输入, , 而他的解就而他的解就由由n n个输入的某个子集组成，只是这个子集必须满足某些事先给个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。把那些必须满足

101、的条件称为定的条件。把那些必须满足的条件称为约束条件约束条件; ;而把满足约定而把满足约定条件的子集称为该问题的条件的子集称为该问题的可行解可行解。显然。显然, ,满足约束条件的子集可满足约束条件的子集可能不止一个能不止一个, ,因此，可行解一般来说是不唯一的。为了衡量可行因此，可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也给出了一定的标准解的优劣，事先也给出了一定的标准, ,这些标准一般以函数形式这些标准一般以函数形式给出给出, , 这些函数称为这些函数称为目标函数目标函数。 那些使目标函数取极值的可行那些使目标函数取极值的可行解，解， 称为称为最优解最优解, , 这一类需求取最优解

102、的问题这一类需求取最优解的问题, , 又可根据描述又可根据描述约束条件和目标函数的约束条件和目标函数的 数学模型的特性或求借问题方法的不同数学模型的特性或求借问题方法的不同进行而细分为进行而细分为 线形规则线形规则、整数规则整数规则、非线形规则非线形规则、动态规划动态规划等等问题。问题。 上节 下节尽管各类规划问题都有一些相应的求解方法，但其中的某尽管各类规划问题都有一些相应的求解方法，但其中的某些问题，还可用一种更直接的方法来求解，这种方法就叫些问题，还可用一种更直接的方法来求解，这种方法就叫贪心贪心方法方法。 动态规划法动态规划法是将问题实例归纳为更小的、是将问题实例归纳为更小的、 相似的

103、子问题相似的子问题, , 并通过求解子问题产生一个全局最优解。其中贪心法的当前选并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择择可能要依赖已经作出的所有选择, , 但不依赖于有待于做出的但不依赖于有待于做出的选择和子问题。选择和子问题。 而而分治法分治法中的各个子问题是独立的中的各个子问题是独立的( (即不包含即不包含公共的子子问题公共的子子问题),),因此一旦递归地求出各子问题的解后，便可因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是自下而上地将子问题的解合并成问题的解。但不足的是, , 如果如果当前选择可能要依赖

104、子问题的解时当前选择可能要依赖子问题的解时, , 则难以通过局部的贪心策则难以通过局部的贪心策略达到全局最优解略达到全局最优解; ;如果各子问题是不独立的如果各子问题是不独立的, ,则分治法要做许则分治法要做许多不必要的工作多不必要的工作, ,重复地解公共的子问题。重复地解公共的子问题。 上节上节 下节下节动态规划在解决不独立子问题时，是分为若干个阶段进行动态规划在解决不独立子问题时，是分为若干个阶段进行的的, ,而且在任一阶段后的行为都仅依赖而且在任一阶段后的行为都仅依赖i i阶段的过程状态阶段的过程状态, , 而与而与i i阶段之前的过程如何达到这种状态的方法无关阶段之前的过程如何达到这种

105、状态的方法无关, ,这样的过程就构这样的过程就构成一个成一个多阶段决策过程多阶段决策过程。 动态规划不仅求出了当前状态到目标动态规划不仅求出了当前状态到目标状态的最优值状态的最优值, ,而且同时求出了到中间状态的最优值。而且同时求出了到中间状态的最优值。 显然显然, ,用枚举的方法从所有可能的决策序列中选取最优决策用枚举的方法从所有可能的决策序列中选取最优决策序列是一种最笨的方法。序列是一种最笨的方法。 上节上节 下节下节最优性原理最优性原理指出指出, , 过程的过程的最优序列最优序列有如下性质：无论过程的有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策初始状态和

106、初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。所产生的状态构成一个最优决策序列。 如果求解问题的最优性原理成立如果求解问题的最优性原理成立, , 则说明用动态规划方法有则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获得各阶段间的递推关可能解决该问题。而解决问题的关键在于获得各阶段间的递推关系式。因此系式。因此, , 从某种意义上说从某种意义上说动态规划是一种找出子问题间递推动态规划是一种找出子问题间递推或递归关系的方法或递归关系的方法。 动态规划相比一般穷举也存在一定动态规划相比一般穷举也存在一定缺点缺点: :空间占据过多空间占据过多, ,但对但对于空间需求量不大的题目来说于空间需求量不大的题目来说, ,动态规划无疑是最佳方法！动态规划无疑是最佳方法！ 上节 下节