一個(gè)程序往往要包含兩個(gè)方面的描述：一是對(duì)數(shù)據(jù)組織的描述，就是數(shù)據(jù)的類型和數(shù)據(jù)的組織形式（例如數(shù)組），稱作數(shù)據(jù)結(jié)構(gòu)；一是對(duì)程序操作流程的描述，就是程序的操作步驟，也就是所謂算法。正如著名的計(jì)算機(jī)科學(xué)家沃思（Nikiklaus Wirth）提出的公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序。

算法，廣義地講就是解決問(wèn)題的方法和過(guò)程?？梢允褂米匀徽Z(yǔ)言、偽代碼、流程圖等多種不同的方法來(lái)描述。如果把一個(gè)程序比喻成一個(gè)具有生命的人，那么數(shù)據(jù)結(jié)構(gòu)就是這個(gè)人的軀體，而算法則是這個(gè)人的靈魂。

枚舉

枚舉法，又稱窮舉法，或稱為暴力破解法，是一種針對(duì)于密碼的破譯方法，即將密碼進(jìn)行逐個(gè)推算直到找出真正的密碼為止。

基本思想：在可能的解空間中窮舉出每一種可能的解，并對(duì)每一個(gè)可能解進(jìn)行判斷，從中得到問(wèn)題的答案。雖然枚舉法本質(zhì)上屬于搜索策略，但是它與后面講的回溯法或?qū)挾葍?yōu)先搜索有所不同?？偟膩?lái)說(shuō)，枚舉就是通過(guò)列舉所有的可能性進(jìn)行一一判斷檢查。

適用條件：

1、可預(yù)先確定每個(gè)狀態(tài)的元素個(gè)數(shù)n。

2、可預(yù)先確定每個(gè)狀態(tài)元素a1,a2,…,an的值域。

注意事項(xiàng)：使用枚舉思想解決實(shí)際問(wèn)題，最關(guān)鍵的步驟是劃定問(wèn)題的解空間，并在該解空間中一一枚舉每一個(gè)可能的解。這里有兩點(diǎn)需要注意。一是解空間的劃定必須保證覆蓋問(wèn)題的全部解。如果解空間集合用H表示，問(wèn)題的解集用h表示，那么只有當(dāng)時(shí)，才能使用枚舉法求解。二是解空間集合及問(wèn)題的解集一定是離散的集合，也就是說(shuō)集合中的元素是可列的、有限的。

常見類型：枚舉排列、枚舉子集。

常見方法： 遞歸地枚舉，這種方法往往更為直觀；遞推（循環(huán)）地枚舉，這種方法往往寫起來(lái)更為簡(jiǎn)潔。

主要優(yōu)點(diǎn)：由于枚舉算法一般是現(xiàn)實(shí)問(wèn)題的“直譯”，且是建立在考察大量狀態(tài)、甚至是窮舉所有狀態(tài)的基礎(chǔ)之上的，因此比較直觀，易于理解，其算法的正確性也比較容易證明。

主要缺點(diǎn)：枚舉算法的效率取決于枚舉狀態(tài)的數(shù)量以及單個(gè)狀態(tài)枚舉的代價(jià)，因此效率比較低。在某些情況下，我們可以通過(guò)利用題目的特點(diǎn)去除相當(dāng)大的一部分情況的列舉，從而提高枚舉的效率。

算法優(yōu)化：

1、    提取有效信息;

2、    減少重復(fù)計(jì)算;

3、    將原問(wèn)題化為更小的問(wèn)題;

4、    根據(jù)問(wèn)題的性質(zhì)進(jìn)行截枝;

5、    引進(jìn)其他算法。

例：NOIP2016玩具謎題、NOIP2014生活大爆炸版石頭剪刀布等

遞推

遞推是一種用若干步可重復(fù)的簡(jiǎn)運(yùn)算（規(guī)律）來(lái)描述復(fù)雜問(wèn)題的方法。給定一個(gè)數(shù)的序列H0,H1,…,Hn,…若存在整數(shù)n0，使當(dāng)n>n0時(shí),可以用等號(hào)(或大于號(hào)、小于號(hào))將Hn與其前面的某些項(xiàng)Hi(0<><>

基本思想：遞推是按照一定的規(guī)律來(lái)計(jì)算序列中的每個(gè)項(xiàng)，通常是通過(guò)計(jì)算機(jī)前面的一些項(xiàng)來(lái)得出序列中的指定項(xiàng)的值。把一個(gè)復(fù)雜的龐大的計(jì)算過(guò)程轉(zhuǎn)化為簡(jiǎn)單過(guò)程的多次重復(fù)，該算法利用了計(jì)算機(jī)速度快和不知疲倦的機(jī)器特點(diǎn)。

主要步驟：建立遞推關(guān)系式；確定邊界條件；遞推求解。

應(yīng)用分類：一般遞推問(wèn)題；組合計(jì)數(shù)類問(wèn)題；一類博弈問(wèn)題的求解；動(dòng)態(tài)規(guī)劃問(wè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ī)劃一般有較為明顯的階段。

五種典型的遞推關(guān)系

1、Fibonacci數(shù)列

在所有的遞推關(guān)系中，F(xiàn)ibonacci數(shù)列應(yīng)該是最為大家所熟悉的。在最基礎(chǔ)的程序設(shè)計(jì)語(yǔ)言Logo語(yǔ)言中，就有很多這類的題目。而在較為復(fù)雜的Basic、Pascal、C語(yǔ)言中，F(xiàn)ibonacci數(shù)列類的題目因?yàn)榻夥ㄏ鄬?duì)容易一些，逐漸退出了競(jìng)賽的舞臺(tái)。可是這不等于說(shuō)Fibonacci數(shù)列沒有研究?jī)r(jià)值，恰恰相反，一些此類的題目還是能給我們一定的啟發(fā)的。

Fibonacci數(shù)列的代表問(wèn)題是由意大利著名數(shù)學(xué)家Fibonacci于1202年提出的“兔子繁殖問(wèn)題”(又稱“Fibonacci問(wèn)題”)。

問(wèn)題的提出：有雌雄一對(duì)兔子，假定過(guò)兩個(gè)月便可繁殖雌雄各一的一對(duì)小兔子。問(wèn)過(guò)n個(gè)月后共有多少對(duì)兔子？

解：設(shè)滿x個(gè)月共有兔子Fx對(duì)，其中當(dāng)月新生的兔子數(shù)目為Nx對(duì)。第x-1個(gè)月留下的兔子數(shù)目設(shè)為Fx-1對(duì)。則：

F_x=N_x+F_x-1

N_x=F_x-2  (即第x-2個(gè)月的所有兔子到第x個(gè)月都有繁殖能力了)

∴F_x=F_x-1+F_x-2  邊界條件：F0=0，F(xiàn)1=1

由上面的遞推關(guān)系可依次得到

F₂=F₁+F₀=1，F(xiàn)₃=F₂+F₁=2，F(xiàn)₄=F₃+F₂=3，F(xiàn)₅=F₄+F₃=5，……。

Fabonacci數(shù)列常出現(xiàn)在比較簡(jiǎn)單的組合計(jì)數(shù)問(wèn)題中，例如以前的競(jìng)賽中出現(xiàn)的“骨牌覆蓋”問(wèn)題。在優(yōu)選法中，F(xiàn)ibonacci數(shù)列的用處也得到了較好的體現(xiàn)。

2、Hanoi塔問(wèn)題

問(wèn)題的提出：Hanoi塔由n個(gè)大小不同的圓盤和三根木柱a,b,c組成。開始時(shí)，這n個(gè)圓盤由大到小依次套在a柱上，如圖所示。

要求把a(bǔ)柱上n個(gè)圓盤按下述規(guī)則移到c柱上：

1、一次只能移一個(gè)圓盤；

2、圓盤只能在三個(gè)柱上存放；

3、在移動(dòng)過(guò)程中，不允許大盤壓小盤。

問(wèn)將這n個(gè)盤子從a柱移動(dòng)到c柱上，總計(jì)需要移動(dòng)多少個(gè)盤次？

解：設(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(n2)個(gè)盤子時(shí)，總是先借助c柱把上面的n-1個(gè)盤子移動(dòng)到b柱上，然后把a(bǔ)柱最下面的盤子移動(dòng)到c柱上；再借助a柱把b柱上的n-1個(gè)盤子移動(dòng)到c柱上；總共移動(dòng)h_n-1+1+h_n-1個(gè)盤次。

∴h_n=2h_n-1+1    邊界條件：h₁=1

3、平面分割問(wèn)題

問(wèn)題的提出：設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，問(wèn)這些封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。

解：設(shè)a_n為n條封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。 由圖3-13可以看出：a₂-a₁=2；a₃-a₂=4；a₄-a₃=6。

從這些式子中可以看出a_n-a_n-1=2(n-1)。當(dāng)然，上面的式子只是我們通過(guò)觀察4幅圖后得出的結(jié)論，它的正確性尚不能保證。下面不妨讓我們來(lái)試著證明一下。當(dāng)平面上已有n-1條曲線將平面分割成a_n-1-個(gè)區(qū)域后，第n-1條曲線每與曲線相交一次，就會(huì)增加一個(gè)區(qū)域，因?yàn)槠矫嫔弦延辛薾-1條封閉曲線，且第n條曲線與已有的每一條閉曲線恰好相交于兩點(diǎn)，且不會(huì)與任兩條曲線交于同一點(diǎn)，故平面上一共增加2(n-1)個(gè)區(qū)域，加上已有的an-1個(gè)區(qū)域，一共有a_n-1+2(n-1)個(gè)區(qū)域。所以本題的遞推關(guān)系是a_n=a_n-1+2(n-1)，邊界條件是a₁=1。

4、Catalan數(shù)

Catalan數(shù)首先是由Euler在精確計(jì)算對(duì)凸n邊形的不同的對(duì)角三角形剖分的個(gè)數(shù)問(wèn)題時(shí)得到的，它經(jīng)常出現(xiàn)在組合計(jì)數(shù)問(wèn)題中。

問(wèn)題的提出：在一個(gè)凸n邊形中，通過(guò)不相交于n邊形內(nèi)部的對(duì)角線，把n邊形拆分成若干三角形，不同的拆分?jǐn)?shù)目用h_n表示，h_n即為Catalan數(shù)。例如五邊形有如下五種拆分方案，故h₅=5。求對(duì)于一個(gè)任意的凸n邊形相應(yīng)的h_n。

NOIP初賽復(fù)習(xí)（三）棧與卡特蘭數(shù)>>>

Catalan數(shù)是比較復(fù)雜的遞推關(guān)系，尤其在競(jìng)賽的時(shí)候，選手很難在較短的時(shí)間里建立起正確的遞推關(guān)系。當(dāng)然，Catalan數(shù)類的問(wèn)題也可以用搜索的方法來(lái)完成，但是，搜索的方法與利用遞推關(guān)系的方法比較起來(lái)，不僅效率低，編程復(fù)雜度也陡然提高。

5、第二類Stirling數(shù)

在五類典型的遞推關(guān)系中，第二類Stirling是最不為大家所熟悉的。也正因?yàn)槿绱?，我們有必要先解釋一下什么是第二類Strling數(shù)。

定義：n個(gè)有區(qū)別的球放到m個(gè)相同的盒子中，要求無(wú)一空盒，其不同的方案數(shù)用S(n,m)表示，稱為第二類Stirling數(shù)。

下面就讓我們根據(jù)定義來(lái)推導(dǎo)帶兩個(gè)參數(shù)的遞推關(guān)系——第二類Stirling數(shù)。

解：設(shè)有n個(gè)不同的球，分別用b1,b2,……bn表示。從中取出一個(gè)球bn，bn的放法有以下兩種：

1、bn獨(dú)自占一個(gè)盒子；那么剩下的球只能放在m-1個(gè)盒子中，方案數(shù)為S2(n-1,m-1)；

2、bn與別的球共占一個(gè)盒子；那么可以事先將b1,b2,……bn-1這n-1個(gè)球放入m個(gè)盒子中，然后再將球bn可以放入其中一個(gè)盒子中，方案數(shù)為mS2(n-1,m)。

綜合以上兩種情況，可以得出第二類Stirling數(shù)定理：

S2(n,m)=mS2(n-1,m)+S2(n-1,m-1)   (n>1,m1)

邊界條件可以由定義2推導(dǎo)出：

S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(k>n)。     

小結(jié)：通過(guò)上面對(duì)五種典型的遞推關(guān)系建立過(guò)程的探討，可知對(duì)待遞推類的題目，要具體情況具體分析，通過(guò)找到某狀態(tài)與其前面狀態(tài)的聯(lián)系，建立相應(yīng)的遞推關(guān)系。

遞歸

一個(gè)函數(shù)、過(guò)程、概念或數(shù)學(xué)結(jié)構(gòu)，如果在其定義或說(shuō)明內(nèi)部又直接或間接地出現(xiàn)有其本身的引用，則稱它們是遞歸的或者是遞歸定義的。在程序設(shè)計(jì)中，過(guò)程或函數(shù)直接或者間接調(diào)用自己，就被稱為遞歸調(diào)用。其中直接調(diào)用自己稱為直接遞歸，而將A調(diào)用B，B以調(diào)用A的遞歸叫做間接遞歸。

基本思想：

1、遞歸是借助于一個(gè)遞歸工作棧來(lái)實(shí)現(xiàn)。遞歸=遞推+回歸。

2、遞推：?jiǎn)栴}向一極推進(jìn), 這一過(guò)程叫做遞推。這一過(guò)程相當(dāng)于壓棧。

3、回歸：?jiǎn)栴}逐一解決，最后回到原問(wèn)題，這一過(guò)程叫做回歸。這一過(guò)程相當(dāng)于彈棧。

注意事項(xiàng)：

1、    遞歸就是在過(guò)程或函數(shù)里調(diào)用自身；

2、    在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。

主要優(yōu)點(diǎn)：采用遞歸方法編寫的問(wèn)題解決程序具有結(jié)構(gòu)清晰，可讀性強(qiáng)等優(yōu)點(diǎn)，且遞歸算法的設(shè)計(jì)比非遞歸算法的設(shè)計(jì)往往要容易一些，所以當(dāng)問(wèn)題本身是遞歸定義的，或者問(wèn)題所涉及到的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的，或者是問(wèn)題的解決方法是遞歸形式的時(shí)候，往往采用遞歸算法來(lái)解決。

主要缺點(diǎn)：執(zhí)行的效率很低，尤其在邊界條件設(shè)置不當(dāng)?shù)那闆r下，極有可能陷入死循環(huán)或者內(nèi)存溢出的窘境。遞歸實(shí)現(xiàn)的代價(jià)是巨大的棧空間的耗費(fèi)，那是因?yàn)檫^(guò)程每向前遞推一次，程序?qū)⒈緦拥膶?shí)在變量（值參和變參）、局部變量構(gòu)成一個(gè)“工作記錄”壓入工作棧的棧頂，只有退出該層遞歸時(shí)，才將這一工作記錄從棧頂彈出釋放部分空間。由此可以想到，減少每個(gè)“工作記錄”的大小便可節(jié)省部分空間。例如某些變參可以轉(zhuǎn)換為全局變量，某些值參可以省略以及過(guò)程內(nèi)部的精簡(jiǎn)。

應(yīng)用分類：

1、遞歸的定義問(wèn)題。樹結(jié)構(gòu)是由遞歸定義的。因此，在解決與樹有關(guān)的問(wèn)題時(shí)，常?？梢圆捎眠f歸的方法。

2、解決搜索問(wèn)題。因?yàn)樗阉鳟a(chǎn)生的節(jié)點(diǎn)成樹狀結(jié)構(gòu)，所以可以用遞歸方法解決。這類例子很多，如“N皇后”問(wèn)題，全排列，哈密頓回路，圖的可著色性等搜索問(wèn)題。

3、實(shí)現(xiàn)分治思想。不難發(fā)現(xiàn)，在各種時(shí)間復(fù)雜度為nlogn排序方法中，大都采用了遞歸的形式。因?yàn)闊o(wú)論是分治合并排序，還是堆排序、快速排序，都存在有分治的思想。只要分開處理，就可以采用遞歸。其實(shí)進(jìn)行分治，也是一個(gè)建樹的過(guò)程。

4、用于輸出動(dòng)態(tài)規(guī)劃的中間過(guò)程。動(dòng)態(tài)規(guī)劃對(duì)空間要求較高，若要保存中間過(guò)程用于輸出，則可能要增加一倍的空間需求。此時(shí)，如果采用遞歸輸出，就完全不需要浪費(fèi)這寶貴的空間。

【例】 給定n（n>=1）,用遞歸的方法計(jì)算1+2+3+4+...+(n-1)+n。

算法分析：本題可以用遞歸方法求解，其原因在于它符合遞歸的三個(gè)條件：

1、本題是累加問(wèn)題：當(dāng)前和=前一次和+當(dāng)前項(xiàng)，而前一次和的計(jì)算方法與其相同，只是數(shù)據(jù)不同s(n)=s(n-1)+n;

2、給定n,所以是有限次的遞歸調(diào)用；

3、結(jié)束條件是當(dāng)n=1，則s=1。

【參考程序】

#include

using namespace std;

int fac(int);                    //遞歸函數(shù)

int main()

{

　　int t;

　　cin>>t;                   //輸入t的值

　　cout<><>

       //計(jì)算1到t的累加和，輸出結(jié)果

}

int fac(int n)

{

　　if (n==1) return 1;

　　return (fac(n-1)+n);          //調(diào)用下一層遞歸

}

運(yùn)行程序，當(dāng)T=5時(shí)，輸出結(jié)果：S=15，其遞歸調(diào)用執(zhí)行過(guò)程如下圖：（設(shè)T=3）

遞歸調(diào)用過(guò)程，實(shí)質(zhì)上是不斷調(diào)用過(guò)程或函數(shù)的過(guò)程，由于遞歸調(diào)用一次，所有子程序的變量（局部變量、變參等）、地址在計(jì)算機(jī)內(nèi)部都有用特殊的管理方法——棧（先進(jìn)后出）來(lái)管理，一旦遞歸調(diào)用結(jié)束，計(jì)算機(jī)便開始根據(jù)棧中存儲(chǔ)的地址返回各子程序變量的值，并進(jìn)行相應(yīng)操作。

搜索

搜索，某種意義上就是對(duì)于枚舉算法的一種改進(jìn)，通過(guò)在枚舉的過(guò)程中，不斷排除一些不可能達(dá)到的情況，從而達(dá)到優(yōu)化復(fù)雜度的效果。

常見方法：

1、深度優(yōu)先搜索（DFS）

主要思想：從一個(gè)頂點(diǎn)沿一條路一直走，如果發(fā)現(xiàn)到不了目標(biāo)節(jié)點(diǎn)，則返回上一個(gè)節(jié)點(diǎn)，沿另一條路一直走到底。總體來(lái)說(shuō)，DFS就是一個(gè)一個(gè)一直處理到底，發(fā)現(xiàn)無(wú)法得到結(jié)果之后，逐步返回尋求其它的出路。

算法優(yōu)化：

1、最優(yōu)化剪枝：求最優(yōu)值時(shí)，當(dāng)前的狀態(tài)無(wú)論如何不可能比最優(yōu)值更優(yōu)，則退出，可與展望結(jié)合剪枝；

2、可行性剪枝：提前判斷該狀態(tài)是否能得到可行解，如不能則退出；

3、記憶化搜索：對(duì)于已經(jīng)搜索過(guò)的狀態(tài)直接退出；

4、改變搜索順序：對(duì)于看起來(lái)希望更大的決策先進(jìn)行搜索；

5、優(yōu)化搜索策略；

6、預(yù)處理找到大體搜索翻譯；

7、改寫成IDA*算法。

2、寬度優(yōu)先搜索（BFS）

主要思想：首先訪問(wèn)起始節(jié)點(diǎn)的所有鄰接點(diǎn)，然后再訪問(wèn)較遠(yuǎn)的區(qū)域，逐步擴(kuò)大范圍，直到找到了目標(biāo)節(jié)點(diǎn)。BFS是一個(gè)處理不含邊權(quán)的圖當(dāng)中求解最短路徑的一個(gè)非常有效的方法。這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。

注意事項(xiàng)：

1、每生成一個(gè)子結(jié)點(diǎn)，就要提供指向它們父親結(jié)點(diǎn)的指針。當(dāng)解出現(xiàn)時(shí)候，通過(guò)逆向跟蹤，找到從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的一條路徑。當(dāng)然不要求輸出路徑，就沒必要記父親。

2、生成的結(jié)點(diǎn)要與前面所有已經(jīng)產(chǎn)生結(jié)點(diǎn)比較，以免出現(xiàn)重復(fù)結(jié)點(diǎn)，浪費(fèi)時(shí)間和空間，還有可能陷入死循環(huán)。

3、如果目標(biāo)結(jié)點(diǎn)的深度與“費(fèi)用”（如：路徑長(zhǎng)度）成正比，那么，找到的第一個(gè)解即為最優(yōu)解，這時(shí)，搜索速度比深度搜索要快些，在求最優(yōu)解時(shí)往往采用寬度優(yōu)先搜索；如果結(jié)點(diǎn)的“費(fèi)用”不與深度成正比時(shí)，第一次找到的解不一定是最優(yōu)解。

4、寬度優(yōu)先搜索的效率還有賴于目標(biāo)結(jié)點(diǎn)所在位置情況，如果目標(biāo)結(jié)點(diǎn)深度處于較深層時(shí)，需搜索的結(jié)點(diǎn)數(shù)基本上以指數(shù)增長(zhǎng)。

算法優(yōu)化：

1、判重的優(yōu)化：hash，二叉排序樹；

2、雙向廣搜或啟發(fā)式搜索；

3、改寫成A*算法；

4、二分優(yōu)化。

3、迭代加深搜索

深度優(yōu)先搜索的優(yōu)點(diǎn)在于能較高效地逼近解，缺點(diǎn)在于初始遞歸方向錯(cuò)誤會(huì)帶來(lái)很嚴(yán)重后果；寬度優(yōu)先搜索的優(yōu)點(diǎn)在于能迅速找到答案不算大的解，缺點(diǎn)在于解答案較大時(shí)所耗時(shí)間與空間都比較大。于是，在綜合以上兩個(gè)算法之后，出現(xiàn)了一個(gè)折中的方法：迭代加深搜索。

主要思想：通過(guò)限定下界k，然后允許深度優(yōu)先搜索搜索k層，一旦仍沒有找到有效解，則增大下界。

主要優(yōu)點(diǎn)：相對(duì)于深度優(yōu)先搜索并沒有大很多的時(shí)間開銷，但能部分解決深度優(yōu)先搜索的局限；無(wú)需寬度優(yōu)先搜索一般的大空間需求。

【例】迷宮問(wèn)題

如下圖所示，給出一個(gè)N*M的迷宮圖和一個(gè)入口、一個(gè)出口。

編一個(gè)程序，打印一條從迷宮入口到出口的路徑。這里黑色方塊的單元表示走不通（用-1表示），白色方塊的單元表示可以走（用0表示）。只能往上、下、左、右四個(gè)方向走。如果無(wú)路則輸出“no way.”。

算法分析：只要輸出一條路徑即可，所以是一個(gè)經(jīng)典的回溯算法問(wèn)題，本例給出了回溯（深搜）程序和寬搜程序。

【深搜參考程序】

#include

using namespace std;

intn,m,desx,desy,soux,souy,totstep,a[51],b[51],map[51][51];

bool f;

int move(int x, int y,int step)

{

 map[x][y]=step;     //走一步，作標(biāo)記，把步數(shù)記下來(lái)

 a[step]=x;  b[step]=y;             //記路徑

  if((x==desx)&&(y==desy))

  {

   f=1;

  totstep=step;

  }

   else

   {

     if((y!=m)&&(map[x][y+1]==0)) move(x,y+1,step+1);         //向右

     if((!f)&&(x!=n)&&(map[x+1][y]==0))  move(x+1,y,step+1);   //往下

     if((!f)&&(y!=1)&&(map[x][y-1]==0))  move(x,y-1,step+1);   //往左

     if((!f)&&(x!=1)&&(map[x-1][y]==0))  move(x-1,y,step+1);   //往上

   }

}

int main()

{

  int i,j;

 cin>>n>>m;                     //n行m列的迷宮

  for(i=1;i<=n;i++)>//讀入迷宮，0表示通，-1表示不通

   for (j=1;j<>

   cin>>map[i][j];

  cout<'input the="">

 cin>>soux>>souy;               //入口

 cout<'input the="">

 cin>>desx>>desy;               //出口

  f=0;      //f=0表示無(wú)解；f=1表示找到了一個(gè)解

 move(soux,souy,1);

  if (f)

  {

    for(i=1;i<> //輸出直迷宮的路徑

    cout<><><><>

  }

else cout<'no><>

return 0;

}

【寬搜參考程序】

#include

using namespace std;

int u[5]={0,0,1,0,-1},

   w[5]={0,1,0,-1,0};

intn,m,i,j,desx,desy,soux,souy,head,tail,x,y,a[51],b[51],pre[51],map[51][51];

bool f;

int print(int d)

{

  if (pre[d]!=0)print (pre[d]);             //遞歸輸出路徑

 cout<><><><>

}

int main()

{

  int i,j;

 cin>>n>>m;                        //n行m列的迷宮

  for(i=1;i<=n;i++)>//讀入迷宮，0表示通，-1表示不通

   for (j=1;j<>

    cin>>map[i][j];

  cout<'input the="">

 cin>>soux>>souy;                             //入口

 cout<'input the="">

 cin>>desx>>desy;                             //出口

  head=0;

  tail=1;

  f=0;

 map[soux][souy]=-1;

 a[tail]=soux;  b[tail]=souy;pre[tail]=0;

  while(head!=tail)                           //隊(duì)列不為空

  {

   head++;

    for(i=1;i<> //4個(gè)方向

    {

     x=a[head]+u[i];  y=b[head]+w[i];

      if((x>0)&&(x<=n)&&(y>0)&&(y<>

     {                                     //本方向上可以走

        tail++;

       a[tail]=x;  b[tail]=y;  pre[tail]=head;

       map[x][y]=-1;

       if ((x==desx)&&(y==desy))    

      //擴(kuò)展出的結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn)

        {

         f=1;

         print(tail);

         break;

        }

      }

    }

    if(f) break;

  }

  if (!f)cout<'no><>

  return 0;

}

分治

基本思想：將一個(gè)較大規(guī)模的問(wèn)題分成多個(gè)（一般是2個(gè)）較小規(guī)模的互相獨(dú)立且與原問(wèn)題相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。當(dāng)我們將問(wèn)題分解成兩個(gè)較小問(wèn)題求解時(shí)的分治方法稱之為二分法。

適用條件：

1、該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；

2、該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；

3、利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；

4、該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子子問(wèn)題。

遞歸與分治的算法思想往往是相伴而生的，它們?cè)诟黝愃惴ㄖ惺褂梅浅ｎl繁，應(yīng)用遞歸和分治的算法思想有時(shí)可以設(shè)計(jì)出代碼簡(jiǎn)潔且比較高效的算法來(lái)。

解題步驟：

1、分解，將要解決的問(wèn)題劃分成若干規(guī)模較小的同類問(wèn)題；

2、求解，當(dāng)子問(wèn)題劃分得足夠小時(shí)，用較簡(jiǎn)單的方法解決；

3、合并，按原問(wèn)題的要求，將子問(wèn)題的解逐層合并構(gòu)成原問(wèn)題的解。

應(yīng)用分類： 二分搜索；大整數(shù)乘法；Strassen矩陣乘法；棋盤覆蓋；合并排序；快速排序；線性時(shí)間選擇；最接近點(diǎn)對(duì)問(wèn)題；循環(huán)賽日程表；漢諾塔等。

例：NOIP2012借教室；NOIP2013轉(zhuǎn)圈游戲等

【例】用遞歸算法實(shí)現(xiàn)二分查找即：有n個(gè)已經(jīng)從小到大排序好的數(shù)據(jù)，輸入一個(gè)數(shù)m，用二分查找算法，判斷它是否在這n個(gè)數(shù)中。

#include

using namespace std;

int jc(int,int);

int n,a[1000],m;

int main()

{

  intx,y,i; 

 cin>>n;

  x=1;y=n;

  for(i=1;i<> //輸入排序好的數(shù)

  cin>>a[i];

 cin>>m;                                //輸入要查找的數(shù)

 jc(x,y);                                 //遞歸過(guò)程

 cout<>

}

int jc(int x,int y)                           //遞歸過(guò)程

{

   int k;

  k=(x+y)/2;                          //取中間位置點(diǎn)

   if(a[k]==m)

   cout<'thennum in =""><>

  //找到查找的數(shù)，輸出結(jié)果

   if (x>y)cout<'no>//找不到該數(shù)

           else

             {

               if (a[k]//在后半中查找

               if (a[k]>m) jc(x,k-1);         //在前半中查找

             }

}

貪心

基本思想：貪心，又稱貪婪算法。指的是在對(duì)問(wèn)題求解過(guò)程中，總是做出目前來(lái)看最優(yōu)的選擇，也就是說(shuō)貪心算法不會(huì)考慮全局最優(yōu)解，而只會(huì)不斷考慮局部最優(yōu)解。是一種對(duì)某些求最優(yōu)解問(wèn)題的更簡(jiǎn)單、更迅速的設(shè)計(jì)技術(shù)。往往可以以較低的代碼復(fù)雜度與時(shí)間復(fù)雜度而得到較優(yōu)的結(jié)果，對(duì)于求解近似值的作用很大。

貪心算法沒有固定的算法框架，算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇。必須注意的是，貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無(wú)后效性，即某個(gè)狀態(tài)以后的過(guò)程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

當(dāng)存在一些題目的正解想不出來(lái)，并且一個(gè)貪心原則又效果不好的情況下，可以采取多個(gè)貪心原則同時(shí)用，并取最優(yōu)的方案來(lái)解決。但對(duì)于相當(dāng)一部分需要求解最優(yōu)值的問(wèn)題，實(shí)際上我們會(huì)發(fā)現(xiàn)我們通?？梢圆捎脛?dòng)態(tài)規(guī)劃或者網(wǎng)絡(luò)流的方法取代貪心算法。

適用條件：

1、可通過(guò)局部的貪心選擇來(lái)達(dá)到問(wèn)題的全局最優(yōu)解。運(yùn)用貪心策略解題，一般來(lái)說(shuō)需要一步步的進(jìn)行多次的貪心選擇。在經(jīng)過(guò)一次貪心選擇之后，原問(wèn)題將變成一個(gè)相似的，但規(guī)模更小的問(wèn)題，而后的每一步都是當(dāng)前看似最佳的選擇，且每一個(gè)選擇都僅做一次。

2、原問(wèn)題的最優(yōu)解包含子問(wèn)題的最優(yōu)解，即問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。在下面示例的背包問(wèn)題中，第一次選擇單位重量?jī)r(jià)值最大的貨物，它是第一個(gè)子問(wèn)題的最優(yōu)解，第二次選擇剩下的貨物中單位重量?jī)r(jià)值最大的貨物，同樣是第二個(gè)子問(wèn)題的最優(yōu)解，依次類推。

3、其次，如何選擇一個(gè)貪心標(biāo)準(zhǔn)？正確的貪心標(biāo)準(zhǔn)可以得到問(wèn)題的最優(yōu)解，在確定采用貪心策略解決問(wèn)題時(shí)，不能隨意的判斷貪心標(biāo)準(zhǔn)是否正確，尤其不要被表面上看似正確的貪心標(biāo)準(zhǔn)所迷惑。在得出貪心標(biāo)準(zhǔn)之后應(yīng)給予嚴(yán)格的數(shù)學(xué)證明。

解題步驟：

1、建立數(shù)學(xué)模型來(lái)描述問(wèn)題；

2、把求解的問(wèn)題分成若干個(gè)子問(wèn)題；

3、對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解；

4、把子問(wèn)題的解局部最優(yōu)解合成原來(lái)解問(wèn)題的一個(gè)解。

例：NOIP2012國(guó)王游戲；NOIP2013積木大賽；NOIP2015跳石頭等。

【例】部分背包問(wèn)題

給定一個(gè)最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價(jià)值為Vi元/公斤，編程確定一個(gè)裝貨方案，使得裝入卡車中的所有物品總價(jià)值最大。

算法分析：因?yàn)槊恳粋€(gè)物品都可以分割成單位塊，單位塊的利益越大顯然總收益越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解答，方法如下：先將單位塊收益按從大到小進(jìn)行排列，然后用循環(huán)從單位塊收益最大的取起，直到不能取為止便得到了最優(yōu)解。

因此我們非常容易設(shè)計(jì)出如下算法：

問(wèn)題初始化；                             //讀入數(shù)據(jù)

按Vi從大到小將商品排序；

　　i=1;

　　do

　　{ 

　　  if (m==0)  break;       //如果卡車滿載則跳出循環(huán)

　　  m=m-w[i];

　　  if (m>=0)                    //將第i種商品全部裝入卡車

　　  else  將(m+w[i])  重量的物品i裝入卡車;

　　  i=i+1;                                 //選擇下一種商品

　　}while (m>0&&i<>

在解決上述問(wèn)題的過(guò)程中，首先根據(jù)題設(shè)條件，找到了貪心選擇標(biāo)準(zhǔn)(Vi)，并依據(jù)這個(gè)標(biāo)準(zhǔn)直接逐步去求最優(yōu)解，這種解題策略被稱為貪心法。

 回溯

基本思想：在包含問(wèn)題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹。當(dāng)探索到某一結(jié)點(diǎn)時(shí)，要先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解，如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去；如果該結(jié)點(diǎn)不包含問(wèn)題的解，那就說(shuō)明以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹一定不包含問(wèn)題的最終解，因此要跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)探索，逐層向其祖先結(jié)點(diǎn)回溯。這個(gè)過(guò)程叫做解空間樹的“剪枝”操作。如果應(yīng)用回溯法求解問(wèn)題的所有解，要回溯到解空間樹的樹根，這樣根結(jié)點(diǎn)的所有子樹都被探索到才結(jié)束。如果只要求解問(wèn)題的一個(gè)解，那么在探索解空間樹時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束了。

【例】素?cái)?shù)環(huán):從1到20這20個(gè)數(shù)擺成一個(gè)環(huán)，要求相鄰的兩個(gè)數(shù)的和是一個(gè)素?cái)?shù)。

算法分析：非常明顯，這是一道回溯的題目。從1開始，每個(gè)空位有20種可能，只要填進(jìn)去的數(shù)合法：與前面的數(shù)不相同；與左邊相鄰的數(shù)的和是一個(gè)素?cái)?shù)。第20個(gè)數(shù)還要判斷和第1個(gè)數(shù)的和是否素?cái)?shù)。

算法流程：

1、數(shù)據(jù)初始化；  

2、遞歸填數(shù)：判斷第i個(gè)數(shù)填入是否合法

A、如果合法：填數(shù)；判斷是否到達(dá)目標(biāo)（20個(gè)已填完）：是，打印結(jié)果；不是，遞歸填下一個(gè)；

B、如果不合法：選擇下一種可能。

【參考程序】

#include

#include

#include

#include

using namespace std;

bool b[21]={0};

int total=0,a[21]={0};

int search(int);                    //回溯過(guò)程

int print();                       //輸出方案

bool pd(int,int);                  //判斷素?cái)?shù)

int main()

{

    search(1);

   cout<><>   //輸出總方案數(shù)

}

int search(int t)

{

    int i;

    for(i=1;i<>//有20個(gè)數(shù)可選

     if(pd(a[t-1],i)&&(!b[i]))      

 //判斷與前一個(gè)數(shù)是否構(gòu)成素?cái)?shù)及該數(shù)是否可用

      {

        a[t]=i;

        b[i]=1;

         if(t==20) { if (pd(a[20],a[1])) print();}

            else search(t+1);

        b[i]=0;

      }

}

int print()

{

   total++;

  cout<><><><'>';

   for (intj=1;j<>

    cout<><'>

  cout<>

  }

bool pd(int x,int y)

{

    intk=2,i=x+y;

    while(k<=sqrt(i)&&i%k!=0)>

    if(k>sqrt(i)) return 1;

       elsereturn 0;

}

動(dòng)態(tài)規(guī)劃

基本思想：在多階段決策的問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與時(shí)間或空間有關(guān)的。決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)，故有“動(dòng)態(tài)”的含義，我們稱這種解決多階段決策最優(yōu)化的過(guò)程為動(dòng)態(tài)規(guī)劃方法。

基本概念：

階段：把所求問(wèn)題的過(guò)程按照時(shí)間或空間恰當(dāng)?shù)胤殖扇舾蓚€(gè)相互聯(lián)系的階段。

狀態(tài)：表示每個(gè)階段的客觀狀態(tài)，它既是某階段的出發(fā)位置，又是前一階段的終點(diǎn)。

無(wú)后效性：如果給定某一階段的狀態(tài)，則在這一階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響，所以各階段確定時(shí)，整個(gè)過(guò)程也就確定了。

決策：一個(gè)階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段狀態(tài)的一種選擇(行動(dòng))。

策略：由每個(gè)階段的決策組成的序列。

最優(yōu)性原理：把一個(gè)大問(wèn)題劃分成多個(gè)子問(wèn)題，對(duì)于整個(gè)問(wèn)題必須最優(yōu)的情況時(shí)，問(wèn)題也必須最優(yōu)，即問(wèn)題具備最優(yōu)子結(jié)構(gòu)的性質(zhì)。

適用條件：

1、最優(yōu)子結(jié)構(gòu)。如果問(wèn)題的一個(gè)最優(yōu)解中包含了子問(wèn)題的最優(yōu)解，則該問(wèn)題具有最優(yōu)子結(jié)構(gòu)。也稱最優(yōu)化原理。最優(yōu)子結(jié)構(gòu)也可以理解為“整體最優(yōu)則局部最優(yōu)”。反之不一定成立。

2、重疊子問(wèn)題。在解決整個(gè)問(wèn)題時(shí)，要先解決其子問(wèn)題，要解決這些子問(wèn)題，又要先解決他們的子子問(wèn)題 ……。而這些子子問(wèn)題又不是相互獨(dú)立的，有很多是重復(fù)的，這些重復(fù)的子子問(wèn)題稱為重疊子問(wèn)題。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表中，以后再遇到這些相同問(wèn)題時(shí)直接查表就可以，而不需要再重復(fù)計(jì)算，每次查表的時(shí)間為常數(shù)。

3、無(wú)后效性原則。已經(jīng)求得的狀態(tài)，不受未求狀態(tài)的影響。

解題步驟：

1、判斷問(wèn)題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)，若不具備，則不能用動(dòng)態(tài)規(guī)劃；

2、把問(wèn)題分成若干個(gè)子問(wèn)題(分階段)；

3、建立狀態(tài)轉(zhuǎn)移方程(遞推公式)；

4、找出邊界條件；

5、設(shè)定初始值；

6、遞推求解。

狀態(tài)轉(zhuǎn)移方程的構(gòu)造是動(dòng)態(tài)規(guī)劃過(guò)程中最重要的一步，也是最難的一步。對(duì)于大多數(shù)的動(dòng)態(tài)規(guī)劃，尋找狀態(tài)轉(zhuǎn)移方程有一條十分高效的通道，就是尋找變化中的不變量（已經(jīng)求得的值）。

例：背包型動(dòng)態(tài)規(guī)劃：POJ1014,1068；序列型動(dòng)態(tài)規(guī)劃：POJ 1044,1576,3027；區(qū)間型動(dòng)態(tài)規(guī)劃：POJ 1048,1154,1166；棋盤性動(dòng)態(tài)規(guī)劃：POJ 1010,1169,1219,1220；劃分型動(dòng)態(tài)規(guī)劃：POJ 1017,1039,1040；樹型動(dòng)態(tài)規(guī)劃：POJ 1163,1380等

【例1】最短路徑問(wèn)題

下圖給出了一個(gè)地圖，地圖中的每個(gè)頂點(diǎn)代表一個(gè)城市，兩個(gè)城市間的一條連線代表道路，連線上的數(shù)值代表道路的長(zhǎng)度。現(xiàn)在想從城市A到達(dá)城市E，怎樣走路程最短？最短路程的長(zhǎng)度是多少？

算法分析：把A到E的全過(guò)程分成四個(gè)階段，用K表示階段變量，第1階段有一個(gè)初始狀態(tài)A，有兩條可供選擇的支路A-B1、A-B2；第2階段有兩個(gè)初始狀態(tài)B1、B2，B1有三條可供選擇的支路，B2有兩條可供選擇的支路……。用DK（X_I，X+1_J）表示在第K階段由初始狀態(tài)X_I到下階段的初始狀態(tài)X+1_J的路徑距離，F(xiàn)K（X_I）表示從第K階段的X_I到終點(diǎn)E的最短距離，利用倒推的方法，求解A到E的最短距離。

具體計(jì)算過(guò)程如下：

S1： K = 4 有

F4（D1）= 3，

F4（D2）= 4，

F4（D3）= 3；

S2： K = 3 有

F3（C1）= MIN{ D3（C1，D1）+ F4（D1），D3（C1，D2）+ F4（D2）}

        = MIN{ 5+3，6+4 } = 8

F3（C2）= D3（C2，D1）+ F4（D1）= 5+3 = 8

F3（C3）= D3（C3，D3）+ F4（D3）= 8+3 = 11

F3（C4）= D3（C4，D3）+ F4（D3）= 3+3 = 6

S3： K = 2 有  

F2（B1）= MIN{ D2（B1，C1）+ F3（C1），D2（B1，C2）+ F3（C2），

D2（B1，C3）+ F3(C3)} = MIN{ 1+8,6+8,3+11} = 9

F2（B2）= MIN{ D2（B2，C2）+ F3（C2），D2（B2，C4）+ F3（C4）}

        = MIN{ 8+8，4+6 } = 10

S4： K = 1 有

F1（A）= MIN{ D1（A，B1）+ F2（B1），D1（A，B2）+ F2（B2）}

       = MIN{ 5+9，3+10} = 13

因此由A點(diǎn)到E點(diǎn)的全過(guò)程最短路徑為A→B2→C4→D3→E；最短路程長(zhǎng)度為13。

從以上過(guò)程可以看出，每個(gè)階段中，都求出本階段的各個(gè)初始狀態(tài)到終點(diǎn)E的最短距離，當(dāng)逆序倒推到過(guò)程起點(diǎn)A時(shí)，便得到了全過(guò)程的最短路徑和最短距離。

在上例的多階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與階段有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有“動(dòng)態(tài)”的含義，我們稱這種解決多階段決策最優(yōu)化的過(guò)程為動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)方法。

#include

#include

usingnamespace std;

intmain()

{

   long d[5][5][5],f[10][10];

  memset(d,42,sizeof(d));         

//有些路徑是不通的,賦值為較大值，用于判斷

   d[1][1][1]=5;d[1][1][2]=3;d[2][1][1]=1;  

//以下給可通路徑賦正常值

   d[2][1][2]=6;d[2][1][3]=3;d[2][2][2]=8

   d[2][2][4]=4;d[3][1][1]=5;d[3][1][2]=6;

   d[3][2][1]=5;d[3][3][3]=8;d[3][4][3]=3;

   d[4][1][1]=3;d[4][2][1]=4;d[4][3][1]=3;

   for (int i=0;i<>

    for (int j=0;j<=9;++j) f[i][j]="">

   f[5][1]=0;

   for (int i=4;i>=1;--i)

    for (int j=1;j<>

     for (int k=1;k<>

       if(f[i][j]>d[i][j][k]+f[i+1][k])    

//即使走非法路徑，也不影響答案

          f[i][j]=d[i][j][k]+f[i+1][k];

    cout<><>

}

【例2】混合背包

一個(gè)旅行者有一個(gè)最多能用V公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，...,Wn，它們的價(jià)值分別為C1,C2,...,Cn。有的物品只可以取一次（01背包），有的物品可以取無(wú)限次（完全背包），有的物品可以取的次數(shù)有一個(gè)上限（多重背包）。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。

【輸入格式】

第一行：二個(gè)整數(shù)，V(背包容量，V<><>

第2..N+1行：每行三個(gè)整數(shù)Wi,Ci,Pi，前兩個(gè)整數(shù)分別表示每個(gè)物品的重量，價(jià)值，第三個(gè)整數(shù)若為0，則說(shuō)明此物品可以購(gòu)買無(wú)數(shù)件，若為其他數(shù)字，則為此物品可購(gòu)買的最多件數(shù)(Pi)。

【輸出格式】

僅一行，一個(gè)數(shù)，表示最大總價(jià)值。

【樣例輸入】mix.in

104

2  1  0

3  3  1

4  5  4

【樣例輸出】mix.out

11

【樣例解釋】

選第一件物品1件和第三件物品2件。

【參考程序】

#include

using namespace std;

int m, n;

int w[31], c[31], p[31];

int f[201];

int max(int x,int y) { return  x>y?x:y; }

int main(){

   scanf('%d%d',&m,&n);

    for (int i =1; i <= n;="">

       scanf('%d%d%d',&w[i],&c[i],&p[i]);

    for (int i =1; i <= n;="">

        if (p[i]== 0)  {                        //完全背包

            for(int j = w[i]; j <= m;="">

               f[j] = max(f[j], f[j-w[i]]+c[i]);

        }

        else {

            for(int j = 1; j <= p[i];="">//01背包和多重背包

               for (int k = m; k >= w[i]; k--)

                   f[k] = max(f[k],f[k-w[i]]+c[i]);

        }

   printf('%d',f[m]);

    return 0;

}

按解題的目標(biāo)來(lái)分，信息學(xué)試題主要分四類：判定性問(wèn)題、構(gòu)造性問(wèn)題、計(jì)數(shù)問(wèn)題和最優(yōu)化問(wèn)題。我們?cè)诟?jìng)賽中碰到的大多是最優(yōu)化問(wèn)題，而動(dòng)態(tài)規(guī)劃正是解決最優(yōu)化問(wèn)題的有力武器，因此動(dòng)態(tài)規(guī)劃在競(jìng)賽中的地位日益提高。而遞推法在處理判定性問(wèn)題和計(jì)數(shù)問(wèn)題方面也是一把利器。