普及講座6基于貪心的算法和應(yīng)用舉例C版課件

江蘇省大豐高級中學(xué)陳鵬PengChenJiangSuDaFengSeniorHighSchool基于貪心的算法和應(yīng)用舉例

GreedySelectorAlgorithm&Application[一]貪心策略

[二]應(yīng)用舉例

[三]小結(jié)10六月20232[一]貪心策略『引例1』——刪數(shù)問題鍵盤輸入一個高精度的正整數(shù)n（n<=240），去掉其中任意s個數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的n和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小。【算法分析】每一步總是選擇一個使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個數(shù)字；否則刪除第一個遞減區(qū)間的首字符。10六月20233[一]貪心策略『定義』——貪心貪心算法是從問題的某一個初始狀態(tài)出發(fā)，通過逐步構(gòu)造最優(yōu)解的方法向給定的目標(biāo)前進(jìn)，并期望通過這種方法產(chǎn)生出一個全局最優(yōu)解的方法。小球表示當(dāng)前狀態(tài)；紅箭頭表示當(dāng)前最優(yōu)決策；藍(lán)箭頭表示其他決策。10六月20234方向[一]貪心策略

貪心標(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ì)。10六月20235[一]貪心策略『引例2』——金銀島某天KID利用飛行器飛到了一個金銀島上，上面有許多珍貴的金屬，KID喜歡各種寶石的藝術(shù)品，可是也不拒絕這樣珍貴的金屬。但是他只帶著一個口袋，口袋至多只能裝重量為w的物品。島上金屬有s個種類,每種金屬重量不同，分別為n1，n2，…，ns，同時每個種類的金屬總的價值也不同，分別為v1，v2，…，vs。KID想一次帶走價值盡可能多的金屬，問他最多能帶走價值多少的金屬。注意到金屬是可以被任意分割的，并且金屬的價值和其重量成正比。10六月20236[一]貪心策略【算法分析】有以下幾種策略可供選擇：（1）每次挑選價值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？（2）每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解？（3）每次選取單位重量價值最大的物品。10六月20237[一]貪心策略解題一般步驟:1、設(shè)計數(shù)據(jù)找規(guī)律；2、進(jìn)行貪心猜想；3、正確性證明（嚴(yán)格證明和一般證明）★一般證明：列舉反例；★嚴(yán)格證明：數(shù)學(xué)歸納和反證法；4、程序?qū)崿F(xiàn)。10六月20238[二]應(yīng)用舉例『例1』——三國游戲【問題描述】小涵很喜歡一個叫做《三國》的游戲。在游戲中，小涵和計算機(jī)各執(zhí)一方，組建各自的軍隊進(jìn)行對戰(zhàn)。游戲中共有N位武將（N為偶數(shù)且不小于4），任意兩個武將之間有一個“默契值”，表示若此兩位武將作為一對組合作戰(zhàn)時，該組合的威力有多大。游戲開始前，所有武將都是自由的（稱為自由武將，一旦某個自由武將被選中作為某方軍隊的一員，那么他就不再是自由武將了），換句話說，所謂的自由武將不屬于任何一方。游戲開始，小涵和計算機(jī)要從自由武將中挑選武將組成自己的軍隊，規(guī)則如下：小涵先從自由武將中選出一個加入自己的軍隊，然后計算機(jī)也從自由武將中選出一個加入計算機(jī)方的軍隊。10六月20239[二]應(yīng)用舉例接下來一直按照“小涵→計算機(jī)→小涵→…”的順序選擇武將，直到所有的武將被雙方均分完。然后，程序自動從雙方軍隊中各挑出一對默契值最高的武將組合代表自己的軍隊進(jìn)行二對二比武，擁有更高默契值的一對武將組合獲勝，表示兩軍交戰(zhàn)，擁有獲勝武將組合的一方獲勝。已知計算機(jī)一方選擇武將的原則是盡量破壞對手下一步將形成的最強(qiáng)組合，它采取的具體策略如下：任何時刻，輪到計算機(jī)挑選時，它會嘗試將對手軍隊中的每個武將與當(dāng)前每個自由武將進(jìn)行一一配對，找出所有配對中默契值最高的那對武將組合，并將該組合中的自由武將選入自己的軍隊。10六月202310[二]應(yīng)用舉例下面舉例說明計算機(jī)的選將策略，例如，游戲中一共有6個武將，他們相互之間的默契值如下表所示雙方選將過程如下所示：10六月202311武將相互之間的默契值：雙方選將過程入圖所示：[二]應(yīng)用舉例小涵想知道，如果計算機(jī)在一局游戲中始終堅持上面這個策略，那么自己有沒有可能必勝？如果有，在所有可能的勝利結(jié)局中，自己那對用于比武的武將組合的默契值最大是多少？假設(shè)整個游戲過程中，對戰(zhàn)雙方任何時候均能看到自由武將隊中的武將和對方軍隊的武將。為了簡化問題，保證對于不同的武將組合，其默契值均不相同。10六月202312[二]應(yīng)用舉例【算法分析】由于計算機(jī)的貪心策略，每一個武將不可能與和他默契度最大的武將合作，但要與和他默契度次大的武將合作，變得非常容易，小涵只需要經(jīng)過兩次挑選。

只要小涵選出默契度次大值中最大的那對武將，那么他將穩(wěn)操勝券。10六月202313[二]應(yīng)用舉例10六月202314123456152816292722332013832264331151261654323332[二]應(yīng)用舉例10六月20231512345678111111170211118013111501416011511161171818765432[二]應(yīng)用舉例10六月20231612345678111111170211118013111114160501511161171818765432[二]應(yīng)用舉例【算法分析】將所有邊按從大到小排序，檢查每條邊的兩個頂點是否已出現(xiàn)過，有三種情況：（1）兩個頂點都沒有出現(xiàn)過，說明兩個武將都是自由的，不能同時取到，放棄該邊；（2）有一個頂點出現(xiàn)過，說明這個武將前面可以被小涵先取到，現(xiàn)在可以取另一個頂點，該邊即為最大值；（3）兩個頂點都出現(xiàn)過，說明這兩個武將前面都可以被小涵分別先取到，該邊即為最大值。10六月202317[二]應(yīng)用舉例【參考程序片斷】constintN=505;inlineintread(){charc=getchar();intx=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}returnx*f;}intn,m,ans,a[N][N];intmain(){n=read();for(inti=1;i<=n;i++)for(intj=i+1;j<=n;j++)a[i][j]=a[j][i]=read();10六月202318[二]應(yīng)用舉例

for(inti=1;i<=n;i++){intt1=0,t2=0;for(intj=1;j<=n;j++){if(a[i][j]>t1)t2=t1,t1=a[i][j];elseif(a[i][j]>t2)t2=a[i][j];}ans=max(ans,t2);}

printf("1\n%d",ans);}10六月202319[二]應(yīng)用舉例『例2』——推銷員【問題描述】阿明是一名推銷員，他奉命到螺絲街推銷他們公司的產(chǎn)品。螺絲街是一條死胡同，出口與入口是同一個，街道的一側(cè)是圍墻，另一側(cè)是住戶。螺絲街一共有N家住戶，第i家住戶到入口的距離為Si米。由于同一棟房子里可以有多家住戶，所以可能有多家住戶與入口的距離相等。阿明會從入口進(jìn)入，依次向螺絲街的X家住戶推銷產(chǎn)品，然后再原路走出去。阿明每走1米就會積累1點疲勞值，向第i家住戶推銷產(chǎn)品會積累Ai點疲勞值。阿明是工作狂，他想知道，對于不同的X，在不走多余的路的前提下，他最多可以積累多少點疲勞值。10六月202320[二]應(yīng)用舉例【輸入格式】第一行為一個正整數(shù)N，表示螺絲街住戶的數(shù)量。接下來的一行為N個正整數(shù)，其中：第i個整數(shù)Si表示第i家住戶到入口的距離。數(shù)據(jù)保證S1<=S2<=…<=Sn<10^8。接下來的一行為N個正整數(shù)，其中：第i個整數(shù)Ai表示向第i戶住戶推銷產(chǎn)品會積累的疲勞值。數(shù)據(jù)保證Ai<10^3。【輸出格式】輸出N行，每行一個正整數(shù)，第i行整數(shù)表示當(dāng)X=i時，阿明最多積累的疲勞值。10六月202321[二]應(yīng)用舉例【輸入輸出樣例】輸入：輸出：51512345191234522242510六月202322[二]應(yīng)用舉例【樣例說明】10六月202323S

12345

A

12345起點疲勞值1S

12345

A

12345起點疲勞值1234[二]應(yīng)用舉例10六月202324S

12345

A

12345起點疲勞值123S

12345

A

12345起點疲勞值12[二]應(yīng)用舉例【算法分析】題目中所說不走多余路的意思就是推銷x的房子的時候必須一口氣走完，不能繞來繞去，這樣就更能說明了這樣的貪心策略是可以的。如何選取當(dāng)前那一個疲勞值最大的房子呢？對于一個沒來過的房子（偏向右端），價值就是s[i]*2+a[i]，這里指的是第一個，接下來就不一樣了，每一次接下來選擇的都是阿明走過最遠(yuǎn)房子的左端或右端中價值最大的房子。對于左端，因為不能走多余的路，所以價值就是a[i]，右端呢，需要加上往返的距離，所以價值就是a[i]+(s[i]-now)*2，其中now指的就是阿明走過最遠(yuǎn)房子的位置，然后取一個最大值即可。10六月202325[二]應(yīng)用舉例【算法分析】

貪心策略：每次訪問的位置＝max{max(已訪問的最遠(yuǎn)位置的左邊疲勞值)，max(已訪問的最遠(yuǎn)位置到某個位置距離*2+疲勞值)}。10六月202326起點已訪問的最遠(yuǎn)位置疲勞值距離*2+疲勞值[二]應(yīng)用舉例【參考程序片斷】right=0;r[i]=r[i-1]+max;f[sel]=false;for(i=1;i<=n;i++){ifsel>rightright=sel;max:=0;cout<<r[i];for(j=1;i<=right-1;j++)}iff[j]&&(a[j]>max){max=a[j];sel=j;}for(j=right+1;j<=n;j++)iff[j]&&(a[j]+(s[j]-s[right])*2>max){max=a[j]+(s[j]-s[right])*2;sel=j;}10六月202327[二]應(yīng)用舉例『例3』——電池的壽命【問題描述】小S新買了一個掌上游戲機(jī)，這個游戲機(jī)由兩節(jié)5號電池供電。為了保證能夠長時間玩游戲，他買了很多5號電池，這些電池的生產(chǎn)商不同，質(zhì)量也有差異，因而使用壽命也有所不同，有的能使用5個小時，有的可能就只能使用3個小時。顯然如果他只有兩個電池一個能用5小時一個能用3小時，那么他只能玩3個小時的游戲，有一個電池剩下的電量無法使用，但是如果他有更多的電池，就可以更加充分地利用它們，比如他有三個電池分別能用3、3、5小時，他可以先使用兩節(jié)能用3個小時的電池，使用半個小時后再把其中一個換成能使用5個小時的電池，兩個半小時后10六月202328[二]應(yīng)用舉例再把剩下的一節(jié)電池?fù)Q成剛才換下的電池（那個電池還能用2.5個小時），這樣總共就可以使用5.5個小時，沒有一點浪費?，F(xiàn)在已知電池的數(shù)量和電池能夠使用的時間，請你找一種方案使得使用時間盡可能的長。10六月202329[二]應(yīng)用舉例【輸入格式】輸入包含多組測試數(shù)據(jù)。每組測試數(shù)據(jù)包括兩行，第一行為一個整數(shù)N（2<=N<=1000），表示電池的數(shù)目。接下來的一行為N個正整數(shù)，表示電池能使用的時間。【輸出格式】對每組數(shù)據(jù)輸出一行，表示電池能使用的時間，結(jié)果保留到小數(shù)點后1位。10六月202330[二]應(yīng)用舉例【輸入輸出樣例】輸入：輸出：23.035