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

1、動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃-入門(mén)篇入門(mén)篇Dynamic programmingEZOI多階段決策過(guò)程（ multistep decision process ）是指這樣一類(lèi)特殊的活動(dòng)過(guò)程，過(guò)程可以按時(shí)間順序分解成若干個(gè)相互聯(lián)系的階段，在每一個(gè)階段都需要做出決策，全部過(guò)程的決策是一個(gè)決策序列。 （dynamic programming ）算法是解決多階段決策過(guò)程最優(yōu)化問(wèn)題的一種常用方法，難度比較大，技巧性也很強(qiáng)。利用動(dòng)態(tài)規(guī)劃算法，可以?xún)?yōu)雅而高效地解決很多貪婪算法或分治算法不能解決的問(wèn)題。求解問(wèn)題的兩個(gè)重要性質(zhì)：如果問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的，我們就稱(chēng)該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（ 即滿(mǎn)足最優(yōu)化原

2、理 ）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動(dòng)態(tài)規(guī)劃算法解決問(wèn)題提供了重要線(xiàn)索。 ：在用遞歸算法自頂向下對(duì)問(wèn)題進(jìn)行求解時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題會(huì)被重復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子問(wèn)題只計(jì)算一次，然后將其計(jì)算結(jié)果保存在一個(gè)表格中，當(dāng)再次需要計(jì)算已經(jīng)計(jì)算過(guò)的子問(wèn)題時(shí)，只是在表格中簡(jiǎn)單地查看一下結(jié)果，從而獲得較高的解題效率。動(dòng)態(tài)規(guī)劃與分治、遞歸、貪心的區(qū)別在程序?qū)崿F(xiàn)上直觀(guān)容易，但因?yàn)樽訂?wèn)題被重復(fù)計(jì)算，且程序背后存在對(duì)棧的操作，速度（計(jì)算復(fù)雜度一般是指數(shù)級(jí)的）上劣于動(dòng)態(tài)規(guī)劃。在遞歸的過(guò)程中，通過(guò)保存子問(wèn)題的結(jié)果，可以減少計(jì)算量，同樣是空間換時(shí)間的思想，稱(chēng)作memo

3、ization算法。要求各個(gè)子問(wèn)題是獨(dú)立的(即不包含公共的子問(wèn)題)，因此一旦遞歸地求出各個(gè)子問(wèn)題的解后，便可自下而上地將子問(wèn)題的解合并成原問(wèn)題的解。動(dòng)態(tài)規(guī)劃與分治法的不同之處在于動(dòng)態(tài)規(guī)劃允許這些子問(wèn)題不獨(dú)立(即各子問(wèn)題可包含公共的子問(wèn)題)，它對(duì)每個(gè)子問(wèn)題只解一次，并將結(jié)果保存起來(lái)，避免每次碰到時(shí)都要重復(fù)計(jì)算。這就是動(dòng)態(tài)規(guī)劃高效的一個(gè)原因。在中，每采用一次貪婪準(zhǔn)則，便做出一個(gè)不可撤回的決策；而在動(dòng)態(tài)規(guī)劃算法中，還要考察每個(gè)最優(yōu)決策序列中是否包含一個(gè)最優(yōu)決策子序列，即問(wèn)題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)。最短路徑問(wèn)題 圖中給出了一個(gè)地圖，地圖中每個(gè)頂點(diǎn)代表一個(gè)城市，兩個(gè)城市間的連線(xiàn)代表道路，連線(xiàn)上的數(shù)值代表

4、道路的長(zhǎng)度。現(xiàn)在，想從城市A到達(dá)城市E，怎樣走路程最短，最短路程的長(zhǎng)度是多少? 題題1 最長(zhǎng)不下降子序列【問(wèn)題描述】 設(shè)有整數(shù)序列b1,b2,b3,bm，若存在i1i2i3in，且bi1bi2bi3bin，則稱(chēng) b1,b2,b3,bm中有長(zhǎng)度為n的不下降序列bi1,bi2,bi3,bin。求序列b1,b2,b3,bm中所有長(zhǎng)度(n)最大不下降子序列輸入：整數(shù)序列輸出：最大長(zhǎng)度n題題1 最長(zhǎng)不下降子序列【分析】設(shè)F(i)為前I個(gè)數(shù)中的最大不下降序列長(zhǎng)度。由題意不難得知，要求F(i)，需要求得F(1)F(i-1)，然后選擇一個(gè)最大的F(j) ( jbj )，那么前I個(gè)數(shù)中最大不下降序列便是前j個(gè)數(shù)

5、中最大不下降序列后添加bi而得?？梢?jiàn)此任務(wù)滿(mǎn)足最優(yōu)子結(jié)構(gòu)，可以用動(dòng)態(tài)規(guī)劃解決。通過(guò)上面的分析可得狀態(tài)轉(zhuǎn)移方程如下： F(i)=maxF(j)+1 (ji, bjbj)and(filen then len:=fi 記錄最大值題題2 數(shù)塔如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左下走或是向右下走，一直走到底層，要求找出一條路徑，使路徑上的數(shù)的和最大。數(shù)塔層數(shù)用n表示，1=n=100。題題2 數(shù)塔 貪心法。時(shí)間上有保證，但得不到最優(yōu)解。主要原因是貪心法只顧眼前利益，不考慮長(zhǎng)遠(yuǎn)利益。 在規(guī)定時(shí)間內(nèi)得到正確結(jié)果，唯一的方法就是“動(dòng)態(tài)規(guī)劃”。 下面以示意圖表示動(dòng)態(tài)規(guī)劃的過(guò)程：所選路徑為：9-12

6、-10-18-10注意分析時(shí)，有以下幾個(gè)特點(diǎn)：（1）將問(wèn)題劃分成了4個(gè)階段；（2）每個(gè)階段均得到了“部分”的最優(yōu)解，得到最優(yōu)解時(shí)，需要進(jìn)行條件判斷；（3）從最下面一層往頂層推導(dǎo)。題題3 棋盤(pán)路徑問(wèn)題【題目簡(jiǎn)介】有一個(gè)n*m的棋盤(pán)，左下角為（1,1），右上角為（n,m），如下圖： 有一顆棋子，初始位置在（1,1），該棋子只能向右走或者向上走，問(wèn)該棋子從（1,1）到（n,m）一共有幾條路徑？輸入：兩個(gè)整數(shù)n和m輸出：一個(gè)數(shù)，路徑總數(shù)題題3 棋盤(pán)路徑問(wèn)題【題目簡(jiǎn)介】如果使用枚舉的方法，必定有很多路徑被重復(fù)走過(guò)，這樣，勢(shì)必造成程序運(yùn)行時(shí)間的浪費(fèi)，當(dāng)n和m的值比較大的時(shí)候，程序很可能超時(shí)。為了避免程序的

7、重復(fù)運(yùn)行，我們可以通過(guò)記錄點(diǎn)（1,1）到任意一個(gè)點(diǎn)（I,j）的路徑總數(shù)來(lái)解決這個(gè)問(wèn)題。假設(shè)FI,j是點(diǎn)(1,1)到點(diǎn)(I,j)(1in, 1jm)的路徑總數(shù)，因?yàn)槠遄釉谄灞P(pán)中只能向右或者向上走，所以棋盤(pán)中只能2個(gè)點(diǎn)的棋子可以走到點(diǎn)（I,j），即點(diǎn)(I,j-1)和(i-1,j)，這樣，我們就可以知道，F(xiàn)I,j必定是FI,j-1和Fi-1,j的和，即Fi,j=Fi-1,j+Fi,j-1【例4】街道問(wèn)題在下圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走?！纠?】街道問(wèn)題 在一般情況下，如果我們用二維數(shù)組H(i，j)和V(i，j)分別表示水平方向和豎直方向的各路段長(zhǎng)度，如H(1，2)表示水

8、平方向上路口 (1，1)到路口(1，2)的路段長(zhǎng)度，V(1，2)表示豎值方向上路口(0，2)到路口(1，2)的路段長(zhǎng)度，則有公式：如dpl(i，j)=mindpl(i-1，j)+v(i，j)，dpl(i，j-1)+h(i，j) 題題5 機(jī)器分配【問(wèn)題描述】總公司擁有高效生產(chǎn)設(shè)備M臺(tái)，準(zhǔn)備分給下屬的N個(gè)公司。各分公司若獲得這些設(shè)備，可以為國(guó)家提供一定的盈利。問(wèn)：如何分配這M臺(tái)設(shè)備才能使國(guó)家得到的盈利最大？求出最大盈利值。其中M15，N10。分配原則：每個(gè)公司有權(quán)獲得任意數(shù)目的設(shè)備，但總臺(tái)數(shù)不得超過(guò)總設(shè)備數(shù)M。保存數(shù)據(jù)的文件名從鍵盤(pán)輸入。數(shù)據(jù)文件格式為：第一行保存兩個(gè)數(shù)，第一個(gè)數(shù)是設(shè)備臺(tái)數(shù)M，第二

9、個(gè)數(shù)是分公司數(shù)N。接下來(lái)是一個(gè)M*N的矩陣，表明了第I個(gè)公司分配J臺(tái)機(jī)器的盈利。題題5 機(jī)器分配【分析】 這是一個(gè)典型的動(dòng)態(tài)規(guī)劃試題。用機(jī)器數(shù)來(lái)做狀態(tài)，數(shù)組FI，J表示前I個(gè)公司分配J臺(tái)機(jī)器的最大盈利。則狀態(tài)轉(zhuǎn)移方程為 Fi，j=MaxFi-1，k + Valuei，j-k （0=K=J題題6 0-1背包問(wèn)題【題目】 有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是ci，價(jià)值是wi。求解將哪些物品裝入背包可使價(jià)值總和最大。題題6 0-1背包問(wèn)題這是最基礎(chǔ)的背包問(wèn)題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。用子問(wèn)題定義狀態(tài)：即fiv表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。

10、則其狀態(tài)轉(zhuǎn)移方程便是：fiv=maxfi-1v,fi-1v-ci+wi題題7 完全背包問(wèn)題【題目】有N種物品和一個(gè)容量為V的背包，每種物品都有無(wú)限件可用。第i種物品的費(fèi)用是ci，價(jià)值是wi。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。題題7 完全背包問(wèn)題【基本思路】這個(gè)問(wèn)題非常類(lèi)似于01背包問(wèn)題，所不同的是每種物品有無(wú)限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件等很多種。如果仍然按照解01背包時(shí)的思路，令fiv表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫(xiě)出狀態(tài)轉(zhuǎn)移方程，像這

11、樣：fiv=maxfi-1v-k*ci+k*wi0=k*ci=v題題8 攔截導(dǎo)彈某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來(lái)的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于 30000 的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，并依次輸出被攔截的導(dǎo)彈飛來(lái)時(shí)候的高度。 樣例： INPUT 389 207 155 300 299 170 158 65 OUTPUT 6 （最多能攔截的導(dǎo)彈數(shù)），題題8 攔截導(dǎo)彈【分析】 設(shè) D(i) 為第 i 枚導(dǎo)彈被攔截之后，這套系統(tǒng)最多還能攔截的導(dǎo)彈數(shù)（包含被攔截的第 i 枚）。我們可以設(shè)想，當(dāng)系統(tǒng)攔截了第 k 枚導(dǎo)彈 x k ，而 x k 又是序列 X=x 1 ,x 2 ,x n 中的最小值，即第 k 枚導(dǎo)彈為所有飛來(lái)的導(dǎo)彈中高度最低的，則有 D(k)=1 ；當(dāng)系統(tǒng)攔截了最后一枚導(dǎo)彈 xn ，那么，系統(tǒng)最多也只能攔截這一枚導(dǎo)彈了，即 D(n)=1 ；其它情況下，也應(yīng)該有 D(i)1 。