day9基于貪心的算法和應(yīng)用舉例-楊志軍

1、基于貪心的算法和應(yīng)用舉例基于貪心的算法和應(yīng)用舉例20142014年年7 7月月 贛榆高級(jí)中學(xué)贛榆高級(jí)中學(xué)貪心算法引入貪心算法引入【引例1】在n行m列的正整數(shù)矩陣中，要求從每行中選出1個(gè)數(shù)，使得選出的總共n個(gè)數(shù)的和最大?！痉治觥恳箍偤妥畲螅瑒t每個(gè)數(shù)要盡可能大，自然應(yīng)該選每行中最大的那個(gè)數(shù)。貪心算法引入貪心算法引入【引例2】有1元、5元、10元、50元、100元、500元的硬幣各C1、C5、C10、C50、C100、C500枚。現(xiàn)在要用這些硬幣來(lái)支付A元，最少需要多少枚硬幣？【分析】?jī)?yōu)先使用面值大的硬幣。貪心算法定義貪心算法定義 貪心算法是從問(wèn)題的某一個(gè)初始狀態(tài)出發(fā)，通過(guò)逐步構(gòu)造最優(yōu)解的方法向給

2、定的目標(biāo)前進(jìn)，并期望通過(guò)這種方法產(chǎn)生出一個(gè)全局最優(yōu)解的方法。方向方向紅箭頭表示當(dāng)前最優(yōu)決策；藍(lán)箭頭表示其他決策；小球表示當(dāng)前狀態(tài)。貪心算法的特點(diǎn)貪心算法的特點(diǎn) 貪心標(biāo)準(zhǔn)選擇：所謂貪心標(biāo)準(zhǔn)選擇就是應(yīng)用當(dāng)前“最好”的標(biāo)準(zhǔn)作為統(tǒng)一標(biāo)準(zhǔn)，將原問(wèn)題變?yōu)橐粋€(gè)相似的但規(guī)模更小的子問(wèn)題，而后的每一步都是當(dāng)前看似最佳的選擇。 最優(yōu)子結(jié)構(gòu)：當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心算法的特點(diǎn)貪心算法的特點(diǎn)【引例3】部分背包問(wèn)題有一個(gè)背包，容量是M150，有7個(gè)物品，物品可以分割成任意大小，要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘?。物品ABCDEFG體積3530605

3、0401025價(jià)值10403050354030貪心算法的特點(diǎn)貪心算法的特點(diǎn)【分析】有以下幾種策略可供選擇：（1）每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？（2）每次挑選所占空間最小的物品裝入是否能得到最優(yōu)解？（3）每次選取單位容量?jī)r(jià)值最大的物品。貪心算法的特點(diǎn)貪心算法的特點(diǎn)解題一般步驟解題一般步驟: :1 1、設(shè)計(jì)數(shù)據(jù)找規(guī)律；、設(shè)計(jì)數(shù)據(jù)找規(guī)律； 2 2、進(jìn)行貪心猜想；、進(jìn)行貪心猜想；3 3、正確性證明（嚴(yán)格證明和一般證明）、正確性證明（嚴(yán)格證明和一般證明）一般證明：列舉反例；一般證明：列舉反例；嚴(yán)格證明：數(shù)學(xué)歸納和反證法；嚴(yán)格證明：數(shù)學(xué)歸納和反證法；4 4、程序?qū)崿F(xiàn)。、程序?qū)崿F(xiàn)。經(jīng)典

4、例題經(jīng)典例題 刪數(shù)問(wèn)題（NOI 1995） 取數(shù)問(wèn)題（IOI 1996） 接水問(wèn)題 最大整數(shù) 均分紙牌（NOIP 2002） 合并果子（NOIP 2004） 三國(guó)游戲（NOIP 2010） 火柴排隊(duì)（NOIP 2013） 貨車運(yùn)輸（NOIP 2013）【例1】刪數(shù)問(wèn)題（NOI 1994） 鍵盤輸入一個(gè)高精度的正整數(shù)N，去掉其中任意S個(gè)數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。 輸出剩下的最小數(shù)。經(jīng)典例題經(jīng)典例題經(jīng)典例題經(jīng)典例題【分析】 因?yàn)橐獎(jiǎng)h除S個(gè)數(shù)字，可以一個(gè)一個(gè)地刪，每一次刪除的目的都是使剩下的數(shù)盡量小。 那么在每一次

5、刪除時(shí)，應(yīng)該選擇哪個(gè)數(shù)字呢？最大的那個(gè)數(shù)字？還是最左邊的那個(gè)數(shù)字？ 例如5768，刪除7可以使剩余的數(shù)最小。經(jīng)典例題經(jīng)典例題結(jié)論：每一次刪除的數(shù)字應(yīng)該是這個(gè)數(shù)字序列中最左邊遞減序列的第一個(gè)數(shù)字。具體操作為，按高位到低位的方向搜索遞減區(qū)間。若不存在遞減區(qū)間，則刪除尾數(shù)字，否則刪除遞減區(qū)間的首數(shù)符，這樣就形成一個(gè)最小的數(shù)。重復(fù)上述規(guī)則，直到刪除S個(gè)數(shù)字為止。經(jīng)典例題經(jīng)典例題例如：N8796542，S4第一次：N8796542，刪除8；第二次：N796542，刪除9；第三次：N76542，刪除7；第四次：N6542，刪除6，得到542。經(jīng)典例題經(jīng)典例題參考程序參考程序readlnreadln(n);

6、(n);readlnreadln(s);(s);for k:=1 to s dofor k:=1 to s dobeginbegin i i:=1;:=1; while ( while (i ilength(n) and (nlength(n) and (ni i=ni+1) do1) and (n1=0) dowhile (length(n)1) and (n1=0) do delete(n,1,1) delete(n,1,1)writelnwriteln(n);(n);討論一討論一【例2】取數(shù)問(wèn)題（IOI 1996） 給出2n（n100）個(gè)自然數(shù)（小于等于30000），將這2n個(gè)自然數(shù)排成

7、一列，游戲雙方A和B從中輪流取數(shù)，只允許從兩端取數(shù)，A方先取，然后B方再取。取完時(shí)，誰(shuí)取的數(shù)字總和最大為取勝方；若雙方和相等，則B勝，試問(wèn)A方是否有必勝策略？討論一討論一輸入格式：兩行，第一行一個(gè)整數(shù)n，第二行有2n個(gè)自然數(shù)。輸出格式：只有一行，若A有必勝策略，則輸出“YES”，否則輸出“NO”。輸入樣例：47 9 3 6 4 2 5 3輸出樣例：YES討論一討論一【分析】 若采用這樣一種策略，讓A方每次取數(shù)列兩端較大的那個(gè)數(shù)，則B方也會(huì)這樣取，對(duì)于樣例：7 9 3 6 4 2 5 3， A方會(huì)取得7、3、4、5， B方會(huì)取得9、6、2、3， A方的總和為19，B方的總和為20，按照規(guī)則，輸出

8、“NO”。討論一討論一【分析】如果A方取走奇數(shù)位置上的數(shù)后，剩下的兩端都是偶數(shù)位置上的數(shù)，如果A方取走偶數(shù)位置上的數(shù)后，剩下的兩端都是奇數(shù)位置上的數(shù)。A方既可以取走所有奇數(shù)位置上的數(shù)，或者取走所有偶數(shù)位置上的數(shù)。另一個(gè)策略：讓A方取“數(shù)和較大的奇（或偶）位置上的所有數(shù)”。討論一討論一參考程序參考程序readlnreadln(n);(n);for for i i:=1 to 2:=1 to 2* *n don do read(a read(ai i););sasa:=0;:=0;sbsb:=0;:=0;for for i i:=1 to n do:=1 to n dobeginbegin sas

9、a:=:=sa+asa+a22* *i-1;i-1; sbsb:=:=sb+asb+a22* *i i;end;end;if if sasa= =sbsbthen then writelnwriteln(NO)(NO)else else writelnwriteln(YES);(YES);經(jīng)典例題經(jīng)典例題【例3】排隊(duì)接水 有n個(gè)人在一個(gè)水龍頭前排隊(duì)接水，假如每個(gè)人接水的時(shí)間為Ti，請(qǐng)編程找出這n個(gè)人排隊(duì)的一種順序，使得這n個(gè)人平均等待時(shí)間最小。輸入樣例：1056 12 1 99 1000 234 33 55 99 812輸出樣例：291.90經(jīng)典例題經(jīng)典例題【分析】 平均等待時(shí)間就是每個(gè)人的等

10、待時(shí)間之和再除以n，因?yàn)閚是常數(shù)，所以等待時(shí)間之和最小也就等同于平均等待時(shí)間最小。Total=Ti1+(Ti1+Ti2)+(Ti1+Ti2+Ti3)+(Ti1+Ti2+Tin) =nTi1+(n-1)Ti2+(n-2)Ti3+Tin 如果讓Ti1最小，Ti2次小，Tin最大，也就是把接水時(shí)間少的人盡可能排在前面，總的等待時(shí)間就最少了。經(jīng)典例題經(jīng)典例題【例4】最大整數(shù) 設(shè)有n個(gè)正整數(shù)(nB，一般情況下有A+BB+A，但是當(dāng)A=B+C時(shí)，按字符串的大小定義有AB，但有可能會(huì)出現(xiàn)A+BB+A的情況，如A=121,B=12,則A+B=12112,B+A=12121,A+BB，按這一定義將所有的數(shù)字字符

11、串從大到小排序后連接起來(lái)所得到的數(shù)字字符串即是問(wèn)題的解。排序時(shí)先將所有字符串中的最大值選出來(lái)存在數(shù)組的第一個(gè)元素中，再?gòu)牡诙磷詈笠粋€(gè)元素中最大的字符串選出來(lái)存在數(shù)組的第二個(gè)元素中，直到從最后兩個(gè)元素中選出最大的字符串存在數(shù)組的倒數(shù)第二個(gè)元素中為止。經(jīng)典例題經(jīng)典例題參考程序參考程序for for i i:=1 to n-1 do:=1 to n-1 do for j:=i+1 to n do for j:=i+1 to n do if num if numi i+numjnumj+num+numjv，則將ai-v張紙牌從第i堆移動(dòng)到第i+1堆；（2）如果aiv，則將v-ai張紙牌從第i+1堆移

12、動(dòng)第i堆。經(jīng)典例題經(jīng)典例題【分析】從第i+1堆中取出紙牌給第i堆的過(guò)程中，可能會(huì)出現(xiàn)第i+1堆的紙牌數(shù)小于0的情況。如n3，三堆紙牌數(shù)為1、2、27，v10，要從第2堆移動(dòng)9張紙牌到第1堆，而第2堆只有2張紙牌可以移動(dòng)。按照規(guī)則會(huì)得到10、-7、27，再?gòu)牡?堆移動(dòng)17張紙牌到第2堆，即得到10、10、10。在移動(dòng)過(guò)程中，只要改變一下移動(dòng)的順序，而移動(dòng)的次數(shù)不會(huì)變。經(jīng)典例題經(jīng)典例題參考程序參考程序readlnreadln(n);(n); v:=0;v:=0;for for i i:=1 to n do:=1 to n dobeginbegin read(a read(ai i););v:=v:

13、=v+av+a i i;end;end;v:=v div n; s:=0;v:=v div n; s:=0;for for i i:=1 to n-1 do:=1 to n-1 do if a if ai ivv then begin then begin inc(s); ai+1:=ai+1+a inc(s); ai+1:=ai+1+ai i-v;-v; end; end;writelnwriteln(s);(s);討論二討論二【例6】合并果子（NOIP 2004） 在一個(gè)果園里，多多已經(jīng)將所有的果子打了下來(lái)，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。每一次合并，多多

14、可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經(jīng)過(guò)n-1次合并之后，就剩下一堆了。多多在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和。討論二討論二 因?yàn)檫€要花大力氣把這些果子搬回家，所以多多在合并果子時(shí)要盡可能地節(jié)省體力。假定每個(gè)果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案，使多多耗費(fèi)的體力最少，并輸出這個(gè)最小的體力耗費(fèi)值。 例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?，2堆合并，新堆數(shù)目為3，耗費(fèi)體力為3，接著，將新堆與原先的第3堆合并，又得到新的堆，數(shù)目為12，耗費(fèi)體力為12，所以多多總共耗費(fèi)體力為15。討論

15、二討論二【分析】 為了使最終的體力耗費(fèi)值最小，應(yīng)該每一次都選擇最小的兩堆果子合并，使每次合并耗費(fèi)的體力值最小。 算法過(guò)程： （1）讀入每堆果子的數(shù)目； （2）將果子數(shù)目按遞增順序進(jìn)行排序； （3）合并數(shù)目最少的兩堆果子，并增加體力耗費(fèi)值； （4）在果子序列中刪除合并的兩堆果子數(shù)目，增加合并后的果子數(shù)目； （5）重復(fù)步驟24，直到所有果子合并為一堆； （6）輸出體力耗費(fèi)值。討論二討論二【分析】上面的方法需要進(jìn)行n-1次排序，比較浪費(fèi)時(shí)間，可以用空間換時(shí)間的思路，另設(shè)一個(gè)數(shù)組存放每次合并后的堆。先讀入n堆果子的數(shù)目a，并按遞增順序進(jìn)行排列，得到一個(gè)序列a1an。再設(shè)另一個(gè)數(shù)組b，從a、b的第一個(gè)元

16、素開始找合并方案：（1）a數(shù)組的兩個(gè)元素合并；（2）a和b數(shù)組的一個(gè)元素合并；（3）b數(shù)組的兩個(gè)元素合并。將合并后的值放入b數(shù)組。參考程序參考程序p:=0; x:=1; y:=1; total:=0;p:=0; x:=1; y:=1; total:=0;for for i i:=1 to n-1 do:=1 to n-1 dobeginbegin min:= min:=maxlongintmaxlongint; ; if ax+ax+1min if ax+ax+1min then begin min:=ax+ax+1; t:=1; end; then begin min:=ax+ax+1; t

17、:=1; end; if ax+bymin if ax+bymin then begin min:=ax+by; t:=2; end; then begin min:=ax+by; t:=2; end; if by+by+1min if by+by+1min then begin min:=by+by+1; t:=3; end; then begin min:=by+by+1; t:=3; end; p:=p+1; bp:=min; p:=p+1; bp:=min; total total:=:=total+mintotal+min; ; if t=1 then x:=x+2; if t=1

18、then x:=x+2; if t=2 then begin x:=x+1; y:=y+1; if t=2 then begin x:=x+1; y:=y+1; if t=3 then y:=y+2; if t=3 then y:=y+2;end;end;writelnwriteln(total);(total);經(jīng)典例題經(jīng)典例題【例7】三國(guó)游戲（NOIP2010普及組第4題）雙方選將過(guò)程如下所示：武將相互之間的默契值：12345615281629272233201383226433115126經(jīng)典例題經(jīng)典例題【分析】1654323332經(jīng)典例題經(jīng)典例題【分析】1234567811111117

19、0211118013111501416011511161171818765432經(jīng)典例題經(jīng)典例題【分析】12345678111111170211118013111114160501511161171818765432經(jīng)典例題經(jīng)典例題【分析】 將所有邊按從大到小排序，檢查每條邊的兩個(gè)頂點(diǎn)是否已出現(xiàn)過(guò)，有三種情況： （1）兩個(gè)頂點(diǎn)都沒(méi)有出現(xiàn)過(guò)，說(shuō)明兩個(gè)武將都是自由的，不能同時(shí)取到，放棄該邊； （2）有一個(gè)頂點(diǎn)出現(xiàn)過(guò)，說(shuō)明這個(gè)武將前面可以被小涵先取到，現(xiàn)在可以取另一個(gè)頂點(diǎn)，該邊即為最大值； （3）兩個(gè)頂點(diǎn)都出現(xiàn)過(guò)，說(shuō)明這兩個(gè)武將前面都可以被小涵分別先取到，該邊即為最大值。討論三討論三【例8】火柴排隊(duì)

20、（NOIP2013提高組day1第2題） 涵涵有兩盒火柴，每盒裝有n根火柴，每根火柴都有一個(gè)高度。現(xiàn)在將每盒中的火柴各自排成一列，同一列火柴的高度互不相同，兩列火柴之間的距離定義為： ，其中ai表示第一列火柴中第i個(gè)火柴的高度，bi表示第二列火柴中第i個(gè)火柴的高度。 每列火柴中相鄰兩根火柴的位置都可以交換，請(qǐng)你通過(guò)交換使得兩列火柴之間的距離最小。請(qǐng)問(wèn)得到這個(gè)最小的距離，最少需要交換多少次？如果這個(gè)數(shù)字太大，請(qǐng)輸出這個(gè)最小交換次數(shù)對(duì)99,999,997取模的結(jié)果。2()1iinabi【輸入輸出樣例1】412 3 1 43 2 1 4【輸入輸出樣例說(shuō)明】最小距離是0，最少需要交換1次，比如：交換第1列的前2根火柴或者交換第2列的前2根火柴。【輸入輸出樣例2】421 3 4 21 7 2 4【輸入輸出樣例說(shuō)明】最小距離是10，最少需要交換2次，比如：交換第1列的中間2根火柴的位置，再交換第2列中后2根火柴的位置?！痉治觥?對(duì)距離公式化簡(jiǎn)得：要求 最小，就只需要 最大即可。這里有個(gè)貪心，當(dāng)a1a2an，b1b2b，cd，且ac+bdad+bc，則a(c-d)b(c-d)，則ab矛盾，所以ab，cd，則ac+bdad+bc將此式子進(jìn)行推廣：當(dāng)a1a2an，b1b2bn的情況下， 最大，即 最