1、4.4 4.4 貪婪算法貪婪算法最優(yōu)化問(wèn)題：最優(yōu)化問(wèn)題：有有n個(gè)輸入，它的解由這個(gè)輸入，它的解由這n個(gè)輸入的一個(gè)子集組成，這個(gè)輸入的一個(gè)子集組成，這個(gè)子集必須滿足某些事先給定的條件，這些條件稱為個(gè)子集必須滿足某些事先給定的條件，這些條件稱為約束約束條件條件，滿足約束條件的解稱為問(wèn)題的，滿足約束條件的解稱為問(wèn)題的可行解可行解。滿足約束條。滿足約束條件的可行解可能不只一個(gè)，為了衡量這些可行解的優(yōu)劣，件的可行解可能不只一個(gè)，為了衡量這些可行解的優(yōu)劣，事先給出一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)通常以函數(shù)的形式給出，事先給出一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)通常以函數(shù)的形式給出，這些標(biāo)準(zhǔn)函數(shù)稱為這些標(biāo)準(zhǔn)函數(shù)稱為目標(biāo)函數(shù)目標(biāo)函數(shù)，使

2、目標(biāo)函數(shù)取得極值（極大，使目標(biāo)函數(shù)取得極值（極大或極小）的可行解稱為或極小）的可行解稱為最優(yōu)解最優(yōu)解，這類問(wèn)題就稱為，這類問(wèn)題就稱為最優(yōu)化問(wèn)最優(yōu)化問(wèn)題題。 貪婪法又叫登山法貪婪法又叫登山法, , 它的根本思想是逐步到達(dá)山頂它的根本思想是逐步到達(dá)山頂, ,即逐步獲得最優(yōu)解。貪婪算法沒(méi)有固定的算法框架，算法即逐步獲得最優(yōu)解。貪婪算法沒(méi)有固定的算法框架，算法設(shè)計(jì)的關(guān)鍵是貪婪策略的選擇。一定要注意，選擇的貪婪設(shè)計(jì)的關(guān)鍵是貪婪策略的選擇。一定要注意，選擇的貪婪策略要具有無(wú)后效性。某狀態(tài)以后的過(guò)程和不會(huì)影響以前策略要具有無(wú)后效性。某狀態(tài)以后的過(guò)程和不會(huì)影響以前的狀態(tài)的狀態(tài), ,只與當(dāng)前狀態(tài)或以前的狀態(tài)有關(guān)

3、只與當(dāng)前狀態(tài)或以前的狀態(tài)有關(guān), ,稱這種特性為無(wú)稱這種特性為無(wú)后效性。后效性。4.4 貪婪算法【例【例4 4】幣種統(tǒng)計(jì)問(wèn)題幣種統(tǒng)計(jì)問(wèn)題 某單位給每個(gè)職工發(fā)工資（精確到元）。為了保證不要臨某單位給每個(gè)職工發(fā)工資（精確到元）。為了保證不要臨時(shí)兌換零錢(qián)時(shí)兌換零錢(qián), , 且取款的張數(shù)最少，取工資前要統(tǒng)計(jì)出所有職工且取款的張數(shù)最少，取工資前要統(tǒng)計(jì)出所有職工的工資所需各種幣值的工資所需各種幣值(100,50,20,10,5,2,1(100,50,20,10,5,2,1元共七種元共七種) )的張數(shù)。的張數(shù)。請(qǐng)編程完成。請(qǐng)編程完成。 算法設(shè)計(jì)算法設(shè)計(jì) 算法說(shuō)明算法說(shuō)明 算法分析算法分析 貪婪策略貪婪策略 算法

4、設(shè)計(jì)算法設(shè)計(jì) 1) 1) 從鍵盤(pán)輸入每人的工資。從鍵盤(pán)輸入每人的工資。 2) 2) 對(duì)每一個(gè)人的工資，用對(duì)每一個(gè)人的工資，用“貪婪貪婪”的思想，先盡量多地取大的思想，先盡量多地取大面額的幣種，由大面額到小面額幣種逐漸統(tǒng)計(jì)。面額的幣種，由大面額到小面額幣種逐漸統(tǒng)計(jì)。 3) 3) 利用數(shù)組應(yīng)用技巧利用數(shù)組應(yīng)用技巧, ,將七種幣值存儲(chǔ)在數(shù)組將七種幣值存儲(chǔ)在數(shù)組B B。這樣，七種。這樣，七種 幣值就可表示為幣值就可表示為Bi,i=1,2,3,4,5,6,7Bi,i=1,2,3,4,5,6,7。為了能實(shí)現(xiàn)貪。為了能實(shí)現(xiàn)貪婪婪策略，策略，七種幣應(yīng)該從大面額的幣種到小面額的幣種依次存儲(chǔ)。七種幣應(yīng)該從大面額的

5、幣種到小面額的幣種依次存儲(chǔ)。 4) 4) 利用數(shù)組技巧利用數(shù)組技巧, ,設(shè)置一個(gè)有設(shè)置一個(gè)有7 7個(gè)元素的累加器數(shù)組個(gè)元素的累加器數(shù)組S S。 算法算法main( )main( ) int i,j,n,GZ,A int i,j,n,GZ,A； int B8=0,100,50,20,10,5,2,1,S8;int 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;

6、A=GZ/Bj; Sj=Sj+A; Sj=Sj+A; GZ=GZ-A GZ=GZ-A* *Bj;Bj; for(i=1;i=7;i+) for(i=1;i=7;i+) print(Bi, “-”, Si); print(Bi, “-”, Si); 算法說(shuō)明算法說(shuō)明 每求出一種面額所需的張數(shù)后， 一定要把這部分金額減去：“GZ=GZ-A*Bj;”,否則將會(huì)重復(fù)計(jì)算。算法分析算法分析 算法的時(shí)間復(fù)雜性是O（n）。 解決問(wèn)題的貪婪策略：解決問(wèn)題的貪婪策略： 以上問(wèn)題的背景是在我國(guó)以上問(wèn)題的背景是在我國(guó), ,題目中不提示我們也知道有哪題目中不提示我們也知道有哪些幣種些幣種, ,且這樣的幣種正好適合使用

7、貪婪算法且這樣的幣種正好適合使用貪婪算法( (感興趣的讀者可感興趣的讀者可以 證 明 這 個(gè) 結(jié) 論以 證 明 這 個(gè) 結(jié) 論 ) ) 。 假 若。 假 若 , , 某 國(guó) 的 幣 種 是 這 樣 的某 國(guó) 的 幣 種 是 這 樣 的 , , 共共 9 9種種:100,70,50,20,10,7,5,2,1:100,70,50,20,10,7,5,2,1。在這樣的幣值種類下。在這樣的幣值種類下, ,再用貪再用貪婪 算 法 就 行 不 通 了婪 算 法 就 行 不 通 了 , , 比 如 某 人 工 資 是比 如 某 人 工 資 是 1 4 0 ,1 4 0 , 按 貪 婪 算 法按 貪 婪 算

8、 法140=100140=100* *(1(1張張)+20)+20* *(2(2張張) )共需要共需要3 3張張, ,而事實(shí)上而事實(shí)上, ,只要取只要取2 2張張7070面面額的是最佳結(jié)果額的是最佳結(jié)果, ,這類問(wèn)題可以考慮用動(dòng)態(tài)規(guī)劃算法來(lái)解決。這類問(wèn)題可以考慮用動(dòng)態(tài)規(guī)劃算法來(lái)解決。 由此，在用貪婪算法策略時(shí)，最好能用數(shù)學(xué)方法證明每一由此，在用貪婪算法策略時(shí)，最好能用數(shù)學(xué)方法證明每一步的策略是否能保證得到最優(yōu)解。步的策略是否能保證得到最優(yōu)解。 打地鼠打地鼠-ACM程序設(shè)計(jì)比賽題目程序設(shè)計(jì)比賽題目n相信大家都玩過(guò)打地鼠游戲吧！就是在一個(gè)相信大家都玩過(guò)打地鼠游戲吧！就是在一個(gè)n n* *m m矩形

9、區(qū)域內(nèi)有矩形區(qū)域內(nèi)有n n* *m m個(gè)洞，然后地鼠可能在任意一個(gè)洞中出來(lái)。現(xiàn)在一個(gè)小朋友正在個(gè)洞，然后地鼠可能在任意一個(gè)洞中出來(lái)。現(xiàn)在一個(gè)小朋友正在玩這個(gè)游戲，他不想像正常玩游戲一樣，要自己看著，現(xiàn)在他要玩這個(gè)游戲，他不想像正常玩游戲一樣，要自己看著，現(xiàn)在他要買(mǎi)一些機(jī)器人來(lái)幫他，這些機(jī)器人很厲害，一個(gè)就可以頂上十個(gè)，買(mǎi)一些機(jī)器人來(lái)幫他，這些機(jī)器人很厲害，一個(gè)就可以頂上十個(gè)，原因很簡(jiǎn)單，他可以打中所有出現(xiàn)在和它同行或同列的地鼠，但原因很簡(jiǎn)單，他可以打中所有出現(xiàn)在和它同行或同列的地鼠，但是他也有個(gè)弊端，一旦放到一個(gè)位置了就不能在動(dòng)了，而且這些是他也有個(gè)弊端，一旦放到一個(gè)位置了就不能在動(dòng)了，而且這

10、些機(jī)器人只能放在矩形的外圍。當(dāng)然了，他也想省點(diǎn)錢(qián)，現(xiàn)在他已機(jī)器人只能放在矩形的外圍。當(dāng)然了，他也想省點(diǎn)錢(qián)，現(xiàn)在他已經(jīng)計(jì)算出了地鼠將要出現(xiàn)的位置，要你幫他計(jì)算一下他最少要買(mǎi)經(jīng)計(jì)算出了地鼠將要出現(xiàn)的位置，要你幫他計(jì)算一下他最少要買(mǎi)多少個(gè)機(jī)器人。多少個(gè)機(jī)器人。nInputInputn輸入包括多組數(shù)據(jù)。首先輸入輸入包括多組數(shù)據(jù)。首先輸入n n和和m(1=n,m=300)m(1=n,m=300)代表矩形的大小，代表矩形的大小，接下來(lái)一行輸入接下來(lái)一行輸入k(1=k=nk(1=k=n* *m)m)，表示有，表示有k k個(gè)位置地鼠將出現(xiàn)的，然個(gè)位置地鼠將出現(xiàn)的，然后跟著后跟著k k行，每一行包括兩個(gè)數(shù)行，每

11、一行包括兩個(gè)數(shù)x(1=x=n)x(1=x=n)和和y(1=y=m)y(1=y=m)，表示，表示k k個(gè)可能的位置。當(dāng)錄入的個(gè)可能的位置。當(dāng)錄入的n= m=0n= m=0時(shí)，程序結(jié)束。時(shí)，程序結(jié)束。nOutputn輸出最少的機(jī)器人數(shù)，每組數(shù)據(jù)占一行，相鄰的兩組用空格隔開(kāi)。nSample Inputn5 5n3n1 2n2 3n4 5n6 5n5n1 2n1 3n2 3n3 3n6 4nSample Outputn3n n3 【例【例1 1】鍵盤(pán)輸入一個(gè)高精度的正整數(shù)鍵盤(pán)輸入一個(gè)高精度的正整數(shù)N N，去掉其中任意，去掉其中任意S S個(gè)數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。個(gè)數(shù)字后剩下的

12、數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的編程對(duì)給定的N N和和S S，尋找一種方案使得剩下的數(shù)字組成的新，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。數(shù)最小。 輸入數(shù)據(jù)均不需判錯(cuò)。輸出應(yīng)包括所去掉的數(shù)字的位置輸入數(shù)據(jù)均不需判錯(cuò)。輸出應(yīng)包括所去掉的數(shù)字的位置和組成的新的正整數(shù)（和組成的新的正整數(shù)（N N不超過(guò)不超過(guò)240240位）。位）。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：對(duì)高精度正整數(shù)的運(yùn)算在上一節(jié)我們剛剛接數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：對(duì)高精度正整數(shù)的運(yùn)算在上一節(jié)我們剛剛接觸過(guò)，和那里一樣，將輸入的高精度數(shù)存儲(chǔ)為字符串格式。觸過(guò)，和那里一樣，將輸入的高精度數(shù)存儲(chǔ)為字符串格式。根據(jù)輸出要求設(shè)置數(shù)組，在刪除數(shù)字時(shí)記錄其位置。

13、根據(jù)輸出要求設(shè)置數(shù)組，在刪除數(shù)字時(shí)記錄其位置。 4.4.1 可絕對(duì)貪婪問(wèn)題 問(wèn)題分析問(wèn)題分析 在位數(shù)固定的前提下，讓高位的數(shù)字盡量小其值就較小，依據(jù)在位數(shù)固定的前提下，讓高位的數(shù)字盡量小其值就較小，依據(jù)此貪婪策略就可以解決這個(gè)問(wèn)題。此貪婪策略就可以解決這個(gè)問(wèn)題。具體地相鄰兩位比較若高位比低位大則刪除高位。我們通過(guò)具體地相鄰兩位比較若高位比低位大則刪除高位。我們通過(guò)“枚枚舉歸納舉歸納”設(shè)計(jì)算法的細(xì)節(jié)，看一個(gè)實(shí)例（設(shè)計(jì)算法的細(xì)節(jié)，看一個(gè)實(shí)例（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

14、”6比比3大大 刪除刪除 “1 2 3 5 3”下一個(gè)實(shí)例：下一個(gè)實(shí)例： 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” 由實(shí)例由實(shí)例n1，相鄰數(shù)字只需要從前向后比較；而從實(shí)例，相鄰數(shù)字只需要從前向后比較；而從實(shí)例n2中可以看出當(dāng)?shù)谥锌梢钥闯霎?dāng)?shù)趇位與第位與第i+1位比較，若刪除第位比較，若刪除第i位后，必須向位后，必須向前考慮第前考慮第i-1位與第位與第i+1位進(jìn)行比較，才能保證結(jié)果的正確性。位進(jìn)行比較，才能保證結(jié)果的正確性。再如：再如：n3=”1 2 3 4 5 6 7”

15、s=3 由這個(gè)實(shí)例看出，經(jīng)過(guò)對(duì)由這個(gè)實(shí)例看出，經(jīng)過(guò)對(duì)n3相鄰比較一個(gè)數(shù)字都沒(méi)有刪除，相鄰比較一個(gè)數(shù)字都沒(méi)有刪除，這就要考慮將這就要考慮將后三位后三位進(jìn)行刪除，當(dāng)然還有可能，在相鄰比較的進(jìn)行刪除，當(dāng)然還有可能，在相鄰比較的過(guò)程中刪除的位數(shù)小于過(guò)程中刪除的位數(shù)小于s時(shí)，也要進(jìn)行相似的操作。時(shí)，也要進(jìn)行相似的操作。 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” 得到的新數(shù)數(shù)據(jù)是得到的新數(shù)數(shù)據(jù)是3算法設(shè)計(jì)算法設(shè)計(jì)1： 根據(jù)以上實(shí)例分析，算法主要由四部分組成：初始化、相根據(jù)以上實(shí)例分析

16、，算法主要由四部分組成：初始化、相鄰數(shù)字比較（必要時(shí)刪除）、處理比較過(guò)程中刪除不夠鄰數(shù)字比較（必要時(shí)刪除）、處理比較過(guò)程中刪除不夠s位的情位的情況和結(jié)果輸出。況和結(jié)果輸出。 其中刪除字符的實(shí)現(xiàn)方法很多，如：其中刪除字符的實(shí)現(xiàn)方法很多，如： 1 1）物理進(jìn)行字符刪除，就是用后面的字符覆蓋已刪除的字）物理進(jìn)行字符刪除，就是用后面的字符覆蓋已刪除的字符，字符串長(zhǎng)度改變。這樣可能會(huì)有比較多字符移動(dòng)操作，符，字符串長(zhǎng)度改變。這樣可能會(huì)有比較多字符移動(dòng)操作，算法效率不高。算法效率不高。2） 可以利用數(shù)組記錄字符的存在狀態(tài)，元素值為可以利用數(shù)組記錄字符的存在狀態(tài)，元素值為“1”表表示對(duì)應(yīng)數(shù)字存在，元素值為示

17、對(duì)應(yīng)數(shù)字存在，元素值為“0”表示對(duì)應(yīng)數(shù)字已刪除。這表示對(duì)應(yīng)數(shù)字已刪除。這樣避免了字符的移動(dòng)樣避免了字符的移動(dòng)，字符串長(zhǎng)度不會(huì)改變，可以省略專，字符串長(zhǎng)度不會(huì)改變，可以省略專門(mén)記錄刪除數(shù)字的位置。但這樣做前后數(shù)字的比較過(guò)程和門(mén)記錄刪除數(shù)字的位置。但這樣做前后數(shù)字的比較過(guò)程和最后的輸出過(guò)程相對(duì)復(fù)雜一些。最后的輸出過(guò)程相對(duì)復(fù)雜一些。3） 同樣還是利用數(shù)組，記錄未刪除字符的下標(biāo)，粗略的過(guò)同樣還是利用數(shù)組，記錄未刪除字符的下標(biāo)，粗略的過(guò)程如下：程如下： n=“1 2 4 3 5 8 3 3” 1 2 3 4 5 6 7 8 4比比3大大 刪除刪除 “1 2 3 5 8 3 3” 1 2 4 5 6 7

18、8 8比比3大大 刪除刪除 “1 2 3 5 3 3” 1 2 4 5 7 8 5比比3大大 刪除刪除 “1 2 3 3 3” 1 2 4 7 8這時(shí)數(shù)組好象是數(shù)據(jù)庫(kù)中的索引文件。此方式同樣存在操作這時(shí)數(shù)組好象是數(shù)據(jù)庫(kù)中的索引文件。此方式同樣存在操作比較復(fù)雜的問(wèn)題。我們采用方法比較復(fù)雜的問(wèn)題。我們采用方法1）。）。 一種簡(jiǎn)單的控制相鄰數(shù)字比較的方法是每次從頭開(kāi)始，一種簡(jiǎn)單的控制相鄰數(shù)字比較的方法是每次從頭開(kāi)始，最多刪除最多刪除s s次，也就從頭比較次，也就從頭比較s s次。按題目要求次。按題目要求設(shè)置數(shù)組設(shè)置數(shù)組data記錄刪除的數(shù)字所在位置記錄刪除的數(shù)字所在位置delete(char n,i

19、nt b,int k)int i; for(i=b;ilen) print(“data error”); 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; /記錄刪除數(shù)字位置記錄刪除數(shù)字位置 else /實(shí)例實(shí)例2向前刪除的情況實(shí)例向前刪除的情況實(shí)例 datai=datai-1-1; j1=j; break; if( jlength(n) break;for (i=1;i=s;i=i+1)for (i=1;i1) delete(n,1,1); /將字符串首的若

20、干個(gè)將字符串首的若干個(gè)“0”去掉去掉 print(n);for (i=1;ilen) print(“data error”); return;i=0; j=1; j1=0;while(is and j=length(n)-1) while(nj=nj+1) j=j+1; if (jj1) datai=j+i; else datai=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, ); 算法說(shuō)明算法說(shuō)明2：

21、同算法：同算法1一樣，變量一樣，變量i控制刪除字符的個(gè)數(shù)，變量控制刪除字符的個(gè)數(shù)，變量j控控制相鄰比較操作的下標(biāo)，當(dāng)刪除了第制相鄰比較操作的下標(biāo)，當(dāng)刪除了第j個(gè)字符后，個(gè)字符后，j賦值為賦值為j-1，以保證實(shí)例以保證實(shí)例2（字符串（字符串n2）出現(xiàn)的情況得到正確的處理。）出現(xiàn)的情況得到正確的處理。 【例【例2 2】數(shù)列極差問(wèn)題】數(shù)列極差問(wèn)題 在黑板上寫(xiě)了在黑板上寫(xiě)了N N個(gè)正整數(shù)作成的一個(gè)數(shù)列，進(jìn)行如下操個(gè)正整數(shù)作成的一個(gè)數(shù)列，進(jìn)行如下操作作: :每一次擦去其中的兩個(gè)數(shù)每一次擦去其中的兩個(gè)數(shù)a a和和b b，然后在數(shù)列中加入一個(gè)，然后在數(shù)列中加入一個(gè)數(shù)數(shù)a ab+1b+1，如此下去直至黑板上剩

22、下一個(gè)數(shù)，在所有按這種，如此下去直至黑板上剩下一個(gè)數(shù)，在所有按這種操作方式最后得到的數(shù)中，最大的記作操作方式最后得到的數(shù)中，最大的記作maxmax，最小的記作，最小的記作minmin，則該數(shù)列的極差定義為則該數(shù)列的極差定義為M=max-minM=max-min。 問(wèn)題分析問(wèn)題分析 算法設(shè)計(jì)算法設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 算法分析算法分析 問(wèn)題分析問(wèn)題分析 和上一個(gè)例題一樣，我們通過(guò)實(shí)例來(lái)認(rèn)識(shí)題目中描述的計(jì)和上一個(gè)例題一樣，我們通過(guò)實(shí)例來(lái)認(rèn)識(shí)題目中描述的計(jì)算過(guò)程。對(duì)三個(gè)具體的數(shù)據(jù)算過(guò)程。對(duì)三個(gè)具體的數(shù)據(jù)3，5，7討論，可能有以下三種討論，可能有以下三種結(jié)果：結(jié)果：（3*5+1）*7+1=11

23、3、（、（3*7+1）*5+1=111、（、（5*7+1）*3+1=109 由此可見(jiàn)，先運(yùn)算小數(shù)據(jù)得到的是最大值，先運(yùn)算大數(shù)據(jù)由此可見(jiàn)，先運(yùn)算小數(shù)據(jù)得到的是最大值，先運(yùn)算大數(shù)據(jù)得到的是最小值。得到的是最小值。 下面再以三個(gè)數(shù)為例證明此題用貪心策略求解的合理下面再以三個(gè)數(shù)為例證明此題用貪心策略求解的合理性性, ,不妨假設(shè)：不妨假設(shè)：ab=a+k1c=a+k1+k2ab=a+k10k1,k20，則有以下，則有以下幾種組合計(jì)算結(jié)果：幾種組合計(jì)算結(jié)果：1)(a1)(a* *b+1)b+1)* *c+1=ac+1=a* *a a* *a+(2k1+k2)aa+(2k1+k2)a* *a+(k1(k1+k

24、2)+1)a+(k1(k1+k2)+1)* *a+k1+a+k1+k2+1k2+12)(a2)(a* *c+1)c+1)* *b+1=ab+1=a* *a a* *a+(2k1+k2)aa+(2k1+k2)a* *a+(k1(k1+k2)+1)a+(k1(k1+k2)+1)* *a+k1+a+k1+1 13)(b3)(b* *c+1)c+1)* *a+1=aa+1=a* *a a* *a+(2k1+k2)aa+(2k1+k2)a* *a+(k1(k1+k2)+1)a+(k1(k1+k2)+1)* *a+1a+1 顯然此問(wèn)題適合用貪婪策略顯然此問(wèn)題適合用貪婪策略, ,不過(guò)在求最大值時(shí)，要先不過(guò)在

25、求最大值時(shí)，要先選擇較小的數(shù)操作。反過(guò)來(lái)求最小值時(shí)，要先選擇較大的選擇較小的數(shù)操作。反過(guò)來(lái)求最小值時(shí)，要先選擇較大的數(shù)操作。這是一道兩次運(yùn)用貪心策略解決的問(wèn)題。數(shù)操作。這是一道兩次運(yùn)用貪心策略解決的問(wèn)題。算法設(shè)計(jì)算法設(shè)計(jì) 1 1）由以上分析，大家可以發(fā)現(xiàn)這個(gè)問(wèn)題的解決方法和哈）由以上分析，大家可以發(fā)現(xiàn)這個(gè)問(wèn)題的解決方法和哈夫曼樹(shù)的構(gòu)造過(guò)程相似，不斷從現(xiàn)有的數(shù)據(jù)中，選取最大和最夫曼樹(shù)的構(gòu)造過(guò)程相似，不斷從現(xiàn)有的數(shù)據(jù)中，選取最大和最小的兩個(gè)數(shù)，計(jì)算后的結(jié)果繼續(xù)參與運(yùn)算，直到剩余一個(gè)數(shù)算小的兩個(gè)數(shù)，計(jì)算后的結(jié)果繼續(xù)參與運(yùn)算，直到剩余一個(gè)數(shù)算法結(jié)束。法結(jié)束。 2) 2) 選取最大和最小的兩個(gè)數(shù)較高效的

26、算法是用二分法完選取最大和最小的兩個(gè)數(shù)較高效的算法是用二分法完成，成， 這里僅僅用簡(jiǎn)單的逐個(gè)比較的方法來(lái)求解。這里僅僅用簡(jiǎn)單的逐個(gè)比較的方法來(lái)求解。 注意到由于注意到由于找到的兩個(gè)數(shù)將不再參與其后的運(yùn)算，其中一個(gè)自然地是用它找到的兩個(gè)數(shù)將不再參與其后的運(yùn)算，其中一個(gè)自然地是用它們的計(jì)算結(jié)果代替，另一個(gè)我們用當(dāng)前的最后一個(gè)數(shù)據(jù)覆蓋即們的計(jì)算結(jié)果代替，另一個(gè)我們用當(dāng)前的最后一個(gè)數(shù)據(jù)覆蓋即可。所以不但要選取最大和最小，還必須記錄它們的位置，以可。所以不但要選取最大和最小，還必須記錄它們的位置，以便將其覆蓋。便將其覆蓋。 3 3）求）求maxmax、minmin的過(guò)程必須獨(dú)立，也就是說(shuō)求的過(guò)程必須獨(dú)立

27、，也就是說(shuō)求maxmax和和minmin都都必須從原始數(shù)據(jù)開(kāi)始必須從原始數(shù)據(jù)開(kāi)始, ,否則不能找到真正的否則不能找到真正的maxmax和和minmin。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 1) 1) 由設(shè)計(jì)由設(shè)計(jì)2 2）、）、3 3）知，必須用兩個(gè)數(shù)組同時(shí)存儲(chǔ)初始數(shù)據(jù)。）知，必須用兩個(gè)數(shù)組同時(shí)存儲(chǔ)初始數(shù)據(jù)。 2) 2) 求最大和最小的兩個(gè)數(shù)的函數(shù)至少要返回兩個(gè)數(shù)據(jù)，為求最大和最小的兩個(gè)數(shù)的函數(shù)至少要返回兩個(gè)數(shù)據(jù)，為方便起見(jiàn)我們用全局變量實(shí)現(xiàn)。方便起見(jiàn)我們用全局變量實(shí)現(xiàn)。 int s1,s2; main（ ）int j,n,a100,b100,max,min;print(“How mang data?”

28、); input(n);print(“input these data”);for (j=1;j2) while (n2) max2(a,n); as1= as1 max2(a,n); as1= as1* * as2+1; as2+1; as2=an; n=n-1; as2=an; n=n-1; return(a1 return(a1* * a2+1); a2+1); max2(int a,int n)/選出兩個(gè)最大的元素下標(biāo)選出兩個(gè)最大的元素下標(biāo)s1,s2 int j; if(a1=a2) s1=1; s2=2; else s1=2; s2=1; for (j=3;jas1) s2=s1;

29、s1=j; else if (ajas2) s2=j; calculatemax(int a,int n)calculatemax(int a,int n) int j; int j; while (n2) while (n2) min2(a,n); as1= as1 min2(a,n); as1= as1* * as2+1; as2+1; as2=an; n=n-1; as2=an; n=n-1; return(a1 return(a1* * a2+1); a2+1); min2(int a ,int n)/選出兩個(gè)最小的元素下標(biāo)選出兩個(gè)最小的元素下標(biāo)s1,s2 int j; if(a1=a

30、2) s1=1; s2=2; else s1=2; s2=1; for (j=3;j=n;j+) if (ajas1) s2=s1; s1=j; else if (aj1/27/81/2， 7/8-1/21/37/8-1/21/3， 7/8-1/2-1/3=1/247/8-1/2-1/3=1/24。過(guò)程如下：過(guò)程如下： 1)1)找最小的找最小的n n（也就是最大的埃及分?jǐn)?shù)），使分?jǐn)?shù)（也就是最大的埃及分?jǐn)?shù)），使分?jǐn)?shù)f1/nf1/n； 2)2)輸出輸出1/n1/n； 3)3)計(jì)算計(jì)算f=f-1/nf=f-1/n； 4)4)若此時(shí)的若此時(shí)的f f是埃及分?jǐn)?shù)，輸出是埃及分?jǐn)?shù)，輸出f,f,算法結(jié)束算法結(jié)

31、束, ,否則返回否則返回1 1）。）。 數(shù)學(xué)模型數(shù)學(xué)模型 記真分?jǐn)?shù)記真分?jǐn)?shù)F=A/BF=A/B；對(duì)；對(duì)B/AB/A進(jìn)行整除運(yùn)算進(jìn)行整除運(yùn)算, ,商為商為D, D, 余數(shù)為余數(shù)為0 0K KA A，它們之間的關(guān)系及導(dǎo)出關(guān)系如下：它們之間的關(guān)系及導(dǎo)出關(guān)系如下： B=AB=A* *D+KD+K，B/A=D+K/AB/A=D+K/AD+1D+1，A/BA/B1/(D+1)1/(D+1)，記，記C=D+1C=D+1。 這樣我們就找到了分?jǐn)?shù)這樣我們就找到了分?jǐn)?shù)F F所包含的所包含的“最大的最大的”埃及分?jǐn)?shù)就是埃及分?jǐn)?shù)就是1/C1/C。進(jìn)一步計(jì)算：進(jìn)一步計(jì)算： A/B-1/C=A/B-1/C=（A A* *

32、C-BC-B）/B/B* *C C 也就是說(shuō)繼續(xù)要解決的是有關(guān)分子為也就是說(shuō)繼續(xù)要解決的是有關(guān)分子為A=AA=A* *C-B,C-B,分母為分母為B=BB=B* *C C的的問(wèn)題。問(wèn)題。 算法設(shè)計(jì)算法設(shè)計(jì) 由以上數(shù)學(xué)模型，真正的算法過(guò)程如下：由以上數(shù)學(xué)模型，真正的算法過(guò)程如下： 1)1)設(shè)某個(gè)真分?jǐn)?shù)的分子為設(shè)某個(gè)真分?jǐn)?shù)的分子為A(1A(1），分母為），分母為B B； 2)2)把把B B除以除以A A的商的整數(shù)部分加的商的整數(shù)部分加1 1后的值作為埃及后的值作為埃及 分?jǐn)?shù)的一個(gè)分母分?jǐn)?shù)的一個(gè)分母C;C; 3) 3)輸出輸出1/C1/C； 4)4)將將A A乘以乘以C C減去減去B B作為新的作為

33、新的A A； 5)5)將將B B乘以乘以C C作為新的作為新的B B； 6)6)如果如果A A大于大于1 1且能整除且能整除B,B,則最后一個(gè)分母為則最后一個(gè)分母為B/AB/A； 7)7)如果如果A A1,1,則最后一個(gè)分母為則最后一個(gè)分母為B;B;否則轉(zhuǎn)步驟否則轉(zhuǎn)步驟(2).(2). 例：例：7/8=1/2+1/3+1/247/8=1/2+1/3+1/24的解題步驟：的解題步驟： 同樣用變量同樣用變量A A表示分子，變量表示分子，變量B B表示分母；表示分母； C=8+1=2 /C=8+1=2 /說(shuō)明說(shuō)明7/81/27/81/2， 打印打印1/21/2 A=7 A=7* *2-8=62-8=

34、6，B=BB=B* *C=16 C=16 / /在計(jì)算在計(jì)算7/8-1/2=(77/8-1/2=(7* *2-8)/(72-8)/(7* *2)=6/16=A/B2)=6/16=A/B C=16/6+1=3 C=16/6+1=3 / /說(shuō)明說(shuō)明16/61/316/61/3， 打印打印1/31/3 A=6 A=6* *3-16=23-16=2，B=BB=B* *C=16C=16* *3=483=48 / /在計(jì)算在計(jì)算6/16-1/3=(66/16-1/3=(6* *3-16)/(163-16)/(16* *3)=2/48=A/B3)=2/48=A/B A1 A1但但B/AB/A為整數(shù)為整數(shù)24

35、24，打印，打印1/24 1/24 結(jié)束結(jié)束. .算法算法main（）（） int a,b,c; print(“input element”); input(a); print(“input denominator”); input(b); if(ab)/真分?jǐn)?shù)的要求真分?jǐn)?shù)的要求 print(“input error”); else if (a=1 or b mod a=0) print( 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 )

36、 print (+1/; b / a); a=1; if( a 1) print(+); 【例【例4 4】 幣種統(tǒng)計(jì)問(wèn)題 【例【例5 5】 取數(shù)游戲 4.4.2 4.4.2 相對(duì)或近似貪婪問(wèn)題相對(duì)或近似貪婪問(wèn)題 4.4.1 4.4.1節(jié)的三個(gè)例子對(duì)于輸入的任何數(shù)據(jù)，貪婪策略都是適節(jié)的三個(gè)例子對(duì)于輸入的任何數(shù)據(jù)，貪婪策略都是適用的，因此我們稱它們?yōu)橛玫模虼宋覀兎Q它們?yōu)椤翱山^對(duì)貪婪問(wèn)題可絕對(duì)貪婪問(wèn)題”。看下一節(jié)的。看下一節(jié)的例子就明白，有的問(wèn)題就不一定如此了。例子就明白，有的問(wèn)題就不一定如此了。【例【例5 5】取數(shù)游戲取數(shù)游戲 有有2 2個(gè)人輪流取個(gè)人輪流取2n2n個(gè)數(shù)中的個(gè)數(shù)中的n n個(gè)數(shù)，取

37、數(shù)之和大者為勝。請(qǐng)個(gè)數(shù)，取數(shù)之和大者為勝。請(qǐng)編寫(xiě)算法，讓先取數(shù)者勝，模擬取數(shù)過(guò)程。編寫(xiě)算法，讓先取數(shù)者勝，模擬取數(shù)過(guò)程。 問(wèn)題分析問(wèn)題分析 算法設(shè)計(jì)算法設(shè)計(jì) 算法說(shuō)明算法說(shuō)明 算法分析算法分析 問(wèn)題分析問(wèn)題分析 這個(gè)游戲一般假設(shè)取數(shù)者只能看到這個(gè)游戲一般假設(shè)取數(shù)者只能看到2n2n個(gè)數(shù)中兩邊的數(shù)個(gè)數(shù)中兩邊的數(shù), ,用貪婪算法的情況用貪婪算法的情況: : 若一組數(shù)據(jù)為：若一組數(shù)據(jù)為：6,16,27,6,12,9,2,11,6,56,16,27,6,12,9,2,11,6,5。用貪婪策。用貪婪策略每次兩人都取兩邊的數(shù)中較大的一個(gè)數(shù)略每次兩人都取兩邊的數(shù)中較大的一個(gè)數(shù), ,先取者勝先取者勝. .以以A

38、先先取為例：取為例： 取數(shù)結(jié)果為：取數(shù)結(jié)果為： 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 但若選另一組數(shù)據(jù)：但若選另一組數(shù)據(jù)：16,27,7,12,9,2,11,616,27,7,12,9,2,11,6。仍都用貪婪。仍都用貪婪算法，先取者算法，先取者A A敗。敗。 取數(shù)結(jié)果為：取數(shù)結(jié)果為： A 16,7,9,11=43A 16,7,9,11=43 B 27,12,6,2=47 B 27,12,6,2=47 勝勝 其實(shí)，若我們只能看到兩邊的數(shù)據(jù)，則此題無(wú)論先取還其實(shí)，若我們只能看到兩邊的數(shù)據(jù)，則此題

39、無(wú)論先取還是后取都無(wú)必勝的策略。這時(shí)一般的策略是用近似貪婪算法。是后取都無(wú)必勝的策略。這時(shí)一般的策略是用近似貪婪算法。 但若取數(shù)者能看到全部但若取數(shù)者能看到全部2n2n個(gè)數(shù)，則此問(wèn)題可有一些簡(jiǎn)單個(gè)數(shù)，則此問(wèn)題可有一些簡(jiǎn)單的方法，有的雖不能保證所取數(shù)的和是最大，但確是一個(gè)先的方法，有的雖不能保證所取數(shù)的和是最大，但確是一個(gè)先取者必勝的策略。取者必勝的策略。 數(shù)學(xué)模型建立：數(shù)學(xué)模型建立：N個(gè)數(shù)排成一行，我們給這個(gè)數(shù)排成一行，我們給這N個(gè)數(shù)從左到右編號(hào)，個(gè)數(shù)從左到右編號(hào)，依次為依次為1，2，N，因?yàn)椋驗(yàn)镹為偶數(shù)，又因?yàn)槭俏覀兿热?shù)，計(jì)為偶數(shù)，又因?yàn)槭俏覀兿热?shù)，計(jì)算機(jī)后取數(shù)，所以一開(kāi)始我們既可以取

40、到一個(gè)奇編號(hào)的數(shù)（最算機(jī)后取數(shù)，所以一開(kāi)始我們既可以取到一個(gè)奇編號(hào)的數(shù)（最左邊編號(hào)為左邊編號(hào)為1的數(shù)）又可以取到一個(gè)偶編號(hào)的數(shù)（最右邊編號(hào)的數(shù)）又可以取到一個(gè)偶編號(hào)的數(shù)（最右邊編號(hào)為為N的數(shù)）。的數(shù)）。 如果我們第一次取奇編號(hào)（編號(hào)為如果我們第一次取奇編號(hào)（編號(hào)為1）的數(shù)，則接著計(jì)算機(jī)）的數(shù)，則接著計(jì)算機(jī)只能取到偶編號(hào)（編號(hào)為只能取到偶編號(hào)（編號(hào)為2或或N）的數(shù)；）的數(shù)； 如果我們第一次取偶編號(hào)（編號(hào)為如果我們第一次取偶編號(hào)（編號(hào)為N）的數(shù)，則接著計(jì)算機(jī)）的數(shù)，則接著計(jì)算機(jī)只能取到奇編號(hào)（編號(hào)為只能取到奇編號(hào)（編號(hào)為1或或N-1）的數(shù)；）的數(shù)； 即無(wú)論我們第一次是取奇編號(hào)的數(shù)還是取偶編號(hào)的數(shù)，

41、接著即無(wú)論我們第一次是取奇編號(hào)的數(shù)還是取偶編號(hào)的數(shù)，接著計(jì)算機(jī)只能取到另一種編號(hào)（偶編號(hào)或奇編號(hào)）的數(shù)。計(jì)算機(jī)只能取到另一種編號(hào)（偶編號(hào)或奇編號(hào)）的數(shù)。 這是對(duì)第一個(gè)回合的分析，顯然對(duì)以后整個(gè)取數(shù)過(guò)這是對(duì)第一個(gè)回合的分析，顯然對(duì)以后整個(gè)取數(shù)過(guò)程都適用。也就是說(shuō)，我們能夠控制讓計(jì)算機(jī)自始自終程都適用。也就是說(shuō)，我們能夠控制讓計(jì)算機(jī)自始自終只取一種編號(hào)的數(shù)。這樣，我們只要比較奇編號(hào)數(shù)之和只取一種編號(hào)的數(shù)。這樣，我們只要比較奇編號(hào)數(shù)之和與偶編號(hào)數(shù)之和誰(shuí)大，以決定最開(kāi)始我們是取奇編號(hào)數(shù)與偶編號(hào)數(shù)之和誰(shuí)大，以決定最開(kāi)始我們是取奇編號(hào)數(shù)還是偶編號(hào)數(shù)即可。（如果奇編號(hào)數(shù)之和與偶編號(hào)數(shù)之還是偶編號(hào)數(shù)即可。（如

42、果奇編號(hào)數(shù)之和與偶編號(hào)數(shù)之和同樣大，我們第一次可以任意取數(shù)，因?yàn)楫?dāng)兩者所取和同樣大，我們第一次可以任意取數(shù)，因?yàn)楫?dāng)兩者所取數(shù)和相同時(shí)，先取者為勝。數(shù)和相同時(shí)，先取者為勝。算法設(shè)計(jì)：有了以上建立的高效數(shù)學(xué)模型，算法就很簡(jiǎn)單了，算法設(shè)計(jì)：有了以上建立的高效數(shù)學(xué)模型，算法就很簡(jiǎn)單了，算法只需要分別計(jì)算一組數(shù)的奇數(shù)位和偶數(shù)位的數(shù)據(jù)之和，算法只需要分別計(jì)算一組數(shù)的奇數(shù)位和偶數(shù)位的數(shù)據(jù)之和，然后就先了取數(shù)者就可以確定必勝的取數(shù)方式了。然后就先了取數(shù)者就可以確定必勝的取數(shù)方式了。以下面一排數(shù)為例：以下面一排數(shù)為例：1 2 3 10 5 6 7 8 9 4奇編號(hào)數(shù)之和為奇編號(hào)數(shù)之和為25（=1+3+5+7+9

43、），小于偶編號(hào)數(shù)之和為），小于偶編號(hào)數(shù)之和為30（=2+10+6+8+4）。我們第一次取）。我們第一次取4，以后，計(jì)算機(jī)取哪，以后，計(jì)算機(jī)取哪邊的數(shù)我們就取哪邊的數(shù)（如果計(jì)算機(jī)取邊的數(shù)我們就取哪邊的數(shù)（如果計(jì)算機(jī)取1，我們就取，我們就取2；如；如果計(jì)算機(jī)取果計(jì)算機(jī)取9，我們就取，我們就取8）。這樣可以保證我們自始自終取）。這樣可以保證我們自始自終取到偶編號(hào)的數(shù)，而計(jì)算機(jī)自始自終取到奇編號(hào)的數(shù)。到偶編號(hào)的數(shù)，而計(jì)算機(jī)自始自終取到奇編號(hào)的數(shù)。main( )main( )int i,s1,s2,data;int i,s1,s2,data;input(n); s1=0input(n); s1=0； s

44、2=0;s2=0; for(i=1;i=n;i=i+1) for(i=1;is2) print(“first take if(s1s2) print(“first take left”);left”); else print(“first take else print(“first take right”);right”); 這個(gè)例題又一次說(shuō)明，解決問(wèn)題時(shí)數(shù)學(xué)模型的選這個(gè)例題又一次說(shuō)明，解決問(wèn)題時(shí)數(shù)學(xué)模型的選擇是非常重要的。擇是非常重要的。 1.1.貪心法的基本思路貪心法的基本思路： 從問(wèn)題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，每一步都從問(wèn)題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，每一步都作一

45、個(gè)不可回溯的決策作一個(gè)不可回溯的決策, ,盡可能地求得最好的解。當(dāng)達(dá)到某算法盡可能地求得最好的解。當(dāng)達(dá)到某算法中的某一步不需要再繼續(xù)前進(jìn)時(shí)，算法停止。中的某一步不需要再繼續(xù)前進(jìn)時(shí)，算法停止。4.4.3 4.4.3 關(guān)于貪婪策略討論關(guān)于貪婪策略討論2.2.該算法適用的問(wèn)題該算法適用的問(wèn)題： 貪婪算法對(duì)問(wèn)題只需考慮貪婪算法對(duì)問(wèn)題只需考慮當(dāng)前局部信息當(dāng)前局部信息就要做出決策，也就要做出決策，也就是說(shuō)使用貪婪算法的前提是就是說(shuō)使用貪婪算法的前提是“局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解最優(yōu)解”。 該算法的適用范圍較小該算法的適用范圍較小, , 若應(yīng)用不當(dāng)若應(yīng)用不當(dāng), , 不能保證求

46、得問(wèn)題不能保證求得問(wèn)題的最佳解。一般情況下通過(guò)一些實(shí)際的數(shù)據(jù)例子的最佳解。一般情況下通過(guò)一些實(shí)際的數(shù)據(jù)例子( (當(dāng)然要有一當(dāng)然要有一定的普遍性定的普遍性),),就能從直觀上就能判斷一個(gè)問(wèn)題是否可以用貪婪就能從直觀上就能判斷一個(gè)問(wèn)題是否可以用貪婪算法，更準(zhǔn)確的方法是通過(guò)數(shù)學(xué)方法證明問(wèn)題對(duì)貪婪策略的選算法，更準(zhǔn)確的方法是通過(guò)數(shù)學(xué)方法證明問(wèn)題對(duì)貪婪策略的選用性。用性。4.4.貪婪策略選擇貪婪策略選擇: : 首先貪婪算法的原理是通過(guò)局部最優(yōu)來(lái)達(dá)到全局最優(yōu)首先貪婪算法的原理是通過(guò)局部最優(yōu)來(lái)達(dá)到全局最優(yōu), ,采采用的是逐步構(gòu)造最優(yōu)解的方法。用的是逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段，都作出一個(gè)看在每個(gè)階段，都

47、作出一個(gè)看上去最優(yōu)的（在一定的標(biāo)準(zhǔn)下），決策一旦作出，就不可再上去最優(yōu)的（在一定的標(biāo)準(zhǔn)下），決策一旦作出，就不可再更改。用貪婪算法只能解決通過(guò)局部最優(yōu)的策略能達(dá)到全局更改。用貪婪算法只能解決通過(guò)局部最優(yōu)的策略能達(dá)到全局最優(yōu)的問(wèn)題。因此一定要注意判斷問(wèn)題是否適合采用貪婪算最優(yōu)的問(wèn)題。因此一定要注意判斷問(wèn)題是否適合采用貪婪算法策略，找到的解是否一定是問(wèn)題的最優(yōu)解。法策略，找到的解是否一定是問(wèn)題的最優(yōu)解。 在在動(dòng)態(tài)規(guī)劃算動(dòng)態(tài)規(guī)劃算法策略中，體現(xiàn)在它的決策不是線性的而是法策略中，體現(xiàn)在它的決策不是線性的而是全面考慮不同的情況分別進(jìn)行決策全面考慮不同的情況分別進(jìn)行決策, , 并通過(guò)多階段決策來(lái)最并通過(guò)多

48、階段決策來(lái)最終解決問(wèn)題。在各個(gè)階段采取決策后終解決問(wèn)題。在各個(gè)階段采取決策后, , 會(huì)不斷決策出新的數(shù)會(huì)不斷決策出新的數(shù)據(jù)據(jù), ,直到找到最優(yōu)解直到找到最優(yōu)解. .每次決策依賴于當(dāng)前狀態(tài)每次決策依賴于當(dāng)前狀態(tài), , 又隨即引起又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有故有“動(dòng)態(tài)動(dòng)態(tài)”的含義。所以，這種多階段決策最優(yōu)化的解決的含義。所以，這種多階段決策最優(yōu)化的解決問(wèn)題的過(guò)程稱為問(wèn)題的過(guò)程稱為動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃。 4.5 動(dòng)態(tài)規(guī)劃 我們通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明動(dòng)態(tài)規(guī)劃的多階段決策與我們通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明動(dòng)態(tài)規(guī)劃的多

49、階段決策與貪婪算法有什么區(qū)別。貪婪算法有什么區(qū)別。 【例【例1】 數(shù)塔問(wèn)題數(shù)塔問(wèn)題4.5.1 4.5.1 認(rèn)識(shí)動(dòng)態(tài)規(guī)劃認(rèn)識(shí)動(dòng)態(tài)規(guī)劃【例【例1 1】數(shù)塔問(wèn)題數(shù)塔問(wèn)題 有形如圖4-11所示的一個(gè)數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的數(shù)值和最大。 問(wèn)題分析算法設(shè)計(jì)算法小結(jié) 問(wèn)題分析問(wèn)題分析 這個(gè)問(wèn)題用貪婪算法有可能會(huì)找不到真正的最大和。這個(gè)問(wèn)題用貪婪算法有可能會(huì)找不到真正的最大和。以圖以圖4-114-11為例就是如此。用貪婪的策略，則路徑和分別為：為例就是如此。用貪婪的策略，則路徑和分別為： 9+15+8+9+10=51 9+15+8+9+1

50、0=51 （自上而下），（自上而下）， 19+2+10+12+9=5219+2+10+12+9=52（自下而上）。（自下而上）。都得不到最優(yōu)解，真正的最大和是：都得不到最優(yōu)解，真正的最大和是： 9+12+10+18+10=599+12+10+18+10=59。 在知道數(shù)塔的全貌的前提下，可以用在知道數(shù)塔的全貌的前提下，可以用枚舉法枚舉法或下一章將或下一章將學(xué)習(xí)的學(xué)習(xí)的搜索算法搜索算法來(lái)完成。來(lái)完成。 算法設(shè)計(jì)算法設(shè)計(jì) 動(dòng)態(tài)規(guī)劃設(shè)計(jì)過(guò)程如下：動(dòng)態(tài)規(guī)劃設(shè)計(jì)過(guò)程如下： 1.1.階段劃分：階段劃分： 第一步對(duì)于第五層的數(shù)據(jù)，我們做如下第一步對(duì)于第五層的數(shù)據(jù)，我們做如下五次決策五次決策： 對(duì)經(jīng)過(guò)第四層對(duì)

51、經(jīng)過(guò)第四層2 2的路徑選擇第五層的的路徑選擇第五層的1919， 對(duì)經(jīng)過(guò)第四層對(duì)經(jīng)過(guò)第四層1818的路徑選擇第五層的的路徑選擇第五層的1010， 對(duì)經(jīng)過(guò)第四層對(duì)經(jīng)過(guò)第四層9 9的路徑也選擇第五層的的路徑也選擇第五層的1010， 對(duì)經(jīng)過(guò)第四層對(duì)經(jīng)過(guò)第四層5 5的路徑選擇第五層的的路徑選擇第五層的1616。 并保留決策的結(jié)果并保留決策的結(jié)果 以上的決策結(jié)果將五階數(shù)塔問(wèn)題變?yōu)橐陨系臎Q策結(jié)果將五階數(shù)塔問(wèn)題變?yōu)? 4階子問(wèn)題，階子問(wèn)題，遞推遞推出第四層與第五層的和為出第四層與第五層的和為: : 21(2+19),28(18+10),19(9+10),21(5+16) 21(2+19),28(18+10),

52、19(9+10),21(5+16)。 用同樣的方法還可以將用同樣的方法還可以將4 4階數(shù)塔問(wèn)題階數(shù)塔問(wèn)題, ,變?yōu)樽優(yōu)? 3階數(shù)塔問(wèn)題。階數(shù)塔問(wèn)題。 最后得到的最后得到的1 1階數(shù)塔問(wèn)題，就是整個(gè)問(wèn)題的最優(yōu)解階數(shù)塔問(wèn)題，就是整個(gè)問(wèn)題的最優(yōu)解。 2 2存儲(chǔ)、求解：存儲(chǔ)、求解： 1) 1) 原始信息存儲(chǔ)原始信息存儲(chǔ) 原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個(gè)整型原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個(gè)整型 變量變量n n存儲(chǔ)，數(shù)塔中的數(shù)據(jù)用二維數(shù)組存儲(chǔ)，數(shù)塔中的數(shù)據(jù)用二維數(shù)組datadata，存儲(chǔ)成如，存儲(chǔ)成如 下的下三角陣下的下三角陣: : 9 9 12 15 12 15 10 6 8 10 6

53、8 2 18 9 5 2 18 9 5 19 7 10 4 16 19 7 10 4 16 2) 2) 動(dòng)態(tài)規(guī)劃過(guò)程存儲(chǔ)動(dòng)態(tài)規(guī)劃過(guò)程存儲(chǔ) 必需用二維數(shù)組必需用二維數(shù)組a a存儲(chǔ)各階段的決策結(jié)果。二維數(shù)組存儲(chǔ)各階段的決策結(jié)果。二維數(shù)組a a的存儲(chǔ)內(nèi)容如下：的存儲(chǔ)內(nèi)容如下： anj=datanj j=1,2,nanj=datanj j=1,2,n； i=n-1,n-2,1i=n-1,n-2,1，j=1,2,ij=1,2,i；時(shí)；時(shí) aij=max(ai+1jaij=max(ai+1j，ai+1j+1)+dataijai+1j+1)+dataij 最后最后a11a11存儲(chǔ)的就是問(wèn)題的結(jié)果。存儲(chǔ)的就是

54、問(wèn)題的結(jié)果。3) 3) 最優(yōu)解路徑求解及存儲(chǔ)最優(yōu)解路徑求解及存儲(chǔ) 僅有數(shù)組僅有數(shù)組datadata和數(shù)組和數(shù)組a a可以找到最優(yōu)解的路徑，可以找到最優(yōu)解的路徑， 但需要但需要自頂向下比較數(shù)組自頂向下比較數(shù)組datadata和數(shù)組和數(shù)組a a是可以找到。如圖是可以找到。如圖4.5.24.5.2求解求解和輸出過(guò)程如下：和輸出過(guò)程如下： 輸出輸出data119data119 b=a11-data11=59-9=50 b=a11-data11=59-9=50 b b與與a21,a22 a21,a22 比較比較 b b與與a21a21相等輸出相等輸出data2112data2112 b=a21-data

55、21=50-12=38 b=a21-data21=50-12=38 b b與與a31,a32 a31,a32 比較比較 b b與與a31a31相等輸出相等輸出data3110data3110 b=a31-data31=38-10=28 b=a31-data31=38-10=28 b b與與a41,a42 a41,a42 比較比較 b b與與a42a42相等輸出相等輸出data4218data4218 b=a42-data42=28-18=10 b b=a42-data42=28-18=10 b與與a52,a53 a52,a53 比較比較 b b與與a53a53相等輸出相等輸出data5310“

56、data5310“ 數(shù)組數(shù)組data data 數(shù)組數(shù)組a a 9 59 9 59 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-12 4-12 數(shù)塔及動(dòng)態(tài)規(guī)劃過(guò)程數(shù)據(jù)數(shù)塔及動(dòng)態(tài)規(guī)劃過(guò)程數(shù)據(jù) 為了設(shè)計(jì)簡(jiǎn)潔的算法，我們最后用三維數(shù)組為了設(shè)計(jì)簡(jiǎn)潔的算法，我們最后用三維數(shù)組a50503a50503存儲(chǔ)以上確定的三個(gè)數(shù)組的信息。存儲(chǔ)以上確定的三

57、個(gè)數(shù)組的信息。 a50501a50501代替數(shù)組代替數(shù)組datadata， a50502a50502代替數(shù)組代替數(shù)組d, d, a50503 a50503記錄解路徑。記錄解路徑。 數(shù)塔問(wèn)題的算法數(shù)塔問(wèn)題的算法main( )main( ) int a50503,i,j,n; int 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

58、-1 ; i=1;i-) for (j=1 ;j= 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

59、=j+aij3; j=j+aij3; print (anj1);print (anj1); 從例子中可以看到：從例子中可以看到： 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃= =貪婪策略貪婪策略+ +遞推遞推( (降階降階)+)+存儲(chǔ)遞推結(jié)果存儲(chǔ)遞推結(jié)果 貪婪策略、遞推算法都是在貪婪策略、遞推算法都是在“線性線性”地解決問(wèn)題，而動(dòng)態(tài)地解決問(wèn)題，而動(dòng)態(tài)規(guī)劃則是規(guī)劃則是全面全面分階段地解決問(wèn)題。可以通俗地說(shuō)動(dòng)態(tài)規(guī)劃是分階段地解決問(wèn)題。可以通俗地說(shuō)動(dòng)態(tài)規(guī)劃是“帶決策的多階段、多方位的遞推算法帶決策的多階段、多方位的遞推算法”。 1.適合動(dòng)態(tài)規(guī)劃的問(wèn)題特征 動(dòng)態(tài)規(guī)劃算法的問(wèn)題及決策應(yīng)該具有三個(gè)性質(zhì)：動(dòng)態(tài)規(guī)劃算法的問(wèn)題及決策應(yīng)該

60、具有三個(gè)性質(zhì)：最優(yōu)最優(yōu) 化原理、無(wú)后向性、子問(wèn)題重疊性質(zhì)。化原理、無(wú)后向性、子問(wèn)題重疊性質(zhì)。1) 1) 最優(yōu)化原理最優(yōu)化原理( (或稱為最佳原則、最優(yōu)子結(jié)構(gòu)或稱為最佳原則、最優(yōu)子結(jié)構(gòu)) )。 2) 2) 無(wú)后向性無(wú)后向性( (無(wú)后效性無(wú)后效性) )。 3) 3) 有重疊子問(wèn)題。有重疊子問(wèn)題。4.5.24.5.2 算法框架算法框架2. 動(dòng)態(tài)規(guī)劃的基本思想 動(dòng)態(tài)規(guī)劃方法的基本思想是，把求解的問(wèn)題分成許多階動(dòng)態(tài)規(guī)劃方法的基本思想是，把求解的問(wèn)題分成許多階段或多個(gè)子問(wèn)題，然后按順序求解各子問(wèn)題。前一子問(wèn)題的段或多個(gè)子問(wèn)題，然后按順序求解各子問(wèn)題。前一子問(wèn)題的解為后一子問(wèn)題的求解提供了有用的信息。最后一