NOIP基本算法之貪心

貪心算法一、貪心策略的基本思想定義：貪心法是一種解決最優(yōu)問題的策略。它是從問題的初始解出發(fā)，按照當(dāng)前最佳的選擇，把問題歸納為更小的相似的子問題，并使子問題最優(yōu)，再由子問題來推導(dǎo)出全局最優(yōu)解。使用貪心方法需要注意局部最優(yōu)與全局最優(yōu)的關(guān)系，選擇當(dāng)前狀態(tài)的局部最優(yōu)并不一定能推導(dǎo)出問題的全局最優(yōu)。二、貪心策略的特點(diǎn)1貪心選擇性質(zhì)：算法中每一步選擇都是當(dāng)前看似最佳的選擇，這種選擇依賴于已做出的選擇，但不依賴于未做的選擇。2最優(yōu)子結(jié)構(gòu)性質(zhì)：算法中每一次都取得了最優(yōu)解即局部最優(yōu)解，要保證最后的結(jié)果最優(yōu)，則必須滿足全局最優(yōu)解包含局部最優(yōu)解。但并不是所有具有最優(yōu)子結(jié)構(gòu)的問題都可以用貪心策略求解。因?yàn)樨澬耐敲つ康?，需要使用更理性的方法——動態(tài)規(guī)劃（例如“0-1背包問題”與“部分背包問題”）三、貪心策略與其他算法的區(qū)別1貪心與遞推：與遞推不同的是，貪心法中推進(jìn)的每一步不是依據(jù)某一固定的遞推式，而是當(dāng)前看似最佳的貪心決策，不斷的將問題歸納為更加小的相似的子問題。所以歸納、分析、選擇正確合適的貪心策略，是正確解決貪心問題的關(guān)鍵。2貪心與動態(tài)規(guī)劃：與動態(tài)規(guī)劃不同的是，貪心是鼠目寸光；動態(tài)規(guī)劃是統(tǒng)攬全局。四、貪心策略的證明貪心策略能否適用，關(guān)鍵看在貪心的策略下，局部的最優(yōu)解能否得到全局最優(yōu)解。要看是否得到最優(yōu)解，就要看貪心選擇特征的證明了。常用的證明法有反證法和構(gòu)造法。1反證法：顧名思義，對于當(dāng)前的貪心策略，否定當(dāng)前的選擇，看看是否能得到最優(yōu)解，如果不能得到，說明當(dāng)前貪心策略是正確的；否則，當(dāng)前策略不正確，不可用。2構(gòu)造法：對于題目給出的問題，用貪心策略時，把問題構(gòu)造成已知的算法或數(shù)據(jù)結(jié)構(gòu)，以此證明貪心策略是正確的。五、幾個簡單的貪心例子貪心策略【例1】在N行M列的正整數(shù)矩陣中，要求從每行中選出1個數(shù)，使得選出的總共N個數(shù)的和最大?！舅惴ǚ治觥恳箍偤妥畲?，則每個數(shù)要盡可能大，自然應(yīng)該選每行中最大的那個數(shù)。因此，我們設(shè)計出如下算法:讀入N,M,矩陣數(shù)據(jù)；Total:=0;ForI:=1toNdobegin //對N行進(jìn)行選擇選擇第I行最大的數(shù),記為；Total:=Total；End；輸出最大總和Total；

【例2】部分背包問題給定一個最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價值為Vi元/公斤，編程確定一個裝貨方案，使得裝入卡車中的所有物品總價值最大。

【算法分析】因?yàn)槊恳粋€物品都可以分割成單位塊，單位塊的利益越大顯然總收益越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解答，方法如下：先將單位塊收益按從大到小進(jìn)行排列，然后用循環(huán)從單位塊收益最大的取起，直到不能取為止便得到了最優(yōu)解。因此我們非常容易設(shè)計出如下算法：問題初始化； //讀入數(shù)據(jù)按Vi從大到小將商品排序；I:=1;re=0thenBrea; //如果卡車滿載則跳出循環(huán)M:=M-Wi;ifM>=0then將第I種商品全部裝入卡車else將MWi重量的物品I裝入卡車;I:=I1; //選擇下一種商品untilM<=0ORI>N在解決上述問題的過程中，首先根據(jù)題設(shè)條件，找到了貪心選擇標(biāo)準(zhǔn)Vi，并依據(jù)這個標(biāo)準(zhǔn)直接逐步去求最優(yōu)解，這種解題策略被稱為貪心法。貪心策略解題，需要解決兩個問題：1、確定問題是否能用貪心策略求解；一般來說，適用于貪心策略求解的問題具有以下特點(diǎn)：①可通過局部的貪心選擇來達(dá)到問題的全局最優(yōu)解。②原問題的最優(yōu)解包含子問題的最優(yōu)解，即問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。2、如何選擇一個貪心標(biāo)準(zhǔn)？正確的貪心標(biāo)準(zhǔn)可以得到問題的最優(yōu)解，在確定采用貪心策略解決問題時，不能隨意的判斷貪心標(biāo)準(zhǔn)是否正確，尤其不要被表面上看似正確的貪心標(biāo)準(zhǔn)所迷惑。在得出貪心標(biāo)準(zhǔn)之后應(yīng)給予嚴(yán)格的數(shù)學(xué)證明。0-1背包問題給定一個最大載重量為M的卡車和N種動物。已知第i種動物的重量為Wi，其最大價值為Vi，設(shè)定M，Wi，Vi均為整數(shù)，編程確定一個裝貨方案，使得裝入卡車中的所有動物總價值最大?！痉治觥繉τ贜種動物，要么被裝，要么不裝，也就是說在滿足卡車載重的條件下，如何選擇動物，使得動物價值最大的問題。即確定一組1，2，…，n，i∈{0,1}f=ma∑i*Vi其中，∑i*Wi≦W從直觀上來看，我們可以按照上例一樣選擇那些價值大，而重量輕的動物。也就是可以按價值質(zhì)量比（Vi/Wi）的大小來進(jìn)行選擇?？梢钥闯?，每做一次選擇，都是從剩下的動物中選擇那些Vi/Wi最大的，這種局部最優(yōu)的選擇是否能滿足全局最優(yōu)呢？我們來看看一個簡單的例子：設(shè)N=3，卡車最大載重量是100，三種動物A、B、C的重量分別是40，50，70，其對應(yīng)的總價值分別是80、100、150。情況A：按照上述思路，三種動物的Vi/Wi分別為2,2,214。顯然，我們首先選擇動物C，得到價值150，然后任意選擇A或B，由于卡車最大載重為100，因此卡車不能裝載其他動物。情況B：不按上述約束條件，直接選擇A和B?？梢缘玫絻r值80100=180，卡車裝載的重量為4050=90。沒有超過卡車的實(shí)際載重，因此也是一種可行解，顯然，這種解比上一種解要優(yōu)化。問題出現(xiàn)在什么地方呢？我們看看圖23從圖23中明顯可以看出，情況A，卡車的空載率比情況B高。也就是說，上面的分析，只考慮了貨物的價值質(zhì)量比，而沒有考慮到卡車的運(yùn)營效率，因此，局部的最優(yōu)化，不能導(dǎo)致全局的最優(yōu)化。因此，貪心不能簡單進(jìn)行，而需要全面的考慮，最后得到證明?！纠?】排隊打水問題有N個人排隊到R個水龍頭去打水，他們裝滿水桶的時間為T1，T2，…，Tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們花費(fèi)的時間最少？【算法分析】由于排隊時，越靠前面的計算的次數(shù)越多，顯然越小的排在越前面得出的結(jié)果越?。梢杂脭?shù)學(xué)方法簡單證明，這里就不再贅述），所以這道題可以用貪心法解答，基本步驟：1將輸入的時間按從小到大排序；2將排序后的時間按順序依次放入每個水龍頭的隊列中；3統(tǒng)計，輸出答案?！緲永斎搿?2//4人打水，2個水龍頭2645//每個打水時間【樣例輸出】23//總共花費(fèi)時間參考程序主要框架如下：readn,r;FillcharS,SieofS,0;J:=0;Min:=0;ForI:=1ToNDo//用貪心法求解BeginIncJ;IfJ=R1ThenJ:=1;S;End;WritelnMin;//輸出解答【例4】均分紙牌（NOIP2002）有N堆紙牌，編號分別為1，2，…,N。每堆上有若干張，但紙牌總數(shù)必為N的倍數(shù)?？梢栽谌我欢焉先∪舾蓮埣埮?，然后移動。移牌規(guī)則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。現(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。例如N=4，4堆紙牌數(shù)分別為：①9②8③17④6移動3次可達(dá)到目的：從③取4張牌放到④（981310）->從③取3張牌放到②（9111010）->從②取1張牌放到①（10101010）?！据斎敫袷健縉（N堆紙牌，1<=N<=100）A1A2…An（N堆紙牌，每堆紙牌初始數(shù)，l<=Ai<=10000）【輸出格式】所有堆均達(dá)到相等時的最少移動次數(shù)?！緲永斎搿?98176【樣例輸出】3【算法分析】如果你想到把每堆牌的張數(shù)減去平均張數(shù)，題目就變成移動正數(shù)，加到負(fù)數(shù)中，使大家都變成0，那就意味著成功了一半！拿例題來說，平均張數(shù)為10,原張數(shù)9，8，17，6，變?yōu)?1，-2，7，-4，其中沒有為0的數(shù)，我們從左邊出發(fā)：要使第1堆的牌數(shù)-1變?yōu)?，只須將-1張牌移到它的右邊（第2堆）-2中；結(jié)果是-1變?yōu)?，-2變?yōu)?3，各堆牌張數(shù)變?yōu)?，-3，7，-4；同理：要使第2堆變?yōu)?，只需將-3移到它的右邊（第3堆）中去，各堆牌張數(shù)變?yōu)?，0，4，-4；要使第3堆變?yōu)?，只需將第3堆中的4移到它的右邊（第4堆）中去，結(jié)果為0，0，0，0，完成任務(wù)。每移動1次牌，步數(shù)加1。也許你要問，負(fù)數(shù)張牌怎么移，不違反題意嗎？其實(shí)從第i堆移動-m張牌到第i1堆，等價于從第i1堆移動m張牌到第i堆，步數(shù)是一樣的。如果張數(shù)中本來就有為0的，怎么辦呢？如0，-1，-5，6，還是從左算起（從右算起也完全一樣），第1堆是0，無需移牌，余下與上相同；再比如-1，-2，3，10，-4，-6，從左算起，第1次移動的結(jié)果為0，-3，3，10，-4，-6；第2次移動的結(jié)果為0，0，0，10，-4，-6，現(xiàn)在第3堆已經(jīng)變?yōu)?了，可節(jié)省1步，余下繼續(xù)。參考程序主要框架如下：ave:=0;step:=0;fori:=1tondobeginreada;//讀入各堆牌張數(shù)，求總張數(shù)aveend;ave:=avedivn;//求牌的平均張數(shù)avefori:=1tondoa-ave;//每堆牌的張數(shù)減去平均數(shù)i:=1;j:=n;whilea=0andi<ndoinci;//過濾左邊的0whilea=0andj>1dodecj;//過濾右邊的0whilei<jdobegininca;//將第i堆牌移到第i1堆中去a:=0;//第i堆牌移走后變?yōu)?incstep;//移牌步數(shù)計數(shù)inci;//對下一堆牌進(jìn)行循環(huán)操作whilea=0andi<jdoinci;//過濾移牌過程中產(chǎn)生的0end;writelnstep;點(diǎn)評：基本題（較易）本題有3點(diǎn)比較關(guān)鍵：一是善于將每堆牌數(shù)減去平均數(shù)，簡化了問題；二是要過濾掉0（不是所有的0，如-2，3，0，-1中的0是不能過濾的）；三是負(fù)數(shù)張牌也可以移動，這是辯證法（關(guān)鍵中的關(guān)鍵）?！纠?】刪數(shù)問題（NOI94）輸入一個高精度的正整數(shù)N，去掉其中任意S個數(shù)字后剩下的數(shù)字按原左右次序組成一個新的正整數(shù)。編程對給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。輸出應(yīng)新的正整數(shù)。（N不超過240位）輸入數(shù)據(jù)均不需判錯?！据斎搿縩s【輸出】最后剩下的最小數(shù)。【樣例輸入】1754384【樣例輸出】13【算法分析】由于正整數(shù)n的有效數(shù)位為240位，所以很自然地采用字符串類型存貯n。那么如何決定哪s位被刪除呢？是不是最大的s個數(shù)字呢？顯然不是，大家很容易舉出一些反例。為了盡可能逼近目標(biāo)，我們選取的貪心策略為：每一步總是選擇一個使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個數(shù)字；否則刪除第一個遞減區(qū)間的首字符，這樣刪一位便形成了一個新數(shù)字串。然后回到串首，按上述規(guī)則再刪下一個數(shù)字。重復(fù)以上過程s次為止，剩下的數(shù)字串便是問題的解了。例如：n=175438s=4刪數(shù)的過程如下：n=175438//刪掉715438//刪掉51438//刪掉4138//刪掉813//解為13這樣，刪數(shù)問題就與如何尋找遞減區(qū)間首字符這樣一個簡單的問題對應(yīng)起來。不過還要注意一個細(xì)節(jié)性的問題，就是可能會出現(xiàn)字符串串首有若干0的情況，甚至整個字符串都是0的情況。按以上貪心策略編制的程序框架如下輸入n，s；whiles>0dobegini：=1；//從串首開始找whilei<lengthnandndoi:=i1；deleten，i，1；//刪除字符串n的第i個字符s:=s-1；end；whilelengthn>1andn=‘0’dodeleten，1，1；輸出n；//刪去串首可能產(chǎn)生的無用零【例6】攔截導(dǎo)彈問題（NOIP1999）某國為了防御敵國的導(dǎo)彈襲擊，開發(fā)出一種導(dǎo)彈攔截系統(tǒng)，但是這種攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲，由于該系統(tǒng)還在試用階段。所以一套系統(tǒng)有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度不大于30000的正整數(shù)）。計算要攔截所有導(dǎo)彈最小需要配備多少套這種導(dǎo)彈攔截系統(tǒng)?！据斎敫袷健縩顆依次飛來的高度（1≤n≤1000）【輸出格式】要攔截所有導(dǎo)彈最小配備的系統(tǒng)數(shù)。【輸入樣例】38920715530029917015865【輸出樣例】2【輸入輸出樣例】輸入：導(dǎo)彈高度：79685輸出