基礎(chǔ)算法綜合

基礎(chǔ)算法綜合長沙市第一中學(xué)曹利國第一部分枚舉策略枚舉枚舉：是對(duì)一個(gè)問題找出所有的可行狀態(tài)，然后從中找出最優(yōu)的狀態(tài)。枚舉的不足：當(dāng)枚舉的狀態(tài)很多時(shí)，所用的時(shí)間會(huì)非常大，效率比較低。枚舉方法的優(yōu)化枚舉算法的時(shí)間復(fù)雜度：狀態(tài)總數(shù)*單個(gè)狀態(tài)的耗時(shí)主要優(yōu)化方法：⑴減少狀態(tài)總數(shù)⑵降低單個(gè)狀態(tài)的考察代價(jià)優(yōu)化過程從以下幾個(gè)方面考慮：⑴枚舉對(duì)象的選?、泼杜e方法的確定

⑶采用局部枚舉或引進(jìn)其他算法例題1：偵探推理（Noip試題）xx同學(xué)最近迷上了偵探漫畫《柯南》并沉醉于推理游戲之中，于是他召集了一群同學(xué)玩推理游戲。游戲的內(nèi)容是這樣的，xx的同學(xué)們先商量好由其中的一個(gè)人充當(dāng)罪犯（在xx不知情的情況下），xx的任務(wù)就是找出這個(gè)罪犯。接著，xx逐個(gè)詢問每一個(gè)同學(xué)，被詢問者可能會(huì)說：

例題1：偵探推理證詞中出現(xiàn)的其他話，都不列入邏輯推理的內(nèi)容。xx所知道的是，他的同學(xué)中有N個(gè)人始終說假話，其余的人始終說真?，F(xiàn)在，xx需要你幫助他從他同學(xué)的話中推斷出誰是真正的兇手，請(qǐng)記住，兇手只有一個(gè)！數(shù)據(jù)范圍：M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100），M為總?cè)藬?shù)，P為總共說了多少話例題1：偵探推理初步分析：開始接觸的這題目，不知道怎么下手，但是我們從題目中可以知道：兇手只有一個(gè),并且說話的總?cè)藬?shù)很少深入分析：我們不妨換一個(gè)思路，枚舉兇手是哪個(gè)和今天是星期幾；然后對(duì)每一句話進(jìn)行判斷，看這個(gè)人是不是始終說真話和假話；統(tǒng)計(jì)始終說真話和假話的人有多少；最后看是不是符合題目的要求。例題1：偵探推理偽代碼：For(longi=1;i<=m;i++)//枚舉兇手是誰For(longday=1;day<=7;day++)//枚舉今天是星期幾{For(longk=1;k<=p;k++)check(k)//判斷第K句話是真話還是假話For(longk=1;k<=m;i++)count(i)//統(tǒng)計(jì)第k個(gè)人是否始終說真話或假話。Getcheck()//看這個(gè)枚舉的結(jié)果是不是符合題目要求

}例題2B_station在離著名的國家Berland不遠(yuǎn)的地方，有一個(gè)水下工作站。這個(gè)工作站有N層。已知：是第i層裝有Wi的水，最多可以容納Li的水，恐怖分子炸毀第i層的代價(jià)是Pi。第i層一旦被炸毀，該層所有的水都將傾瀉到第i+1層。如果某一層的水量超過了它的容量(即Li)，那么該層就將自動(dòng)被毀壞，所有的水也會(huì)傾瀉到下一層。Pivland的恐怖分子想要用最少的錢毀掉第N層，現(xiàn)在他雇傭你來計(jì)算，需要炸毀哪些層。

輸入:第一行有一個(gè)自然數(shù)N(1<=n<=15000)。接下來的N行，每行3個(gè)整數(shù)Wi,Li,Pi(0<=Wi,Li,Pi<=15000)。輸出:輸出需要炸毀的層的編號(hào)。樣例Input樣例output311000100012010002210100

分析令Si=W1+W2+…+Wi（特別的S0=0）。不妨設(shè)恐怖分子炸毀的第高層是第p層（第一層是最高層，第N層是最底層）。因?yàn)榭植婪肿拥哪繕?biāo)是毀滅第N層，所以水必須從第p層一直瀉下去。如果存在一個(gè)i，滿足Wp+Wp+1+…+Wi-1+Wi<=Li，也就是說前面幾層的水全部泄下來也無法把第i層自動(dòng)沖毀，那么就必須要使用炸藥把它炸開了。所以恐怖分子需要炸毀的層的集合就是Bomb[p]={p}∪{i|i>pSi-Sp-1<=Li}令Qi=Si-Li，那么：Bomb[p]={p}∪{i|i>pQi<=Sp-1}我們枚舉p，然后看哪些層需要炸毀。這樣就得到了一個(gè)O(n2)的算法。

優(yōu)化注意到Sp是隨著p的增加而遞增的，觀察兩個(gè)集合：Bomb[p]={p}∪{i|i>pQi<=Sp-1}Bomb[p-1]={p-1}∪{i|i>p-1Qi<=Sp-2}因?yàn)镾p-2<=Sp-1，所以{i|i>p-1Qi<=Sp-2}包含于Bomb[p]，也就是說，Bomb[p-1]是在Bomb[p]的基礎(chǔ)上，通過以下操作得到的：刪除所有的i∈Bomb[p]，Qi>Sp-2。添加p-1。針對(duì)這兩種操作，我們可以使用大根堆(Heap)。從大到小枚舉p，對(duì)于每一個(gè)p，執(zhí)行：Step1.如果堆的根i滿足Qi>Sp-2，那么刪除根；否則轉(zhuǎn)Step3。Step2.轉(zhuǎn)Step1。Step3.添加p-1。每層至多進(jìn)堆一次、出堆一次，所以總的時(shí)間復(fù)雜度是O(nlogn)。對(duì)于n<=15000的范圍完全能夠勝任了。

枚舉對(duì)象的確定例題3：二進(jìn)制數(shù)的分類若將一個(gè)正整數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)后，0的個(gè)數(shù)多于1的個(gè)數(shù)的這類數(shù)稱為A類數(shù)，否則稱為B類數(shù)。例如：（13）10=（1101）2，13為B類數(shù)；（10）10=（1010）210為B類數(shù)；（24）10=（11000）224為A類數(shù)；程序要求：求出1～1000之中（包括1與1000），全部A、B兩類數(shù)的個(gè)數(shù)?！痉治觥看祟}是一道統(tǒng)計(jì)類題目。解決統(tǒng)計(jì)問題的一個(gè)常用方法是枚舉法：逐一枚舉所有情況，同時(shí)進(jìn)行統(tǒng)計(jì)，枚舉結(jié)束時(shí)，統(tǒng)計(jì)也完成，得到結(jié)果。具體對(duì)本題而言，采用枚舉法的正確性與可行性是顯然的，而本題的數(shù)據(jù)規(guī)模又僅為1～1000，所以采用逐一枚舉方法進(jìn)行統(tǒng)計(jì)的時(shí)間復(fù)雜度是完全可以接受的。枚舉算法的應(yīng)用例題4：01統(tǒng)計(jì)將問題的數(shù)據(jù)規(guī)模擴(kuò)充到求1到m（m<=1030）中A類數(shù)的個(gè)數(shù)。分析本題是統(tǒng)計(jì)問題，但使用1~m的循環(huán)來逐個(gè)判斷顯然耗時(shí)過多，對(duì)于m較大時(shí)無法在規(guī)定的時(shí)間內(nèi)出解。所以我們希望通過分類統(tǒng)計(jì)的方法，進(jìn)一步抽象問題，得到可行的算法:根據(jù)二進(jìn)制數(shù)的前綴來分類是合理的，既沒有重復(fù)也沒有遺漏。當(dāng)m的二進(jìn)制數(shù)長度為n時(shí)，最多有2n種類型，即2（log2m+1）

種，比窮舉m種類型有了很大進(jìn)步。設(shè)m=(112)10=(1110000)2，求1~m的A類數(shù)個(gè)數(shù)。可以將112個(gè)數(shù)分為以下幾類：數(shù)字形式為(111xxxx)2

這一類數(shù)只有1個(gè)，即(1110000)2，是A類數(shù)數(shù)字形式為(110xxxx)2

設(shè)4個(gè)填數(shù)位置填0的個(gè)數(shù)為S0，填1的個(gè)數(shù)為S1，則S0+S1+3=7,若為A類數(shù)，則S0+1>S1+2,可以取S0=4S1=0；S0=3S1=1.這一類數(shù)中的A類數(shù)個(gè)數(shù)：(44)+(34)數(shù)字形式為(10xxxxx)2設(shè)5個(gè)填數(shù)位置填0的個(gè)數(shù)為S0，填1的個(gè)數(shù)為S1，則S0+S1+2=7若為A類數(shù)，則S0+1>S1+1,可以取S0=5S1=0；S0=4S1=1；S0=3S1=2.這一類數(shù)中的A類數(shù)個(gè)數(shù)：(55)+(45)+(35)數(shù)字形式為(0xxxxxx)2這一類數(shù)字的分析與前幾類略有不同，因?yàn)榍皫最惗M(jìn)制數(shù)的位數(shù)都是7，而這一類數(shù)還需對(duì)位數(shù)進(jìn)行討論：（1）1位數(shù)，即(1)2，不是A類數(shù)（2）2位數(shù)，即(1x)2，(10)2和(11)2都不是A類數(shù)（3）3位數(shù)，即(1xx)2，A類數(shù)個(gè)數(shù)為(22)=1（4）4位數(shù)，即(1xxx)2，A類數(shù)個(gè)數(shù)為(33)=1（5）5位數(shù)，即(1xxxx)2，A類數(shù)個(gè)數(shù)為(44)+(34)=5（6）6位數(shù)，即(1xxxxx)2，A類數(shù)個(gè)數(shù)為(55)+(45)=6最后的答案是1+5+16+(1+1+5+6)=35局部枚舉例題5：求第一、第二、第三最短路問題局部枚舉例題6：新年好重慶城里有n個(gè)車站，m條雙向公路連接其中的某些車站。每兩個(gè)車站最多用一條公路直接相連，從任何一個(gè)車站出發(fā)都可以經(jīng)過一條或多條公路到達(dá)其他車站，但不同的路徑需要花費(fèi)的時(shí)間可能不同。在一條路上花費(fèi)的時(shí)間等于路徑上所有公路需要的時(shí)間之和。佳佳的家在車站1，他有五個(gè)親戚，分別住在車站a,b,c,d,e。過年了，他需要從自己的家出發(fā)，拜訪每個(gè)親戚（順序任意），給他們送去節(jié)日的祝福。怎樣走，才需要最少的時(shí)間？分析這一題中的邊數(shù)遠(yuǎn)小于n2，所以復(fù)雜度也只有nlogn+m算法框架是：（1）用5次最短路，計(jì)算出6個(gè)點(diǎn)兩兩之間的距離（2）枚舉5個(gè)結(jié)點(diǎn)的全排列，找到一個(gè)使得總路程長度最短的方案。第二部分遞推策略遞推的概念與基本思想

給定一個(gè)數(shù)的序列H0,H1,…,Hn,…若存在整數(shù)n0，使當(dāng)n>n0時(shí),可以用等號(hào)(或大于號(hào)、小于號(hào))將Hn與其前面的某些項(xiàng)Hi(0<i<n)聯(lián)系起來，這樣的式子就叫做遞推關(guān)系。解決遞推問題的一般步驟

建立遞推關(guān)系式確定邊界條件遞推求解

遞推的形式順推法和倒推法遞推的應(yīng)用分類

一般遞推問題組合計(jì)數(shù)類問題一類博弈問題的求解動(dòng)態(tài)規(guī)劃問題的遞推關(guān)系遞推的應(yīng)用（一般遞推問題）例題1:Hanoi塔問題

.

Hanoi塔由n個(gè)大小不同的圓盤和三根木柱a,b,c組成。開始時(shí)，這n個(gè)圓盤由大到小依次套在a柱上，如圖1所示。要求把a(bǔ)柱上n個(gè)圓盤按下述規(guī)則移到c柱上：(1)一次只能移一個(gè)圓盤；(2)圓盤只能在三個(gè)柱上存放；(3)在移動(dòng)過程中，不允許大盤壓小盤。問將這n個(gè)盤子從a柱移動(dòng)到c柱上，總計(jì)需要移動(dòng)多少個(gè)盤次？abc

圖1遞推的應(yīng)用（一般遞推問題）例題1:Hanoi塔問題

.

Hanoi塔由n個(gè)大小不同的圓盤和三根木柱a,b,c組成。開始時(shí)，這n個(gè)圓盤由大到小依次套在a柱上，如圖1所示。要求把a(bǔ)柱上n個(gè)圓盤按下述規(guī)則移到c柱上：(1)一次只能移一個(gè)圓盤；(2)圓盤只能在三個(gè)柱上存放；(3)在移動(dòng)過程中，不允許大盤壓小盤。問將這n個(gè)盤子從a柱移動(dòng)到c柱上，總計(jì)需要移動(dòng)多少個(gè)盤次？abc

圖1分析設(shè)hn為n個(gè)盤子從a柱移到c柱所需移動(dòng)的盤次。顯然，當(dāng)n=1時(shí)，只需把a(bǔ)柱上的盤子直接移動(dòng)到c柱就可以了，故h1=1。當(dāng)n=2時(shí)，先將a柱上面的小盤子移動(dòng)到b柱上去；然后將大盤子從a柱移到c柱；最后，將b柱上的小盤子移到c柱上，共記3個(gè)盤次，故h2=3。以此類推，當(dāng)a柱上有n(n>=2)個(gè)盤子時(shí)，總是先借助c柱把上面的n-1個(gè)盤子移動(dòng)到b柱上，然后把a(bǔ)柱最下面的盤子移動(dòng)到c柱上；再借助a柱把b柱上的n-1個(gè)盤子移動(dòng)到c柱上；總共移動(dòng)hn-1+1+hn-1個(gè)盤次。∴hn=2hn-1+1

邊界條件：h1=1遞推的應(yīng)用（一般遞推問題）例2：實(shí)數(shù)數(shù)列一個(gè)實(shí)數(shù)數(shù)列共有n項(xiàng)，已知ai=(ai-1-ai+1)/2+d，(1<i<n)(n<60)鍵盤輸入n，d，a1，an，m，輸出am。輸入數(shù)據(jù)均不需判錯(cuò)。分析根據(jù)公式ai=(ai-1-ai+1)/2+d變形得，ai+1=ai-1-2ai+2d，因此該數(shù)列的通項(xiàng)公式為：ai=ai-2-2ai-1+2d，已知a1，如果能求出a2，這樣就可以根據(jù)公式遞推求出am∵ai=ai-2-2ai-1+2d……(1) =ai-2-2（ai-3-2ai-2+2d）+2d=-2ai-3+5（ai-4-2ai-3+2d）-2d=5ai-4-12ai-3+8d……

一直迭代下去，直到最后，可以建立ai和a1與a2的關(guān)系式。分析設(shè)ai=Pia2+Qid+Ria1，我們來尋求Pi,Qi,Ri的變化規(guī)律?！遖i=ai-2-2ai-1+2d∴ai=Pi-2a2+Qi-2d+Ri-2a1-2（Pi-1a2+Qi-1d+Ri-1a1）+2d=(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1∴Pi=Pi-2-2Pi-1 ……② Qi=Qi-2-2Qi-1+2 ……③ Ri=Ri-2-2Ri-1

……④顯然，P1=0Q1=0R1=1（i=1） P2=1Q2=0R2=0 （i=2）將初值P1Q1R1和P2Q2R2代入②③④可以求出PnQnRn∵an=Pna2+Qnd+Rna1∴a2=(an-Qnd+Rna1)/Pn然后根據(jù)公式①遞推求出am，問題解決。改進(jìn)算法但仔細(xì)分析，上述算法有一個(gè)明顯的缺陷：在求由于在求a2要運(yùn)用除法，因此會(huì)存在實(shí)數(shù)誤差，這個(gè)誤差在以后遞推求am的過程又不斷的擴(kuò)大。在實(shí)際中，當(dāng)m超過30時(shí)，求出的am就明顯偏離正確值。顯然，這種算法雖簡單但不可靠。為了減少誤差，我們可設(shè)計(jì)如下算法：∵ai=Pia2+Qid+Ria1 =Pi-1a3+Qi-1d+Ri-1a2 =Pi-2a4+Qi-2d+Ri-2a3……=Pi-2+kak+Qi-2+kd+Ri-2+kak-1∴an=Pn-k+2ak+Qn-k+2d+Rn-k+2ak-1ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2……⑤根據(jù)公式⑤，可以順推a2、a3、…、aM。雖然仍然存在實(shí)數(shù)誤差，但由于Pn-k+2遞減，因此最后得出的am要比直接利用公式①精確得多。遞推的應(yīng)用（一般遞推問題）例題：貯油點(diǎn)。一輛重型卡車欲穿過1000公里的沙漠，卡車耗汽油為1升/公里，卡車總載油能力為500公升。顯然卡車裝一次油是過不了沙漠的。因此司機(jī)必須設(shè)法在沿途建立若干個(gè)貯油點(diǎn)，使卡車能順利穿過沙漠。試問司機(jī)如怎樣建立這些貯油點(diǎn)？每一貯油點(diǎn)應(yīng)存儲(chǔ)多少汽油，才能使卡車以消耗最少汽油的代價(jià)通過沙漠？編程計(jì)算及打印建立的貯油點(diǎn)序號(hào)，各貯油點(diǎn)距沙漠邊沿出發(fā)的距離以及存油量。格式如下：No.Distance(k.m.)Oil(litre)1××××2××××…

……

……分析設(shè)Way[i]——第i個(gè)貯油點(diǎn)到終點(diǎn)（i=0）的距離；oil[i]——第i個(gè)貯油點(diǎn)的貯油量；我們可以用倒推法來解決這個(gè)問題。從終點(diǎn)向始點(diǎn)倒推，逐一求出每個(gè)貯油點(diǎn)的位置及存油量。從貯油點(diǎn)i向貯油點(diǎn)i+1倒推的方法是：卡車在貯油點(diǎn)i和貯油點(diǎn)i+1間往返若干次?？ㄜ嚸看畏祷豬+1點(diǎn)時(shí)應(yīng)該正好耗盡500公升汽油，而每次從i+1點(diǎn)出發(fā)時(shí)又必須裝足500公升汽油。兩點(diǎn)之間的距離必須滿足在耗油最少的條件下，使i點(diǎn)貯足i*500公升汽油的要求（0≦i≦n-1）。倒推第一步第一個(gè)貯油點(diǎn)i=1應(yīng)距終點(diǎn)i=0處500km，且在該點(diǎn)貯藏500公升汽油，這樣才能保證卡車能由i=1處到達(dá)終點(diǎn)i=0處，這就是說Way[1]=500；oil[1]=500；倒推第二步 為了在i=1處貯藏500公升汽油，卡車至少從I=2處開兩趟滿載油的車至i=1處，所以i=2處至少貯有2*500公升汽油，即oil[2]=500*2=1000；另外，再加上從i=1返回至i=2處的一趟空載，合計(jì)往返3次。三次往返路程的耗油量按最省要求只能為500公升，即d1,2=500/3km，Way[2]=Way[1]+d1,2=Way[1]+500/3倒推第三步為了在I=2處貯藏1000公升汽油，卡車至少從I=3處開三趟滿載油的車至I=2處。所以I=3處至少貯有3*500公升汽油，即oil[3]=500*3=1500。加上I=2至I=3處的二趟返程空車，合計(jì)5次。路途耗油亦應(yīng)500公升，即d23=500/5，Way[3]=Way[2]+d2,3=Way[2]+500/5；倒推第k步……為了在i=k處貯藏k*500公升汽油，卡車至少從i=k+1處開k趟滿載車至i=k處，即oil[k+1]=(k+1)*500=oil[k]+500，加上從i=k返回i=k+1的k-1趟返程空間，合計(jì)2k-1次。這2k-1次總耗油量按最省要求為500公升，即dk,k+1=500/(2k-1)Way[k+1]=Way[k]+dk,k+1=Way[k]+500/(2k-1)；i=n的情形i=n至始點(diǎn)的距離為1000-Way[n],oil[n]=500*n。為了在i=n處取得n*500公升汽油，卡車至少從始點(diǎn)開n+1次滿載車至I=n，加上從I=n返回始點(diǎn)的n趟返程空車，合計(jì)2n+1次，2n+1趟的總耗油量應(yīng)正好為（1000-Way[n]）*(2n+1)，即始點(diǎn)藏油為oil[n]+(1000-Way[n])*(2n+1)。掃雷(Mine)有一個(gè)長度為n的格子，其中某些格子中有一個(gè)地雷。給定一個(gè)長度為n的非負(fù)整數(shù)序列，序列中的第i個(gè)元素表示第i-1格，第i格，第i+1格（如果存在）中雷的個(gè)數(shù)。求出地雷的分布方案數(shù)。輸入文件：

第一行為N，第二行有N個(gè)數(shù)，依次為第二列的格子中的數(shù)。（1<=N<=10000）輸出文件：

一個(gè)數(shù)，即第一列中雷的擺放方案數(shù)。SampleInput21

SampleOutput2分析按照我們平時(shí)玩掃雷的心得，我們往往可以通過某個(gè)位置周圍的數(shù)字以及已經(jīng)得到的雷的分布推出其是不是雷。該題同樣可以這樣做，如果已知第i-1格和i-2格是否有雷(i>2)，則可以通過序列中第i-1個(gè)數(shù)推出第i格是否有雷。而第2格的狀態(tài)則只需要由第一格的雷和序列第一個(gè)數(shù)推出。

設(shè)Ai表示序列中第i個(gè)元素，F(xiàn)i表示第I格的雷數(shù),我們可以遞推求解。

方程：Fi=Ai-1-Fi-1(i=2)

Fi=Ai-1-Fi-2-Fi-1(i>=3)但是F1的值還是未知的，由于每一格就是有雷和無雷兩種狀態(tài)，顯然我們可以枚舉第一格雷的狀態(tài)，即F1的值為0或者1，這樣就可以遞推得到所有的F值。如果Fi（1<=i<=n）的值不為0，1的話顯然是不符合要求的，而如果Fn+Fn-1<>An,顯然也是不符合要求的。如果不出現(xiàn)這種情況就得到一種可行的分布方案，所以最后答案不外乎0，1，2三種。

例題3：走直線棋問題。有如下所示的一個(gè)編號(hào)為１到ｎ的方格：

現(xiàn)由計(jì)算機(jī)和人進(jìn)行人機(jī)對(duì)奕，從１到ｎ，每次可以走ｋ個(gè)方格，其中ｋ為集ｓ={a1,a2,a3,....am}中的元素(m<=4)，規(guī)定誰最先走到第n格為勝，試設(shè)計(jì)一個(gè)人機(jī)對(duì)奕方案，摸擬整個(gè)游戲過程的情況并力求計(jì)算機(jī)盡量不敗。遞推的應(yīng)用（博弈問題）12345……N-1N題設(shè)條件：若誰先走到第N格誰將獲勝，例如，假設(shè)S={1,2}，從第N格往前倒推，則走到第N-1格或第N-2格的一方必?cái)?，而走到第N-3格者必定獲勝，因此在N，S確定后，棋格中每個(gè)方格的勝、負(fù)或和態(tài)（雙方都不能到達(dá)第N格）都是可以事先確定的。將目標(biāo)格置為必勝態(tài)，由后往前倒推每一格的勝負(fù)狀態(tài)，規(guī)定在自己所處的當(dāng)前格后，若對(duì)方無論走到哪兒都必定失敗，則當(dāng)前格為勝態(tài)，若走后有任一格為勝格，則當(dāng)前格為輸態(tài)，否則為和態(tài)。分析設(shè)1表示必勝態(tài)，-1表示必?cái)B(tài)，0表示和態(tài)或表示無法到達(dá)的棋格。例如，設(shè)N＝10，S＝{1,2}，則可確定其每個(gè)棋格的狀態(tài)如下所示：而N＝10，S＝{2,3}時(shí)，其每格的狀態(tài)將會(huì)如下所示：

有了棋格的狀態(tài)圖后，程序應(yīng)能判斷讓誰先走，計(jì)算機(jī)選擇必勝策略或雙方和（雙方均不能到達(dá)目標(biāo)格）的策略下棋，這樣就能保證計(jì)算機(jī)盡可能不敗。分析1-1-11-1-11-1-110-1-1010-1-101在一個(gè)n×m的方格中，m為奇數(shù)，放置有n×m個(gè)數(shù)，如圖,方格中間的下方有一人，此人可按照五個(gè)方向前進(jìn)但不能越出方格,見右下圖。人每走過一個(gè)方格必須取此方格中的數(shù)。要求找到一條從底到頂?shù)穆窂?，使其?shù)相加之和為最大。輸出和的最大值。1643126034-56700260-1-236853400-27-17407-560-1341242人

遞推的應(yīng)用（動(dòng)態(tài)規(guī)劃中的遞推例4：方格取數(shù)分析我們用坐標(biāo)(x,y)唯一確定一個(gè)點(diǎn)，其中(m,n)表示圖的右上角，而人的出發(fā)點(diǎn)是，受人前進(jìn)方向的限制，能直接到達(dá)點(diǎn)(x,y)的點(diǎn)只有(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)。到點(diǎn)(x,y)的路徑中和最大的路徑必然要從(m/2,0)到(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)的幾條路徑中產(chǎn)生，既然要求最優(yōu)方案，當(dāng)然要挑一條和最大的路徑，關(guān)系式如下：Fx,y=Max{Fx+2,y-1,Fx+1,y-1,Fx,y-1,Fx-1,y-1,Fx-2,y-1}+Numx,y，其中Numx,y表示(x,y)點(diǎn)上的數(shù)字。邊界條件為：動(dòng)態(tài)規(guī)劃與遞推的關(guān)系上題實(shí)質(zhì)上是采用動(dòng)態(tài)規(guī)劃來求解,那么與遞推動(dòng)態(tài)規(guī)劃之間到底是什么關(guān)系呢？我們不妨畫個(gè)圖(如下圖)。而通常人們理解的遞推關(guān)系就是一般遞推關(guān)系，故認(rèn)為動(dòng)態(tài)規(guī)劃與遞推關(guān)系是兩個(gè)各自獨(dú)立的個(gè)體。動(dòng)態(tài)規(guī)劃一般遞推關(guān)系遞推關(guān)系動(dòng)態(tài)規(guī)劃與遞推的關(guān)系1、一般遞推邊界條件很明顯,動(dòng)態(tài)規(guī)劃邊界條件比較隱蔽,容易被忽視2、一般遞推數(shù)學(xué)性較強(qiáng),動(dòng)態(tài)規(guī)劃數(shù)學(xué)性相對(duì)較弱

3、一般遞推一般不劃分階段,動(dòng)態(tài)規(guī)劃一般有較為明顯的階段第三部分貪心方法貪心方法的基本思想

貪心是一種解題策略，也是一種解題思想使用貪心方法需要注意局部最優(yōu)與全局最優(yōu)的關(guān)系，選擇當(dāng)前狀態(tài)的局部最優(yōu)并不一定能推導(dǎo)出問題的全局最優(yōu)利用貪心策略解題，需要解決兩個(gè)問題：該題是否適合于用貪心策略求解如何選擇貪心標(biāo)準(zhǔn)，以得到問題的最優(yōu)解

適用于貪心策略求解的問題的特點(diǎn)

適用于貪心策略求解的問題必須具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，但并不是所有具有最優(yōu)子結(jié)構(gòu)的問題都可以用貪心策略求解。因?yàn)樨澬耐敲つ康模枰褂酶硇缘姆椒ā獎(jiǎng)討B(tài)規(guī)劃（例如“0-1背包問題”與“部分背包問題”）

貪心方法的應(yīng)用例題1：節(jié)點(diǎn)網(wǎng)絡(luò)?，F(xiàn)有一個(gè)N！個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)的編號(hào)都是編號(hào)（A1A2A3…AN）序列的一個(gè)置換。對(duì)于任意兩個(gè)節(jié)點(diǎn)S和T，如果T的編號(hào)是由S編號(hào)的首位與除首位外的編號(hào)中任一位交換所得，則S和T之間有一條邊，求從給定節(jié)點(diǎn)S走到節(jié)點(diǎn)（A1A2A3…AN）所需經(jīng)過的最少邊數(shù)。其中，n≤100。貪心方法的應(yīng)用例如n=3的情況：(A1A2A3)(A1A3A2)(A2A3A1)(A2A1A3)(A3A1A2)(A3A2A1)貪心方法的應(yīng)用【分析】從題意表面上看，本題是一個(gè)求最短路徑的問題，但題設(shè)中的N≤100，也就是說圖中最多有100！個(gè)節(jié)點(diǎn)，采用二維關(guān)系的圖結(jié)構(gòu)根本無法存貯這眾多的狀態(tài)。通過問題的本質(zhì)分析，可以將問題轉(zhuǎn)化為一個(gè)序列的最優(yōu)轉(zhuǎn)化問題。貪心方法的應(yīng)用采用貪心策略：每次讓一個(gè)節(jié)點(diǎn)歸位或?yàn)橄乱徊焦ぷ髯鰷?zhǔn)備。其具體步驟為：若序列中第一個(gè)點(diǎn)為Ax(x≠1)，則將第一個(gè)點(diǎn)和第x個(gè)點(diǎn)交換。這便完成了讓一個(gè)點(diǎn)歸位的工作；若第一個(gè)是A1，則任找一個(gè)編號(hào)與位置不相符的點(diǎn)，并與之交換。這樣下一步便可讓交換到1號(hào)位置的點(diǎn)歸位。貪心方法的應(yīng)用(A3A4A1A2)(A1A4A3A2)第一個(gè)點(diǎn)A1已歸位，但第二個(gè)點(diǎn)為A4≠A2，將第2個(gè)點(diǎn)A4與A1交換第一個(gè)點(diǎn)為A3≠A1，將第3個(gè)點(diǎn)A1與A3交換(A4A1A3A2)第一個(gè)點(diǎn)為A4≠A1，將第4個(gè)點(diǎn)A2與A4交換(A2A1A3A4)第一個(gè)點(diǎn)為A2≠A1，將第2個(gè)點(diǎn)A1與A2交換(A1A2A3A4)已經(jīng)符合要求了一共經(jīng)過4步完成。下面看一個(gè)n=4，初始序列為(A3A4A1A2)的推演過程：例題2排序問題排序是計(jì)算機(jī)科學(xué)中一個(gè)常見任務(wù)。有一種特殊的排序，最多只有3個(gè)關(guān)鍵字。例如，試圖對(duì)這次競爭的獎(jiǎng)牌榜排序時(shí)，就只有3個(gè)關(guān)鍵字，所有的金牌獲得者在最前面，隨后是獲銀牌者，最后是銅牌獲得者。

本題中用1,2,3分別表示3個(gè)關(guān)鍵字，需將它們按升序排列。排序是通過一系列對(duì)換操作實(shí)現(xiàn)的。一次操作可以交換兩個(gè)數(shù)的位置。子任務(wù)A

請(qǐng)寫一個(gè)程序，對(duì)于一個(gè)給定的只含有關(guān)鍵字的序列，計(jì)算最少需要幾次對(duì)換操作就可以將其按升序排列。子任務(wù)B

輸出一種最少次數(shù)的對(duì)換方案。分析如果要我們自己來手算的話，勢必會(huì)先找到一對(duì)數(shù)，使其交換位置后正好都回到應(yīng)該在的位置，例如數(shù)串111232333，我們發(fā)現(xiàn)第5位上的3與第6位上的2正好反過來了。把它們交換就可以得到排序后的數(shù)串。又因?yàn)檫@樣的一次交換使兩個(gè)數(shù)回到正確的位置，這說明這次交換已經(jīng)發(fā)揮了它的最大功效，一定不是多余的，雖然是要求最少的交換次數(shù)也絕不能少了這樣的交換。到這里我們發(fā)現(xiàn)這道題可以用貪心法來做。不斷地尋找這樣的一對(duì)數(shù)，直至找不到為止。但是注意，還有一種更加普遍的情況我們沒有考慮，也就是雖然存在錯(cuò)位了的數(shù)，但是找不到互換位置可以符合以上要求的兩個(gè)數(shù)。例如：113221332中，第3位上的3，第6位上的1，第9位上的2，都是錯(cuò)位的，但不管取他們?nèi)齻€(gè)中的哪兩個(gè)交換，通通都不能使兩個(gè)數(shù)都?xì)w原位。這個(gè)時(shí)候，我們只好放棄一個(gè)，只保證一個(gè)數(shù)可以歸原位，于是交換1與2，數(shù)串變成113222331，這時(shí)再交換3與1，就用兩次交換對(duì)該數(shù)列排完了序。問題變形給定N個(gè)不同的正整數(shù)，每次只能交換兩個(gè)相鄰的數(shù)，如何一住校的交換次數(shù)使得其變成升序？貪心方法的應(yīng)用（貪心標(biāo)準(zhǔn)）例題：d-規(guī)則問題。對(duì)任意給定的m(m∈N+)和n(n∈N+)，滿足m<n，構(gòu)造一初始集合：P={x|m≤x≤n,x∈N+}(m,n≤100)現(xiàn)定義一種d規(guī)則如下：若存在a∈P，且存在K∈N+,K>1，使得Ka∈P，則修改P為：P=P-{y|y=sa,s∈N+}

，并稱該d規(guī)則具有分值a?，F(xiàn)要求編制一個(gè)程序，對(duì)輸入的m,n值，構(gòu)造相應(yīng)的初始集合P，對(duì)P每應(yīng)用一次d規(guī)則就累加其相應(yīng)的分值，求能得到最大累加分值的d規(guī)則序列，輸出每次使用d規(guī)則時(shí)的分值和集合p的變化過程。貪心方法的應(yīng)用【分析】初看這一問題，很容易想到用貪心策略來求解，即選擇集合中最大的可以刪除的數(shù)開始刪起，直到不能再刪除為止，而且通過一些簡單的例子來驗(yàn)證，這一貪心標(biāo)準(zhǔn)似乎也是正確的，例如，當(dāng)m=3，n=10時(shí)，集合P＝{3,…,10}，運(yùn)用上述“貪心標(biāo)準(zhǔn)”可以得到這一問題的正確的最優(yōu)解d=5＋4＋3＝12，即其d-規(guī)則過程如下：1.a=5P={3,4,6,7,8,9} d=52.a=4P={3,6,7,9} d=5+4=93.a=3p={7} d=5+4+3=12貪心方法的應(yīng)用但是，如果再仔細(xì)地分析一個(gè)例子，當(dāng)m=3，n＝18時(shí)，如果還是使用上述“貪心標(biāo)準(zhǔn)”，則得到問題的d-規(guī)則總分為d=35，其d-規(guī)則序列為（9,8,7,6,5），而實(shí)際上可以得到最大d-規(guī)則總分為d＝38，其對(duì)應(yīng)的d-規(guī)則序列為（9,8,7,6,3,5）。為什么會(huì)出現(xiàn)這樣的反例呢？這是因?yàn)椋瑔栴}中要使得d-規(guī)則總分d值越大，不光是要求每一個(gè)d分值越大越好，也要求取得的d分值越多越好。因此，本題不能采用純粹的貪心策略求解。貪心方法的應(yīng)用【改進(jìn)】將原算法基礎(chǔ)上進(jìn)行改進(jìn)。下面給出新的算法：建立集合P={m..n}從ndiv2到m每數(shù)構(gòu)造一個(gè)集合c[i]，包含該數(shù)在P中的所有倍數(shù)（不包括i本身）從ndiv2起找到第一個(gè)元素個(gè)數(shù)最少但又不為空的集合c[i]在d分值中加上i把i及c[i]集合從P集中刪除，更新所有構(gòu)造集合的元素檢查所有構(gòu)造集合，若還有非空集合，則繼續(xù)3步驟，否則打印、結(jié)束貪心方法的應(yīng)用下面看m=3,n=18時(shí)的推演過程：初始P={3..18}找到i=9,c[i]={18},P={3..8,10..17}找到i=8,c[i]={16},P={3..7,10..15,17}找到i=7,c[i]={14},P={3..6,10..13,15,17}找到i=6,c[i]={12},P={3..5,10,11,13,15,17}找到i=3,c[i]={15},P={4,5,10,11,13,17}找到i=5,c[i]={10},P={4,11,13,17}到此所有構(gòu)造集合全部為空，d=9+8+7+6+3+5=38例題分析：田忌賽馬問題

中國古代的歷史故事“田忌賽馬”是為大家所熟知的。話說齊王和田忌又要賽馬了，他們各派出N匹馬，每場比賽，輸?shù)囊环綄⒁o贏的一方200兩黃金，如果是平局的話，雙方都不必拿出錢?，F(xiàn)在每匹馬的速度值是固定而且已知的，而齊王出馬也不管田忌的出馬順序。請(qǐng)問田忌該如何安排自己的馬去對(duì)抗齊王的馬，才能贏取最多的錢？正整數(shù)n(n<=2000)，表示雙方馬的數(shù)量。分析不妨用貪心思想來分析一下問題。因?yàn)樘锛烧莆沼斜荣惖摹爸鲃?dòng)權(quán)”，他總是根據(jù)齊王所出的馬來分配自己的馬，所以這里不妨認(rèn)為齊王的出馬順序是按馬的速度從高到低出的。由這樣的假設(shè)，我們歸納出如下貪心策略：1、如果田忌剩下的馬中最強(qiáng)的馬都贏不了齊王剩下的最強(qiáng)的馬，那么應(yīng)該用最差的一匹馬去輸給齊王最強(qiáng)的馬。2、如果田忌剩下的馬中最強(qiáng)的馬可以贏齊王剩下的最強(qiáng)的馬，那就用這匹馬去贏齊王剩下的最強(qiáng)的馬。

3、如果田忌剩下的馬中最強(qiáng)的馬和齊王剩下的最強(qiáng)的馬打平的話，可以選擇打平或者用最差的馬輸?shù)舯荣?。光是打平的話，如果齊王馬的速度分別是123，田忌馬的速度也是123，每次選擇打平的話，田忌一分錢也得不到，而如果選擇先用速度為1的馬輸給速度為3的馬的話，可以贏得200兩黃金。光是輸?shù)舻脑?，如果齊王馬的速度分別是13，田忌馬的速度分別是23，田忌一勝一負(fù)，仍然一分錢也拿不到。而如果先用速度為3的馬去打平的話，可以贏得200兩黃金。

通過上述的三種貪心策略，我們可以發(fā)現(xiàn)，如果齊王的馬是按速度排序之后，從高到低被派出的話，田忌一定是將他馬按速度排序之后，從兩頭取馬去和齊王的馬比賽。有了這個(gè)信息之后，動(dòng)態(tài)規(guī)劃的模型也就出來了！Dp求解設(shè)f[i,j]表示齊王按從強(qiáng)到弱的順序出馬和田忌進(jìn)行了i場比賽之后，從“頭”取了j匹較強(qiáng)的馬，從“尾”取了i-j匹較弱的馬，所能夠得到的最大盈利。狀態(tài)轉(zhuǎn)移方程如下：F[I,j]=max{f[i-1,j]+g[n-(i-j)+1,i],f[i-1,j-1]+g[j,i]}其中g(shù)[i,j]表示田忌的馬和齊王的馬分別按照由強(qiáng)到弱的順序排序之后，田忌的第i匹馬和齊王的第j匹馬賽跑所能取得的盈利，勝為200，輸為－200，平為0。貪心方法的應(yīng)用（貪心標(biāo)準(zhǔn)證明）例題：射擊競賽射擊的目標(biāo)是一個(gè)由RC(2≤R≤C≤1000)個(gè)小方格組成的矩形網(wǎng)格。每一列恰有2個(gè)白色的小方格和R-2個(gè)黑色的小方格。行從頂至底編號(hào)為1~R，列從左至右編號(hào)為1~C。射擊者可射擊C次。在連續(xù)的C次射擊中，若每列恰好有一個(gè)白色的方格被射中，且不存在無白色方格被射中的行，這樣的射擊才是正確的。如果存在正確的射擊方法，則要求找到它。貪心方法的應(yīng)用射擊的選擇有2C種，符合要求的卻很少。要解決問題，還需從正確的射擊方法的特征入手。貪心方法的應(yīng)用【方法一】網(wǎng)絡(luò)流算法我們將表示列的點(diǎn)編號(hào)為1到C，表示行的點(diǎn)編號(hào)為C+1到C+R，如果一個(gè)白色方格處在第i行第j列，那么從點(diǎn)j向點(diǎn)C+i連一條弧，弧的容量為1。再增設(shè)一個(gè)源點(diǎn)S，從點(diǎn)S往點(diǎn)1到C間各連一條弧，弧的容量為1，又設(shè)一個(gè)匯點(diǎn)T，從點(diǎn)C+1到點(diǎn)C+R向匯點(diǎn)T連一條弧，弧的容量為1，那么從源點(diǎn)S到匯點(diǎn)T求最大流，求出的最大流量即為最多可以射擊到的行數(shù)。各條流的路線則描述了具體的射擊方案。可以看出，如果用網(wǎng)絡(luò)流求出的最大流量比R小，則問題無解，否則我們可以先根據(jù)網(wǎng)絡(luò)流的結(jié)果求出該二分圖的具體匹配方案。貪心方法的應(yīng)用紅色的連線流量為1藍(lán)色的連線流量為0選擇的射擊格即為：(1,3),(2,1),(3,2),(4,4)S21432143T列:行:源:匯:貪心方法的應(yīng)用網(wǎng)絡(luò)流算法經(jīng)過優(yōu)化，時(shí)間復(fù)雜度可以達(dá)到O(C(n+4C+4R))

上述網(wǎng)絡(luò)流算法雖然可以通過全部數(shù)據(jù)，但編程復(fù)雜度很高，而且極易出錯(cuò)，一不小心就會(huì)因?yàn)橐粋€(gè)小錯(cuò)誤影響整個(gè)程序。貪心方法的應(yīng)用【方法二】貪心方法統(tǒng)計(jì)所有行包含的白格數(shù)從還沒有射擊格的行中選出一個(gè)白格數(shù)最少的檢查所選的行若所選行的白格數(shù)為0，則輸出無解；否則從所選行的白格中任選一個(gè)作為射擊格，并將與該格同列的另一個(gè)白格所處行的白格數(shù)減1返回到第2步，直到所有的行都有射擊格。若還有列沒有選射擊格，則在該列任選一白格作為射擊格即可貪心方法的應(yīng)用上面的貪心方法非常高效：時(shí)間復(fù)雜度為O(RC)，如果在程序中使用堆優(yōu)化，時(shí)間復(fù)雜度將降為O(Rlog2C)?？臻g復(fù)雜度是線性的，而且非常容易實(shí)現(xiàn)。現(xiàn)在關(guān)鍵的問題就是——如何證明它的正確性？貪心方法的應(yīng)用【證明】用h[i]表示第i行的白格數(shù)。如果最開始的時(shí)候：min{h[i]}=0:第i行已經(jīng)沒有辦法找到可作為射擊格的白格，那么問題只能無解。min{h[i]}=1:那么第i行的這一個(gè)白格必須要作為射擊格，否則將因第i行沒有射擊格而造成問題無解。min{h[i]}≥2:那么在這一行任選一個(gè)白格，頂多只會(huì)造成剩余行中有一行h值為1，再處理那一行，最多也只會(huì)再造成剩余行中有一行h值為1，如此往復(fù)，將保持h值為1的行數(shù)不超過1行，最后最壞的情況也是造成最后一行的h值為1，繼續(xù)下去所有行就都已選取了射擊格了。因此，如果原問題有解，該貪心方法一定能找到一種正確的方案。由此可以證明，此貪心方法是正確的。例題分析買彩票(tickt.exe)電視里面正放著“抽百萬大獎(jiǎng)，贏幸福生活”的宣傳廣告，bird看后也想去試試手氣，當(dāng)然，作為經(jīng)濟(jì)學(xué)院的高材生，他可不屑只是單純的去碰運(yùn)氣。經(jīng)過他的一番分析，發(fā)現(xiàn)，商家在彩票里面做了手腳，使得每個(gè)抽獎(jiǎng)點(diǎn)的中獎(jiǎng)概率不是完全一樣的，而且隨著時(shí)間的變化而變化，不過這種變化是有規(guī)律的。

對(duì)于第I個(gè)抽獎(jiǎng)點(diǎn)，最開始的中獎(jiǎng)概率是百萬分之Pi，以后每抽一張彩票后都要重新排隊(duì)，花費(fèi)的時(shí)間是T分鐘，每抽一次減少的概率為Di。由于可憐的bird還有一大堆的作業(yè)沒做，他只能抽出H個(gè)小時(shí)去買彩票。由于抽獎(jiǎng)地點(diǎn)都在一路公共汽車的線路上，所以怕麻煩的bird決定按車站順序抽獎(jiǎng)。當(dāng)然，bird可以從任意一站開始抽獎(jiǎng)，對(duì)于經(jīng)過的抽獎(jiǎng)點(diǎn)可以買彩票，也可以不買。假設(shè)從第I個(gè)抽獎(jiǎng)點(diǎn)到第I+1個(gè)抽獎(jiǎng)點(diǎn)需要做Ci分鐘的汽車。Bird希望能在有限的H個(gè)小時(shí)內(nèi)獲得最好的運(yùn)氣——即抽獎(jiǎng)的概率和最大。輸入：

第一行為一個(gè)整數(shù)n，表示抽獎(jiǎng)點(diǎn)的個(gè)數(shù)，1<=n<=200

第二行是兩個(gè)整數(shù)H和T，1<=H<=10，1<=T<=60。

接下來的n行，每行3個(gè)整數(shù)，分別是Pi，Di，Ci（Cn=0）。1<=Pi<=10000，Di<=Pi，1<=Ci<=600。輸出：

一個(gè)整數(shù)，抽獎(jiǎng)概率和的最大值。樣例數(shù)據(jù)input.txtoutput.txt2500120200100103002000樣例說明：

首先，bird從1號(hào)開始抽獎(jiǎng)，花費(fèi)20分鐘，得到概率200，然后坐車到2號(hào)，花費(fèi)10分鐘，再花20分鐘得到概率300，概率和是500，花費(fèi)50分鐘。此題最初可能想到用搜索，不過如果仔細(xì)分析題目會(huì)發(fā)現(xiàn)其實(shí)用貪心就可以解了。雖然中獎(jiǎng)的概率會(huì)不斷變化，但概率只和在該抽獎(jiǎng)地點(diǎn)的抽獎(jiǎng)次數(shù)有關(guān)，和抽獎(jiǎng)的總次數(shù)以及時(shí)間無關(guān)。所以，我們可以枚舉起始S和終點(diǎn)T的抽獎(jiǎng)地點(diǎn)，則在路上花費(fèi)的時(shí)間可以求出，那么在這個(gè)范圍內(nèi)的抽獎(jiǎng)，可以看作bird能瞬間轉(zhuǎn)移，那么我們只需將此范圍內(nèi)的抽獎(jiǎng)概率排序，取前若干個(gè)，使得花費(fèi)的時(shí)間不超過時(shí)限。很容易證明，這種方法是最優(yōu)的。此題的貪心關(guān)鍵是要先確定一個(gè)范圍，然后針對(duì)具體的范圍貪心。貪心法的隱秘性還是比較強(qiáng)的。例題分析（駱駝商隊(duì)）有N個(gè)城市，編號(hào)為1……N。在一些城市之間有路可通，有路就有商隊(duì)。但是在不同的城市之間經(jīng)商所得的收益不同，在下面的這個(gè)N=4的例子中，在城市1和城市2之間進(jìn)行一次交易可以獲得40枚金幣，在城市2和3之間交易一次可以獲得50枚金幣，規(guī)定在任意兩個(gè)城市之間，這樣的交易只能進(jìn)行一次。給出這個(gè)大陸的地圖和每兩個(gè)城市之間的貿(mào)易值（如果這兩個(gè)城市之間有路可通的話），你需要指揮你的N支商隊(duì)進(jìn)行一次經(jīng)商，使得這N支商隊(duì)在這次經(jīng)商中獲得的總收益最大。注意：你的每支商隊(duì)只能進(jìn)行一次交易，即它們只能從它們所在的城市到達(dá)一個(gè)相鄰的城市。當(dāng)然，它們也可以不進(jìn)行任何交易。分析本題轉(zhuǎn)化成模型就是：在一個(gè)無向圖中，對(duì)于每個(gè)點(diǎn)，取一條和它相關(guān)聯(lián)的邊（如果這樣的邊存在的話），使得取出來的所有邊的權(quán)和最大。首先，如果這個(gè)圖是不連通的，那么它的各個(gè)連通分量之間是沒有任何聯(lián)系的。對(duì)這些連通分量中的問題可以分別獨(dú)立地解決，合并起來就是整個(gè)問題的解。所以我們?cè)谙旅娴挠懻撝屑俣▓D是連通的。直觀地考慮，如果圖中存在度為1的點(diǎn)，那么就把這一點(diǎn)上的唯一的一條邊分配給這個(gè)點(diǎn)（將某條邊“分配”給某個(gè)點(diǎn)的含義是：將這條邊作為和這一點(diǎn)相關(guān)聯(lián)的邊取出來，同時(shí)這一點(diǎn)就失效了，因?yàn)楹退嚓P(guān)聯(lián)的其他邊都不能再取了）。如果不存在這樣的點(diǎn)，那么此時(shí)有兩種情況：一種是邊數(shù)等于點(diǎn)數(shù)，那么這個(gè)圖就是一個(gè)環(huán)，這時(shí)可以取出圖中所有的邊；一種是邊數(shù)大于點(diǎn)數(shù)，那么就可以把這個(gè)圖中權(quán)最小的一條邊直接刪去，因?yàn)檫@條邊“顯然”不會(huì)被取到的。貪心算法（用于連通圖）：1、如果圖中只有一個(gè)點(diǎn)，直接結(jié)束算法。2、如果圖中存在度為1的點(diǎn)，執(zhí)行3；否則轉(zhuǎn)4。3、任意找一個(gè)度為1的點(diǎn)v，將v上的唯一一條邊分配給它。轉(zhuǎn)2。4、如果圖中的邊數(shù)等于點(diǎn)數(shù)，執(zhí)行5；否則轉(zhuǎn)6。5、設(shè)圖中的點(diǎn)數(shù)（也就是邊數(shù)）為n。任取一條邊e1，將它分配給它的兩個(gè)端點(diǎn)中的任意一個(gè)v1；然后將v1上的另一條邊e2分配給e2的另一個(gè)端點(diǎn)v2；將v2上的另一條邊e3分配給e3的另一個(gè)端點(diǎn)v3；……如此重復(fù)直到將en分配給vn，即圖中所有的邊都已分配，結(jié)束算法。6、將圖中權(quán)最小的邊不分配而直接刪去。如果此時(shí)圖仍然連通，則轉(zhuǎn)2；否則對(duì)這個(gè)圖的兩個(gè)連通分量分別執(zhí)行本算法貪心方法的推廣貪心與其它算法結(jié)合搜索的最優(yōu)化剪枝（

生日蛋糕）優(yōu)化動(dòng)態(tài)規(guī)劃（Peter的快餐店）貪心方法與解題策略最優(yōu)方法不一定是最好方法想不到最優(yōu)解法就用較優(yōu)解法貪心與其它算法結(jié)合例題：Peter的快餐店（貪心與動(dòng)態(tài)規(guī)劃）Peter最近在R市新開了一家快餐店。該快餐店準(zhǔn)備推出一種套餐，每套由A個(gè)漢堡、B個(gè)薯?xiàng)l和C個(gè)飲料組成。為了提高產(chǎn)量，Peter引進(jìn)了N條生產(chǎn)線。所有生產(chǎn)線都可以生產(chǎn)漢堡、薯?xiàng)l和飲料，由于每條生產(chǎn)線一天能工作的時(shí)間是有限的、不同的，而漢堡、薯?xiàng)l和飲料的單位生產(chǎn)時(shí)間又不同，Peter需要知道，怎樣安排才能是一天中生產(chǎn)的套餐量最大。假設(shè)一天中漢堡、薯?xiàng)l和飲料的產(chǎn)量均不超過100個(gè)，且生產(chǎn)線總數(shù)小于等于10。貪心與其它算法結(jié)合【分析】用p1、p2、p3分別表示漢堡、薯?xiàng)l和飲料的單位生產(chǎn)時(shí)間，t[i]表示第i條生產(chǎn)線每天的生產(chǎn)時(shí)間，p[i,j,k]表示用前i條生產(chǎn)線生產(chǎn)j個(gè)漢堡、k個(gè)薯?xiàng)l的情況下，最多能生產(chǎn)的飲料數(shù)，r[i,j,k]表示用第i條生產(chǎn)線生產(chǎn)j個(gè)漢堡、k個(gè)薯?xiàng)l的情況下，最多能生產(chǎn)的飲料數(shù)，則p[i,j,k]=max{p[i-1,j1,k1]+r[i,j-j1,k-k1]}((j-j1)p1+(k-k1)p2<t[i])通過對(duì)該算法的時(shí)間復(fù)雜度分析，最壞的情況下時(shí)間復(fù)雜度將達(dá)到109，是相當(dāng)費(fèi)時(shí)的。貪心與其它算法結(jié)合現(xiàn)在加入貪心方法，用貪心方法作預(yù)處理

：首先計(jì)算出一天生產(chǎn)套數(shù)的上限值：min{100divA,100divB,100divC}接著，用貪心方法計(jì)算出這N條生產(chǎn)線可以生產(chǎn)的套數(shù)，并與上限比較，大于或等于則輸出上限值并退出，否則再調(diào)用動(dòng)態(tài)規(guī)劃。因?yàn)樨澬姆椒ǖ拇鷥r(jià)很低，這里甚至可以使用多次貪心標(biāo)準(zhǔn)不同的貪心方法，取其最大值。在運(yùn)行動(dòng)態(tài)規(guī)劃的過程中，也可以每完成一階段工作便與上限值進(jìn)行比較，將貪心思想充分融入到動(dòng)態(tài)規(guī)劃過程中，這樣以來，便可望在動(dòng)態(tài)規(guī)劃完成前提前結(jié)束程序。乘車路線編號(hào)為1..N的N座城鎮(zhèn)用若干道路相連，每條道路上均有兩個(gè)參數(shù)：道路長度(length)和在該條道路上行駛的費(fèi)用（cost）。BOB準(zhǔn)備從城鎮(zhèn)1出發(fā)到達(dá)城鎮(zhèn)N，但他目前只有W的錢，為此，你需要幫助他尋找一條從城鎮(zhèn)1到城鎮(zhèn)N在他能支付的前提下的一條最短路線。分析我們可以在一開始的時(shí)候做一下預(yù)處理，用MinL[I]表示在不考慮費(fèi)用的情況下，從城鎮(zhèn)I到城鎮(zhèn)N的最短路長度。用MinW[I]表示，在不考慮路程的情況下從城鎮(zhèn)I到城鎮(zhèn)N所需的最少費(fèi)用（如有多種方案選擇路程短的）。這兩個(gè)數(shù)組的值都可以用Dijkstra算法求出來。時(shí)間復(fù)雜度為O(N*N)，比起后面的搜索算很小了。求出兩個(gè)數(shù)組的值后，我們可以看MinW[1]的值，如果它比W大，顯然該問題無解，否則將達(dá)到MinW[1]的路程長度作為搜索的下界。

在搜索的時(shí)候，設(shè)當(dāng)前在城鎮(zhèn)I，已經(jīng)走的路程長為L，用的費(fèi)用為W，如果L+MinL[I]>=已找到的最短路長度或是W+MinW[I]>最大可承擔(dān)費(fèi)用，再搜索下去顯然是沒有必要的，此時(shí)我們可以剪枝了。貪心方法小結(jié)貪心作為一種解題思路，雖然有時(shí)無法證明它的正確性，但在無法找到其他算法的時(shí)候，不失為一種好方法。并且，貪心與其他算法的結(jié)合，可以對(duì)其他算法起到優(yōu)化作用。第四部分分治策略分治思想分治(divide-and-conquer)就是“分而治之”的意思，其實(shí)質(zhì)就是將原問題分成n個(gè)規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題；然后遞歸地解這些子問題，最后合并其結(jié)果就得到原問題的解。其三個(gè)步驟如下；分解(Divide)：將原問題分成一系列子問題。解決(Conquer)：遞歸地解各子問題。若子問題足夠小，則可直接求解。合并(combine)；將子問題的結(jié)果合并成原問題的解。分治的應(yīng)用解決一類求方程的根的問題解決真假硬幣的稱量問題基于NLgN算法效率的排序和查找問題分治的應(yīng)用（求方程的根）例題1：一元三次方程求解有形如：ax3+bx2+cx+d=0這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)(a，b，c，d均為實(shí)數(shù))，并約定該方程存在三個(gè)不同實(shí)根(根的范圍在-100至100之間)，且根與根之差的絕對(duì)值>=1。要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根之間留有空格)，并精確到小數(shù)點(diǎn)后4位。提示：記方程f(x)=ax3+bx2+cx+d，若存在2個(gè)數(shù)x1和x2，且x1<x2，f(x1)*f(x2)<0，則在(x1，x2)之間一定有一個(gè)根。樣例輸入：1-5-420輸出：-2.002.005.00分析如果精確到小數(shù)點(diǎn)后兩位，可用簡單的枚舉法：將x從-100.00到100.00（步長0.01）逐一枚舉，得到20000個(gè)f(x)，取其值與0最接近的三個(gè)f(x)，對(duì)應(yīng)的x即為答案。而題目已改成精度為小數(shù)點(diǎn)后4位，枚舉算法時(shí)間復(fù)雜度將達(dá)不到要求。直接使用求根公式，極為復(fù)雜。加上本題的提示給我們以啟迪：采用二分法逐漸縮小根的范圍，從而得到根的某精度的數(shù)值。具體方法如下：分析A、當(dāng)已知區(qū)間(a,b)內(nèi)有一個(gè)根時(shí)，用二分法求根，若區(qū)間(a,b)內(nèi)有根，則必有f(a)·f(b)<0。重復(fù)執(zhí)行如下的過程：

(1)若a+0.0001>b或f((a+b)/2)=0，則可確定根為(a+b)/2并退出過程；

(2)若f(a)*f((a+b)/2)<0，則由題目給出的定理可知根在區(qū)間(a,(a+b)/2)中，故對(duì)區(qū)間重復(fù)該過程；

(3)若f(a)*f((a+b)/2)>0，則必然有f((a+b)/2)*f(b)<0，根在((a+b)/2,b)中，對(duì)此區(qū)間重復(fù)該過程。執(zhí)行完畢，就可以得到精確到0.0001的根。分析B、求方程的所有三個(gè)實(shí)根所有的根的范圍都在-100至100之間，且根與根之差的絕對(duì)值>=1。因此可知：在[-100,-99]、[-99,-98]、……、[99，100]、[100，100]這201個(gè)區(qū)間內(nèi)，每個(gè)區(qū)間內(nèi)至多只能有一個(gè)根。即：除區(qū)間[100，100]外，其余區(qū)間[a,a+1]，只有當(dāng)f(a)=0或f(a)·f(a+1)<0時(shí)，方程在此區(qū)間內(nèi)才有解。若f(a)=0，解即為a；若f(a)·f(a+1)<0，則可以利用A中所述的二分法迅速出找出解。如此可求出方程的所有的解。分治的應(yīng)用（求方程的根）例題2：輸入m，n，p，a，b，求方程f(x)＝mx+nx-px＝0在[a,b]內(nèi)的根。m，n，p，a，b均為整數(shù)，且a<b；m，n，p都大于等于1。如果有根，則輸出，精確到1E-11；如果無方程根，則輸出“NO”?！緲永?equation.in equation.out 23412 1.5071265916E+00

2.9103830457E-11分析由于f(x)單調(diào)遞增函數(shù)，對(duì)于一個(gè)單調(diào)遞增(或遞減)函數(shù)，判斷在[a,b]范圍內(nèi)是否有解，解是多少。常用的一種方法叫“迭代法”，也就是“二分法”。先判斷f(a)·f(b)≤0，如果滿足則說明在[a,b]范圍內(nèi)有解，否則無解。如果有解再判斷x＝(a+b)/2是不是解，如果是則輸出解,結(jié)束程序，否則我們采用二分法，將范圍縮小到[a,x)或(x,b]，究竟在哪一半?yún)^(qū)間里有解，則要看是f(a)·f(x)<0還是f(x)·f(b)<0。

對(duì)于yx，我們需要用換底公式把它換成exp(xln(y))

分治的應(yīng)用(分段處理)例題3：取余運(yùn)算（mod.exe）

輸入b，p，k的值，編程計(jì)算bpmodk的值。其中的b，p，k*k為長整型數(shù)?！据斎胼敵鰳永縨od.in2109mod.out2^10mod9=7分析

1、用高精度計(jì)算比較煩

2、轉(zhuǎn)而用其他方法求解

（1）取模運(yùn)算的一個(gè)規(guī)律：a*bmodk=(amodk)*(bmodk)modk

（2）運(yùn)用規(guī)律可以把樣例數(shù)據(jù)分解：b19=b2*9+1=b9b9b，其中的指數(shù)9可以繼續(xù)分解為2×4＋1，4再分解程2×2＋0，2＝1×2＋0，1＝0×1＋1。反過來，我們可以從0出發(fā)，通過乘以2再加上1或0推得1，2，4，9，19，然后依次以這些數(shù)為指數(shù)的自然數(shù)除以k的余數(shù)。分析（3）不難看出，前面乘以2后要加上的1或0就是該數(shù)對(duì)應(yīng)二進(jìn)制數(shù)各位上的數(shù)字1或0。如，19＝（10011）2。求解的過程也就是將二進(jìn)制數(shù)還原為十進(jìn)制數(shù)的過程。（4）綜上所述，該題可采用分治得思想進(jìn)行遞推求解。找出偽幣給你一個(gè)裝有16枚硬幣的袋子。16枚硬幣中有一個(gè)是偽造的，并且那個(gè)偽造的硬幣比真的硬幣要輕一些。你的任務(wù)是找出這枚偽造的硬幣。為了幫助你完成這一任務(wù)，將提供一臺(tái)可用來比較兩組硬幣重量的儀器，比如天平。利用這臺(tái)儀器，可以知道兩組硬幣的重量是否相同。分治的應(yīng)用(稱量問題)方法1任意取1枚硬幣，與其他硬幣進(jìn)行比較，若發(fā)現(xiàn)輕者，這那枚為偽幣。最多可能有15次比較。方法2將硬幣分為8組，每組2個(gè)，每組比較一次，若發(fā)現(xiàn)輕的，則為偽幣。最多可能有8次比較。方法3分析