【精選】貪心算法

1、貪心算法近年來的信息學(xué)競(jìng)賽中，經(jīng)常需要求一個(gè)問題的可行解和最優(yōu)解，這就是所謂的最優(yōu)化 問題。貪心法是求解這類問題的一種常用算法。在眾多的算法中，貪心法可以算的上是最接 近人們口常思維的一種算法，他在各級(jí)各類信息學(xué)競(jìng)賽、尤其在一些數(shù)據(jù)規(guī)模很大的問題求 解中發(fā)揮著越來越重要的作用。一、什么是貪心法貪心法是從問題的某一個(gè)初始狀態(tài)出發(fā)，通過逐步構(gòu)造最優(yōu)解的方法向給定的目標(biāo)前 進(jìn)，并期望通過這種方法產(chǎn)生出一個(gè)全局最優(yōu)解的方法。做出貪心決策的依據(jù)稱為貪心準(zhǔn)則 （策略），但要注意決策一旦做出，就不可再更改。貪心與遞推不同的是，推進(jìn)的每一步不 是依據(jù)某一固定的遞推式，而是做一個(gè)當(dāng)時(shí)看似最佳的貪心選擇，不斷的將

2、問題實(shí)例歸納為 更小的相似子問題。所以，在有些最優(yōu)化問題中，采用貪心法求解不能保證一定得到最優(yōu)解, 這時(shí)我們可以選擇其他解決最優(yōu)化問題的算法，如動(dòng)態(tài)規(guī)劃等。歸納、分析、選擇貪心準(zhǔn)則 是正確解決貪心問題的關(guān)鍵。二、貪心法的特點(diǎn)及其優(yōu)缺點(diǎn)貪心法主要有以下兩個(gè)特點(diǎn)：貪心選擇性質(zhì):算法中每一步選擇都是當(dāng)前看似最佳的選擇，這種選擇依賴于已做出的 選擇，但不依賴于未作出的選擇。最優(yōu)子結(jié)構(gòu)性質(zhì):算法中每一次都取得了最優(yōu)解（即局部最優(yōu)解），要保證最后的結(jié)果 最優(yōu)，則必須滿足全局最優(yōu)解包含局部最優(yōu)解。利用貪心法解題的一般步驟是：1、產(chǎn)生問題的一個(gè)初始解；2、循環(huán)操作，當(dāng)可以向給定的目標(biāo)前進(jìn)時(shí)，就根據(jù)局部最優(yōu)策略

3、，向目標(biāo)前進(jìn)一步：3、得到問題的最優(yōu)解（或較優(yōu)解）。貪心法的優(yōu)缺點(diǎn)主要表現(xiàn)在：優(yōu)點(diǎn)：一個(gè)正確的貪心算法擁有很多優(yōu)點(diǎn)，比如思維更雜度低、代碼量小、運(yùn)行效率高、 空間更雜度低等，是信息學(xué)競(jìng)賽中的一個(gè)有力武器，受到廣大同學(xué)們的青睞。缺點(diǎn)：貪心法的缺點(diǎn)集中表現(xiàn)在他的“非完美性”。通常我們很難找到一個(gè)簡(jiǎn)單可行并 且保證正確的貪心思路，即使我們找到一個(gè)看上去很正確的貪心思路，也需要嚴(yán)格的正確性 證明。這往往給我們直接使用貪心算法帶來了巨大的困難。典型習(xí)題1、刪數(shù)問題鍵盤輸入一個(gè)高精度的正整數(shù)n （nv=240位），去掉其中任意s個(gè)數(shù)字后剩下的數(shù)字按 原左右次序?qū)⒔M成一個(gè)正整數(shù)編程對(duì)給定的n和s,尋找一種方

4、案，使得剩下的數(shù)字組成的 新數(shù)最小。輸入：ns輸出：最后剩下的最小數(shù)。樣例輸入：1785434樣例輸出：132、一種游戲，給出自然數(shù)11,然后給出2n個(gè)自然數(shù)，例如n=4,給出8個(gè)數(shù)：79 3 642 5 3。游戲雙方為AB 假設(shè)B方有最高智力，現(xiàn)只允許從給出數(shù)列的兩頭取 數(shù)；A可以先取，取完時(shí)誰取得的數(shù)字總和大，為取勝；如果雙方的和相等，仍屬A勝。 試問A能否找到必勝的取數(shù)算法？ （1996國(guó)際奧賽試題）【輸入】n2*n個(gè)自然數(shù)【輸出】共3n+2行，其中前3n行是游戲經(jīng)過。每3行分別為a方所取的數(shù)和b方所取的數(shù)，及 b方取數(shù)前應(yīng)給予的適當(dāng)提示，讓游戲者選擇取哪一頭的數(shù)（LR-左端或右端）。最

5、后2 行分別為a方所取的數(shù)和與b方取得的數(shù)和?！緲永斎搿?79364253【樣例輸出】L79L36L42L520193、noip2002均分紙牌有N堆紙牌，編號(hào)分別為1, 2,，No每堆上有若干張，但紙牌總數(shù)必為N的 倍數(shù)?？梢栽谌我欢焉先∪粲趶埣埮?，然后移動(dòng)。移牌規(guī)則為：在編號(hào)為1堆上取的紙牌，只能移到編號(hào)為2的堆上；在編號(hào)為 N的堆上取的紙牌.，只能移到編號(hào)為NT的堆上；其他堆上取的紙牌.，可以移 到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動(dòng)方法，用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多。例如N=4, 4堆紙牌數(shù)分別為：(1)9 (2)8 (3)17 (4)6移動(dòng)3次可達(dá)到目的：從取4張

6、牌放到(4) (9 8 13 10) -從(3)取3張牌放到(2) (9 11 10 10)- 從(2)取 1 張牌放到(1) (10 10 10 10) o輸入描述N (N 堆紙牌，1二 N二 100)Al A2An (N堆紙牌，每堆紙牌初始數(shù)，k=Ai =10000)輸出描述所有堆均達(dá)到相等時(shí)的最少移動(dòng)次數(shù)。樣例輸入49 8 17 6樣例輸出34、智力大沖浪源程序名riddle.? (pas, c, cpp)可執(zhí)行文件名nddle.exe輸入文件名nddle.iii輸出文件名riddle.out源程序名riddle.? (pas, c, cpp)可執(zhí)行文件名nddle.exe輸入文件名nd

7、dle.iii輸出文件名riddle.out【問題描述】小偉報(bào)名參加中央電視臺(tái)的智力大沖浪節(jié)目。本次挑戰(zhàn)賽吸引了眾多參賽者，主持人為 了表彰大家的勇氣，先獎(jiǎng)勵(lì)每個(gè)參賽者ni元。先不要太高興！因?yàn)檫@些錢還不一定都是你 的？！接下來主持人宣布了比賽規(guī)則:首先，比賽時(shí)間分為n個(gè)時(shí)段(nW500),它又給出了很多小游戲，每個(gè)小游戲都必須在 規(guī)定期限ti前完成(iWHWn)。如果一個(gè)游戲沒能在規(guī)定期限前完成，則要從獎(jiǎng)勵(lì)費(fèi)ni元中 扣去一部分錢wi, wi為自然數(shù)，不同的游戲扣去的錢是不一樣的。當(dāng)然，每個(gè)游戲本身都很簡(jiǎn)單，保證每個(gè)參賽者都能在一個(gè)時(shí)段內(nèi)完成，而且都必須從整時(shí)段開始。主持人只是想 考考每個(gè)參

8、賽者如何安排組織自己做游戲的順序。作為參賽者，小偉很想贏得冠軍，當(dāng)然更 想贏取最多的錢！注意：比賽絕對(duì)不會(huì)讓參賽者賠錢!【輸入】輸入文件riddle.in,共4行。第1行為m,表示一開始獎(jiǎng)勵(lì)給每位參賽者的錢: 第2行為n,表示有n個(gè)小游戲: 第3行有n個(gè)數(shù)，分別表示游戲1到n的規(guī)定完成期限;第4行有n個(gè)數(shù)，分別表示游戲1到n不能在規(guī)定期限前完成的扣款數(shù)?！据敵觥枯敵鑫募﨟ddle.out,僅1行。表示小偉能贏取最多的錢。【樣例】riddle.mriddle. out99501000099504243146 70 60 50 40 30 20 105、排隊(duì)接水源程序名water.? (pas,

9、c, cpp)可執(zhí)行文件名water.exe輸入文件名water, in輸出文件名water. out【問題描述】有n個(gè)人在一個(gè)水龍頭前排隊(duì)接水，假如每個(gè)人接水的時(shí)間為T1,請(qǐng)編程找出這n個(gè)人排隊(duì)的一種順序，使得a個(gè)人的平均等待時(shí)間最小。【輸入】輸入文件共兩行，第一行為n；第二行分別表示第1個(gè)人到第n個(gè)人每人的接水時(shí)間Tl, T2,源程序名water.? (pas, c, cpp)可執(zhí)行文件名water.exe輸入文件名water, in輸出文件名water. out【問題描述】有n個(gè)人在一個(gè)水龍頭前排隊(duì)接水，假如每個(gè)人接水的時(shí)間為T1,請(qǐng)編程找出這n個(gè)人排隊(duì)的一種順序，使得a個(gè)人的平均等待時(shí)

10、間最小?！据斎搿枯斎胛募矁尚?，第一行為n；第二行分別表示第1個(gè)人到第n個(gè)人每人的接水時(shí)間Tl, T2,，Tn,每個(gè)數(shù)據(jù)之間有1個(gè)空格。【輸出】輸出文件有兩行，第一行為一種排隊(duì)順序，即1到n的一種排列；第二行為這種排列方案卜的平均等待時(shí)間（輸出結(jié)果精確到小數(shù)點(diǎn)后兩位）。【樣例】water, mwater. out103278 1496 10 556 12 1 99 1000 234 33 55 99 812291.906、旅行家的預(yù)算（NOIP1999）問題描述:,個(gè)旅行家想駕駛汽車以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市（假設(shè)出發(fā)時(shí)油箱時(shí)空的）。給定兩個(gè)城市之間的距離D1、汽車油箱的容量C （以升

11、為單位）、每升汽油能行駛的距離D2、出發(fā)點(diǎn)每升汽油價(jià)格P和沿途加油站數(shù)N （N可以為零），油站1離出發(fā)點(diǎn)的距離Di、每升汽油價(jià)格Pi （i=l, 2,，N）o計(jì)算結(jié)果四舍五入至小數(shù)點(diǎn)后兩位。如果無法到達(dá)目的地，則輸出No Solution樣例:InputDl=275.6C=11.9D2=27.4P=2.8N=2油站號(hào)I離出發(fā)點(diǎn)的距離Di每升汽油價(jià)格Pi102.02.9220.02.2Output26.95 （該數(shù)據(jù)表示最小費(fèi)用）7、Dl=275.6C=11.9D2=27.4P=2.8N=2油站號(hào)I離出發(fā)點(diǎn)的距離Di每升汽油價(jià)格Pi102.02.9220.02.2Output26.95 （該數(shù)據(jù)

12、表示最小費(fèi)用）7、種樹源程序名可執(zhí)行文件名trees.? (pas, c, cpp)trees.exe輸入文件名trees.in輸出文件名trees, out【問題描述】一條街的一邊有幾座房子。因?yàn)榄h(huán)保原因居民想要在路邊種些樹。路邊的地區(qū)被分 割成塊，并被編號(hào)成1.N。每個(gè)部分為一個(gè)單位尺寸大小并最多可種一棵樹。每個(gè)居民想在 門前種些樹并指定了三個(gè)號(hào)碼B, E, To這三個(gè)數(shù)表示該居民想在B和E之間最少種T棵 樹。當(dāng)然，BWE,居民必須記住在指定區(qū)不能種多于區(qū)域地塊數(shù)的樹，所以TWE-B+1。居 民們想種樹的各自區(qū)域可以交叉。你的任務(wù)是求出能滿足所有要求的最少的樹的數(shù)量。寫一個(gè)程序完成以下工作：從trees.in讀入數(shù)據(jù)計(jì)算最少要種樹的數(shù)量和位置把結(jié)果寫