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

基于貪心的算法和應(yīng)用舉例2014年7月贛榆高級中學(xué)貪心算法引入

【引例1】在n行m列的正整數(shù)矩陣中，要求從每行中選出1個數(shù)，使得選出的總共n個數(shù)的和最大。 【分析】要使總和最大，則每個數(shù)要盡可能大，自然應(yīng)該選每行中最大的那個數(shù)。貪心算法引入

【引例2】有1元、5元、10元、50元、100元、500元的硬幣各C1、C5、C10、C50、C100、C500枚?，F(xiàn)在要用這些硬幣來支付A元，最少需要多少枚硬幣？ 【分析】優(yōu)先使用面值大的硬幣。貪心算法定義

貪心算法是從問題的某一個初始狀態(tài)出發(fā)，通過逐步構(gòu)造最優(yōu)解的方法向給定的目標(biāo)前進(jìn)，并期望通過這種方法產(chǎn)生出一個全局最優(yōu)解的方法。方向紅箭頭表示當(dāng)前最優(yōu)決策；藍(lán)箭頭表示其他決策；小球表示當(dāng)前狀態(tài)。貪心算法的特點(diǎn)

貪心標(biāo)準(zhǔn)選擇：所謂貪心標(biāo)準(zhǔn)選擇就是應(yīng)用當(dāng)前“最好”的標(biāo)準(zhǔn)作為統(tǒng)一標(biāo)準(zhǔn)，將原問題變?yōu)橐粋€相似的但規(guī)模更小的子問題，而后的每一步都是當(dāng)前看似最佳的選擇。

最優(yōu)子結(jié)構(gòu)：當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心算法的特點(diǎn)

【引例3】部分背包問題

有一個背包，容量是M＝150，有7個物品，物品可以分割成任意大小，要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過總?cè)萘?。物品ABCDEFG體積35306050401025價(jià)值10403050354030貪心算法的特點(diǎn)

【分析】

有以下幾種策略可供選擇：

（1）每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？

（2）每次挑選所占空間最小的物品裝入是否能得到最優(yōu)解？

（3）每次選取單位容量價(jià)值最大的物品。貪心算法的特點(diǎn)

解題一般步驟: 1、設(shè)計(jì)數(shù)據(jù)找規(guī)律； 2、進(jìn)行貪心猜想； 3、正確性證明（嚴(yán)格證明和一般證明） ★一般證明：列舉反例； ★嚴(yán)格證明：數(shù)學(xué)歸納和反證法； 4、程序?qū)崿F(xiàn)。經(jīng)典例題※刪數(shù)問題（NOI1995）※取數(shù)問題（IOI1996）※接水問題※最大整數(shù)※均分紙牌（NOIP2002）※合并果子（NOIP2004）※三國游戲（NOIP2010）※火柴排隊(duì)（NOIP2013）※貨車運(yùn)輸（NOIP2013）【例1】刪數(shù)問題（NOI1994）

鍵盤輸入一個高精度的正整數(shù)N，去掉其中任意S個數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。

輸出剩下的最小數(shù)。經(jīng)典例題經(jīng)典例題

【分析】

因?yàn)橐獎h除S個數(shù)字，可以一個一個地刪，每一次刪除的目的都是使剩下的數(shù)盡量小。

那么在每一次刪除時，應(yīng)該選擇哪個數(shù)字呢？最大的那個數(shù)字？還是最左邊的那個數(shù)字？

例如5768，刪除7可以使剩余的數(shù)最小。經(jīng)典例題

結(jié)論：

每一次刪除的數(shù)字應(yīng)該是這個數(shù)字序列中最左邊遞減序列的第一個數(shù)字。具體操作為，按高位到低位的方向搜索遞減區(qū)間。若不存在遞減區(qū)間，則刪除尾數(shù)字，否則刪除遞減區(qū)間的首數(shù)符，這樣就形成一個最小的數(shù)。

重復(fù)上述規(guī)則，直到刪除S個數(shù)字為止。經(jīng)典例題

例如：N＝8796542，S＝4

第一次：N＝8796542，刪除8；

第二次：N＝796542，刪除9；

第三次：N＝76542，刪除7；

第四次：N＝6542，刪除6，得到542。經(jīng)典例題

參考程序 readln(n); readln(s); fork:=1tosdo begin i:=1; while(i<length(n))and(n[i]<=n[i+1])do inc(i); delete(n,i,1); end;

while(length(n)>1)and(n[1]=‘0’)dodelete(n,1,1) writeln(n);討論一

【例2】取數(shù)問題（IOI1996）

給出2n（n≤100）個自然數(shù)（小于等于30000），將這2n個自然數(shù)排成一列，游戲雙方A和B從中輪流取數(shù)，只允許從兩端取數(shù)，A方先取，然后B方再取。取完時，誰取的數(shù)字總和最大為取勝方；若雙方和相等，則B勝，試問A方是否有必勝策略？討論一

輸入格式：兩行，第一行一個整數(shù)n，第二行有2n個自然數(shù)。

輸出格式：只有一行，若A有必勝策略，則輸出“YES”，否則輸出“NO”。

輸入樣例： 4 79364253

輸出樣例： YES討論一 【分析】

若采用這樣一種策略，讓A方每次取數(shù)列兩端較大的那個數(shù)，則B方也會這樣取，對于樣例：79364253， A方會取得7、3、4、5， B方會取得9、6、2、3， A方的總和為19，B方的總和為20，按照規(guī)則，輸出“NO”。討論一

【分析】

如果A方取走奇數(shù)位置上的數(shù)后，剩下的兩端都是偶數(shù)位置上的數(shù)，如果A方取走偶數(shù)位置上的數(shù)后，剩下的兩端都是奇數(shù)位置上的數(shù)。 A方既可以取走所有奇數(shù)位置上的數(shù)，或者取走所有偶數(shù)位置上的數(shù)。

另一個策略：讓A方取“數(shù)和較大的奇（或偶）位置上的所有數(shù)”。討論一

參考程序 readln(n); fori:=1to2*ndo read(a[i]); sa:=0; sb:=0; fori:=1tondo begin sa:=sa+a[2*i-1]; sb:=sb+a[2*i]; end; ifsa=sb thenwriteln(‘NO’) elsewriteln(‘YES’);經(jīng)典例題 【例3】排隊(duì)接水

有n個人在一個水龍頭前排隊(duì)接水，假如每個人接水的時間為Ti，請編程找出這n個人排隊(duì)的一種順序，使得這n個人平均等待時間最小。

輸入樣例： 10 56121991000234335599812

輸出樣例： 291.90經(jīng)典例題

【分析】

平均等待時間就是每個人的等待時間之和再除以n，因?yàn)閚是常數(shù)，所以等待時間之和最小也就等同于平均等待時間最小。 Total=Ti1+(Ti1+Ti2)+(Ti1+Ti2+Ti3)+…(Ti1+Ti2+…+Tin) =nTi1+(n-1)Ti2+(n-2)Ti3+…+Tin

如果讓Ti1最小，Ti2次小，…，Tin最大，也就是把接水時間少的人盡可能排在前面，總的等待時間就最少了。經(jīng)典例題【例4】最大整數(shù)

設(shè)有n個正整數(shù)(n<=20,Longint范圍內(nèi)),將它們聯(lián)接成一排組成一個最大的多位整數(shù)。

例如:n=3時,3個整數(shù)13,312,343聯(lián)接成的最大整數(shù)為:34331213。

又如:n=4時,4個整數(shù)7,13,4,246聯(lián)接成的最大整數(shù)為:7424613。

程序輸入:n及n個數(shù)。

程序輸出:聯(lián)接成的多位數(shù)。經(jīng)典例題 【分析】

本例因?yàn)樯婕皩蓚€自然數(shù)連接起來的問題，采用字符串來處理比較方便。首先我們自然會想到大的字符串應(yīng)該排在前面，因?yàn)槿绻鸄與B是兩個由數(shù)字字符構(gòu)成的字符串且A>B，一般情況下有A+B>B+A，但是當(dāng)A=B+C時，按字符串的大小定義有A>B，但有可能會出現(xiàn)A+B<B+A的情況，如A=121,B=12,則A+B=12112,B+A=12121,A+B<B+A。經(jīng)典例題 【分析】

根據(jù)題意用另一種字符串比較辦法，將A+B與B+A相比較，如果前者大于后者，則認(rèn)為A>B，按這一定義將所有的數(shù)字字符串從大到小排序后連接起來所得到的數(shù)字字符串即是問題的解。排序時先將所有字符串中的最大值選出來存在數(shù)組的第一個元素中，再從第二至最后一個元素中最大的字符串選出來存在數(shù)組的第二個元素中，直到從最后兩個元素中選出最大的字符串存在數(shù)組的倒數(shù)第二個元素中為止。經(jīng)典例題

參考程序 fori:=1ton-1doforj:=i+1tondoifnum[i]+num[j]<num[j]+num[i]thenbegintemp:=num[i];num[i]:=num[j];num[j]:=tempend; fori:=1tondo write(num[i]); writeln;經(jīng)典例題

【例5】均分紙牌（NOIP2002）

有N堆紙牌，編號分別為1，2，……，N。第i堆有a[i]張紙牌（a[i]≤10000）,但紙牌總數(shù)必為N的倍數(shù)?？梢栽谌我欢焉先∪舾蓮埣埮?，然后移動。移牌規(guī)則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N－1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆牌數(shù)都一樣多。經(jīng)典例題

例如：N＝4，紙牌數(shù)分別為9、8、17、6，移動3次可達(dá)到目的。

第一次：從第3堆取4張牌放到第4堆； 9、8、13、10

第二次：從第3堆取3張牌放到第2堆； 9、11、10、10

第三次：從第2堆取1張牌放到第1堆。 10、10、10、10經(jīng)典例題 【分析】

設(shè)v為均分后每堆紙牌的張數(shù)，s為最少移動次數(shù)。按照從左到右的順序移動紙牌。如果第i堆的紙牌數(shù)a[i]不等于v，則移動一次，分兩種情況移動：

（1）如果a[i]>v，則將a[i]-v張紙牌從第i堆移動到第i+1堆；

（2）如果a[i]<v，則將v-a[i]張紙牌從第i+1堆移動第i堆。經(jīng)典例題 【分析】

從第i+1堆中取出紙牌給第i堆的過程中，可能會出現(xiàn)第i+1堆的紙牌數(shù)小于0的情況。如n＝3，三堆紙牌數(shù)為1、2、27，v＝10，要從第2堆移動9張紙牌到第1堆，而第2堆只有2張紙牌可以移動。按照規(guī)則會得到10、-7、27，再從第3堆移動17張紙牌到第2堆，即得到10、10、10。在移動過程中，只要改變一下移動的順序，而移動的次數(shù)不會變。經(jīng)典例題

參考程序 readln(n); v:=0; fori:=1tondo begin read(a[i]); v:=v+a[i]; end; v:=vdivn;s:=0; fori:=1ton-1do ifa[i]<>v thenbegin inc(s);a[i+1]:=a[i+1]+a[i]-v; end; writeln(s);討論二 【例6】合并果子（NOIP2004）

在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯?，所有的果子經(jīng)過n-1次合并之后，就剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。討論二

因?yàn)檫€要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案，使多多耗費(fèi)的體力最少，并輸出這個最小的體力耗費(fèi)值。

例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?，2堆合并，新堆數(shù)目為3，耗費(fèi)體力為3，接著，將新堆與原先的第3堆合并，又得到新的堆，數(shù)目為12，耗費(fèi)體力為12，所以多多總共耗費(fèi)體力為15。討論二

【分析】

為了使最終的體力耗費(fèi)值最小，應(yīng)該每一次都選擇最小的兩堆果子合并，使每次合并耗費(fèi)的體力值最小。

算法過程：

（1）讀入每堆果子的數(shù)目；

（2）將果子數(shù)目按遞增順序進(jìn)行排序；

（3）合并數(shù)目最少的兩堆果子，并增加體力耗費(fèi)值；

（4）在果子序列中刪除合并的兩堆果子數(shù)目，增加合并后的果子數(shù)目；

（5）重復(fù)步驟2－4，直到所有果子合并為一堆；

（6）輸出體力耗費(fèi)值。討論二

【分析】

上面的方法需要進(jìn)行n-1次排序，比較浪費(fèi)時間，可以用空間換時間的思路，另設(shè)一個數(shù)組存放每次合并后的堆。

先讀入n堆果子的數(shù)目a，并按遞增順序進(jìn)行排列，得到一個序列a[1]……a[n]。

再設(shè)另一個數(shù)組b，從a、b的第一個元素開始找合并方案：

（1）a數(shù)組的兩個元素合并；

（2）a和b數(shù)組的一個元素合并；

（3）b數(shù)組的兩個元素合并。

將合并后的值放入b數(shù)組。

參考程序

p:=0;x:=1;y:=1;total:=0; fori:=1ton-1do begin min:=maxlongint; ifa[x]+a[x+1]<min thenbeginmin:=a[x]+a[x+1];t:=1;end; ifa[x]+b[y]<min thenbeginmin:=a[x]+b[y];t:=2;end; ifb[y]+b[y+1]<min thenbeginmin:=b[y]+b[y+1];t:=3;end; p:=p+1;b[p]:=min;total:=total+min; ift=1thenx:=x+2; ift=2thenbeginx:=x+1;y:=y+1; ift=3theny:=y+2; end; writeln(total);經(jīng)典例題【例7】三國游戲（NOIP2010普及組第4題）雙方選將過程如下所示：武將相互之間的默契值：12345615281629272233201383226433115126經(jīng)典例題

【分析】1654323332經(jīng)典例題

【分析】12345678111111170211118013111501416011511161171818765432經(jīng)典例題

【分析】12345678111111170211118013111114160501511161171818765432經(jīng)典例題 【分析】

將所有邊按從大到小排序，檢查每條邊的兩個頂點(diǎn)是否已出現(xiàn)過，有三種情況：

（1）兩個頂點(diǎn)都沒有出現(xiàn)過，說明兩個武將都是自由的，不能同時取到，放棄該邊；

（2）有一個頂點(diǎn)出現(xiàn)過，說明這個武將前面可以被小涵先取到，現(xiàn)在可以取另一個頂點(diǎn)，該邊即為最大值；

（3）兩個頂點(diǎn)都出現(xiàn)過，說明這兩個武將前面都可以被小涵分別先取到，該邊即為最大值。討論三

【例8】火柴排隊(duì)（NOIP2013提高組day1第2題）

涵涵有兩盒火柴，每盒裝有n根火柴，每根火柴都有一個高度?，F(xiàn)在將每盒中的火柴各自排成一列，同一列火柴的高度互不相同，兩列火柴之間的距離定義為：

，其中ai表示第一列火柴中第i個火柴的高度，bi表示第二列火柴中第i個火柴的高度。

每列火柴中相鄰兩根火柴的位置都可以交換，請你通過交換使得兩列火柴之間的距離最小。請問得到這個最小的距離，最少需要交換多少次？如果這個數(shù)字太大，請輸出這個最小交換次數(shù)對99,999,997取模的結(jié)果。 【輸入輸出樣例1】 4 1 2314 3214 【輸入輸出樣例說明】

最小距離是0，最少需要交換1次，比如：交換第1列的前2根火柴或者交換第2列的前2根火柴。 【輸入輸出樣例2】 4 2 1342 1724 【輸入輸出樣例說明】

最小距離是10，最少需要交換2次，比如：交換第1列的中間2根火柴的位置，再交換第2列中后2根火柴的位置。

【分析】

對距離公式化簡得：

要求最小，就只需要最大即可。

這里有個貪心，當(dāng)a1<a2<…<an，b1<b2<…<bn時，

最大。

證明如下：

若存在a>b，c>d，且ac+bd<ad+bc，則a(c-