pascal貪心算法

《pascal貪心算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、貪心策略當(dāng)一個(gè)問題具有最優(yōu)子結(jié)構(gòu)時(shí)，一般我們會(huì)想到用動(dòng)態(tài)規(guī)劃法去解它，但是有些問題存在著更簡(jiǎn)單有效的方法，我們只要總是做出當(dāng)前看來最好的選擇就可以了。貪心算法所作的選擇可以依賴于以往所作過的選擇，但決不依賴于將來的選擇，也不依賴于子問題的解，這使得算法在編碼和執(zhí)行的過程中都有著一定的速度優(yōu)勢(shì)。如果一個(gè)問題可以同時(shí)用幾種方法解決，貪心算法應(yīng)該是最好的選擇之一。但是貪心算法并不是對(duì)所有的問題都能得到整體最優(yōu)解或最理想的近似解，與搜索法等通法比較，它的適用區(qū)域相對(duì)狹窄許多，因此正確的分析、歸納、判斷貪心法的應(yīng)用是十分重要的。同時(shí)我們也應(yīng)該知道貪心是一種方法，而不是算法，貪心法

2、的應(yīng)用需要結(jié)合其他算法。通常而言，貪心策略需要結(jié)合排序算法?！纠}】刪數(shù)問題【問題描述】鍵盤輸入一個(gè)高精度的正整數(shù)N，去掉其中任意S個(gè)數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。輸入數(shù)據(jù)均不需要判錯(cuò)。輸出應(yīng)包括所去掉的數(shù)字的位置和組成的新的正整數(shù)。（N不超過240位）【問題分析】對(duì)于這道試題，我們可以采用這樣一種解題方式：因?yàn)橐獎(jiǎng)h除S個(gè)數(shù)字，我們可以一個(gè)一個(gè)的刪，每一次刪除的目的都是使剩下的數(shù)盡量小。那么在每一次刪除時(shí)，我們應(yīng)該選擇那個(gè)數(shù)字？最大的數(shù)字還是最左的數(shù)字？例如5768，通過觀察可以知道刪除7

3、這個(gè)數(shù)字可以使剩余的數(shù)最小。通過思考可以得出結(jié)論，每一次刪除的數(shù)字應(yīng)該是這個(gè)數(shù)字序列中降序子序列最左邊的數(shù)字。具體可以這樣操作，按高位到低位的方向搜索遞減區(qū)間。若不存在遞減區(qū)間，則刪尾數(shù)符；否則刪遞減區(qū)間的首數(shù)符，這樣形成了一個(gè)新的數(shù)串。然后回到串首，重復(fù)上述規(guī)則，刪下一數(shù)符…以此類推，直至刪除S個(gè)數(shù)符為止。例如：N=“8796542”，S=4刪數(shù)過程如下：N=“8796542”{最左邊的遞減序列是87，刪除“8”}“796542”{最左邊的遞減序列是96542，刪除9}“76542”{最左邊的遞減序列是76542，刪除“7”}“6542”{最左邊的遞減序列是6542，

4、刪除“6”}“542”【程序代碼】programdelete;vari，j，k，s:integer;N:string;beginreadln(n);readln(s);whiles>0dobeginI:=1;while(i1and(n[1]=‘0’)dodelete(n，1，1)；writeln(n);end.【問題思考】由例題可知，貪心算法的實(shí)現(xiàn)需要思考兩個(gè)基本的問題：如何建立和方法的正確性。如何建立。怎樣從一個(gè)規(guī)

5、模較小的解推出規(guī)模較大的解呢？拿這個(gè)例題來說，從數(shù)串5768刪除2位數(shù)的模擬過程中推廣到240位的數(shù)串刪數(shù)過程。方法的正確性。確保貪心算法確實(shí)是有效是使用貪心算法的關(guān)鍵所在。確定貪心算法是有效的，那么解決該問題在時(shí)間復(fù)雜度還是在空間的使用方面與其他方法想比較顯得更為優(yōu)勢(shì)。以例題為例，刪數(shù)方法是首先按高位到低位的方向搜索遞減區(qū)間。若不存在遞減區(qū)間，則刪尾數(shù)符；否則刪遞減區(qū)間的首數(shù)符，這樣形成了一個(gè)新的數(shù)串。這樣獲得的新數(shù)肯定是最小的新數(shù)。對(duì)于上述例題，假如我們按照其他的刪數(shù)過程是正確的，刪除最左邊的數(shù)或者每次刪除最大的數(shù)。同樣以5768為例。刪除5得768，刪除8得576

6、，都不是最小的數(shù)值，假設(shè)不成立，證明這種方式是錯(cuò)誤的，按照原先設(shè)定的方法所得到的解是最優(yōu)解。由上例可以獲知，貪心的使用需要嚴(yán)格的證明，保證問題的嚴(yán)密性，貪心方法的使用還需呀結(jié)合其他算法的使用，例如：排序、模擬、搜素、枚舉等等，但是一旦證明了貪心方法使用的正確性，程序的運(yùn)行效率會(huì)大大提高。證明使用貪心方法的正確性依靠的是嚴(yán)密的數(shù)學(xué)頭腦和以往的經(jīng)驗(yàn)積累，假如不具備這些條件，使用該方法需要謹(jǐn)慎。二．經(jīng)典例題分析1.混合牛奶(milk.pasUSACO練習(xí)題)【問題描述】牛奶包裝是一個(gè)如此低利潤(rùn)的生意，以至于盡可能低地控制初級(jí)產(chǎn)品(牛奶)的價(jià)格變得十分重要。請(qǐng)幫助Merry的牛

7、奶制造公司(MerryMilkMakers')以盡可能最廉價(jià)的方式取得他們所需的牛奶。Merry的牛奶制造公司從一些農(nóng)民那購(gòu)買牛奶，每個(gè)農(nóng)民賣給牛奶制造公司的價(jià)格不一定相同。而且，如一只母牛一天只能生產(chǎn)一定量的牛奶，農(nóng)民每一天只有一定量的牛奶可以賣。每天，Merry的牛奶制造公司從每個(gè)農(nóng)民那購(gòu)買一定量的牛奶，少于或等于農(nóng)民所能提供的最大值?，F(xiàn)給出Merry牛奶制造公司的每日的牛奶需求，連同每個(gè)農(nóng)民的可提供的牛奶量和每加侖的價(jià)格，請(qǐng)計(jì)算Merry的牛奶制造公司所要付出錢的最小值。注意:每天農(nóng)民生產(chǎn)的牛奶的總數(shù)對(duì)Merry的牛奶制造公司來說是