動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)

1、動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)青島二中04級(jí)李辰動(dòng)態(tài)規(guī)劃是信息學(xué)競(jìng)賽中的一種利用擴(kuò)大空間占用而縮短時(shí)間消耗的設(shè)計(jì)方法。現(xiàn)今的幾乎所有程序設(shè)計(jì)競(jìng)賽中，隨著空間的限制逐漸減小，時(shí)間已經(jīng)成為極重要的衡量程序優(yōu)劣的標(biāo)準(zhǔn)。因此，動(dòng)態(tài)規(guī)劃以其靈活性和高效性逐漸為大家的所喜愛。但是由于其概念比較抽象，對(duì)剛接觸的人來講理解起來并不容易。本文將結(jié)合例題，系統(tǒng)細(xì)致地解釋動(dòng)態(tài)規(guī)劃，同時(shí)介紹一些在使用動(dòng)態(tài)規(guī)劃過程中常運(yùn)用到的技巧。相信所有程序設(shè)計(jì)者對(duì)搜索算法很熟悉， 而在搜索能解決的題目中，有很大一部分題能利用動(dòng)態(tài)規(guī)劃解決， 而其效率是搜索所無法比擬的。這類題目的一大特點(diǎn)是在用搜索解決的過程中，不斷重復(fù)了一項(xiàng)已經(jīng)進(jìn)行過的工作。 動(dòng)

2、態(tài)規(guī)劃之所以能極大地提高解題效率，是因?yàn)樗鼉?chǔ)存下了這些已經(jīng)進(jìn)行過得工作的結(jié)果，下次使用時(shí)只需將結(jié)果調(diào)出。 這也是為什么現(xiàn)在很多人把動(dòng)態(tài)規(guī)劃叫做：記憶化搜索。下面這道題就是一個(gè)從搜索轉(zhuǎn)到記憶化搜索動(dòng)態(tài)規(guī)劃的很好例子。一個(gè)數(shù)字三角形 ,形式如下 :12 34 5 678910找出從第一層到最后一層的一條路, 使得所經(jīng)過的權(quán)值之和最大 . 從每層到下面一層只能向左下或右下走。讓我們來模擬一下深度優(yōu)先搜索的過程（走法選擇先選左下，后選右下， <表示無法深入搜索，回溯） ：1247<8<<58<9<<<358<9<<69<10<

3、; < < < 不計(jì)回溯總共需要 15 步（因?yàn)槊繉拥较乱粚佣加星抑挥?2 種選擇，所以理論上三角形有n 層就需要 2 的 n 次方 -1 步）仔細(xì)觀察不難發(fā)現(xiàn)， 想到達(dá)每層中除了最左邊和最右邊的數(shù)字都只有兩種選擇（左上或右上）。達(dá)任意數(shù)字時(shí)的最大值是該數(shù)字 +到達(dá)左上或右上數(shù)字時(shí)的最大值中的較大值。這樣寫比較難懂，讓我們用數(shù)學(xué)語(yǔ)言解釋。不妨設(shè)va ， b 表示第 a 行第 b 列的數(shù)字。fa ，b 表示從頂端到第a 行第 b 列的數(shù)字得到的最大值。max(a， b) 表示 a，b 中較大的那一個(gè)。則 fa，b=max（ fa-1 ， b-1 ，fa-1，b ）+va ， b

4、這樣就抽象出了動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程，我們只需要找出實(shí)現(xiàn)動(dòng)態(tài)方程的循環(huán)方法， 該循環(huán)方法要保證在計(jì)算到當(dāng)前所求值時(shí)方程右邊的元素已經(jīng)全部算出。即在計(jì)算到fa，b時(shí)保證已經(jīng)計(jì)算出了fa-1， b-1和fa-1，b（ va， b為已知值）此題的循環(huán)方法較簡(jiǎn)單，設(shè)i 表示第i 行， j表示第j列雙重循環(huán)即可實(shí)現(xiàn)。For i:=2 to n doFor j:=1 to i do（第i行有i個(gè)數(shù)字）fi，j=max（fi-1，j-1， fi-1， j）+vi， j（在三角形兩邊需要簡(jiǎn)單地特殊處理一下，例如把fi,0和fi,i+1均賦值為0 等很多方法都可以）若三角形有 n 層則此算法的理論計(jì)算量為理論效率

5、N=10N=100n 的平方。N=1000搜索2 的n 次方1024次約10 的31約 10的300次方次次方動(dòng)態(tài)規(guī)劃N的平方100 次10000 次10 的 6 次方按一臺(tái)計(jì)算機(jī)每秒運(yùn)算1 億次來看，即使 n=10000 用動(dòng)態(tài)規(guī)劃也可在 1 秒鐘左右出結(jié)果。 而搜索的時(shí)間代價(jià)已經(jīng)大得無法接受。相信通過上面的例子大家已經(jīng)對(duì)動(dòng)態(tài)規(guī)劃有了一定認(rèn)識(shí)。但動(dòng)態(tài)規(guī)劃的思想絕不僅僅是“記憶化搜索”這幾個(gè)字能概括的，動(dòng)態(tài)規(guī)劃還有一個(gè)重要的特點(diǎn)是它的目標(biāo)狀態(tài)是由前面一個(gè)狀態(tài)得到的， 而前面一個(gè)狀態(tài)又由再前面一個(gè)狀態(tài)得到， 有點(diǎn)類似遞推或遞歸， 但又不像遞推和遞歸那樣一步步按部就班， 目的明確。動(dòng)態(tài)規(guī)劃方程運(yùn)算

6、結(jié)束后， 我們會(huì)發(fā)現(xiàn)除了從初始狀態(tài)到目標(biāo)狀態(tài)的各個(gè)狀態(tài)外，我們還對(duì)許多其他“多余”的狀態(tài)進(jìn)行了處理，但在動(dòng)態(tài)規(guī)劃方程運(yùn)算結(jié)束之前我們并不知道哪些狀態(tài)無法達(dá)到目標(biāo)狀態(tài)，因此無從取舍。拿上面的題舉例子，我們不但找到了到達(dá) 10 的最大權(quán)值和走法，我們還找到了到達(dá)任何一個(gè)頂點(diǎn)的最大權(quán)值和走法， 這雖然看上去是一種浪費(fèi)， 但其實(shí)我們不得不做，因?yàn)樵诮Y(jié)果得出前我們不知道哪個(gè)狀態(tài)是真正必要的，所以所有狀態(tài)都要計(jì)算出。 并且往往前一個(gè)狀態(tài)都是此時(shí)的局部的最優(yōu)解， 后一個(gè)狀態(tài)則是由這個(gè)局部最優(yōu)解得到的大一點(diǎn)的局部的最優(yōu)解，直到得出目標(biāo)狀態(tài)，即全局最優(yōu)解。因此可以說動(dòng)態(tài)規(guī)劃具有最優(yōu)子結(jié)構(gòu)特性。讓我們?cè)倏纯戳硪坏?/p>

7、經(jīng)典題目。有一個(gè)容積為 n 的袋子，又知道 m個(gè)貨物各自的體積和價(jià)值，要求你將貨物裝到袋子里，使袋子中的貨物價(jià)值和最大。假如袋子的容積為10，現(xiàn)有貨物貨物名ABCDE體積44323價(jià)值56423很顯然，最優(yōu)解為裝 B,C,E ，價(jià)值為 13。這個(gè)例子也說明并不是不斷將價(jià)值最大的貨物放進(jìn)袋子就能得到最優(yōu)解。其他與之相似的各類貪心法均可證明是錯(cuò)誤的。我們的目的是要 “記憶化搜索” 出 x 個(gè)貨物，使它們的體積和小于 n，價(jià)值和盡可能大。與上一道題目相類似，如果在放入一些貨物后， 再放入一個(gè)貨物后能得到最優(yōu)解，那么在放入這個(gè)貨物前，所有貨物無論怎么搭配，也不可能出現(xiàn)體積和小于或等于此時(shí)袋中物品體積和

8、而價(jià)值和大于此時(shí)袋中貨物的價(jià)值和的情況。即無論貨物怎么搭配裝進(jìn)袋子，比此時(shí)的價(jià)值和大，比此時(shí)的體積和小這兩種情況不可能同時(shí)滿足， 這就可以稱作是最優(yōu)子結(jié)構(gòu)了。由此得出狀態(tài)轉(zhuǎn)移方程:設(shè) fi,x表示前 i 個(gè)貨物，用體積等于x 時(shí)的袋子裝能得到的最大價(jià)值（最優(yōu)子結(jié)構(gòu)的體現(xiàn)），wi 表示第 i 個(gè)貨物的體積， vi表示第 i 個(gè)貨物的價(jià)值。fi，j=max(fi-1，j-wi+vi, fi-1,j)（i表示當(dāng)前搜索到第i個(gè)貨物，j表示袋中體積和等于j時(shí)的情況,fi-1,j-wi+vi表示放i貨物時(shí)的最大價(jià)值，fi-1,j表示不放 i 貨物時(shí)的最大價(jià)值）由于 j 的循環(huán)是建立在已經(jīng)確定i 的基礎(chǔ)上，

9、因此 j 的循環(huán)在 i 循環(huán)的內(nèi)部。因此具體實(shí)現(xiàn)方法為： for i ： =1 to n dofor j:=1 to m do beginfi,j:=fi-1,j;if (j>=wi) thenif (fi-1,j-wi+vi>fi,j) thenfi,j:=fi-1,j-wi+vi;end;這里還有些細(xì)節(jié)要處理，比如要預(yù)先將f 數(shù)組清零等等 .寫到這里我想向大家介紹一種減少空間使用的辦法， 若用二維數(shù)組表示狀態(tài)（即狀態(tài)表示為 fi,j 的形式），則我們不妨稱 fi 為一個(gè)狀態(tài)層， 每個(gè)層中含有若干個(gè)狀態(tài)。 細(xì)心觀察不難發(fā)現(xiàn)，這道貨物裝袋題與上面一道數(shù)字三角形的程序?qū)崿F(xiàn)中， 要推得

10、下面一個(gè)狀態(tài)層只需要當(dāng)前這個(gè)狀態(tài)層而不需要當(dāng)前狀態(tài)層之前層的狀態(tài)，即要推得 fi ，只需要 fi-1 。這樣說來求出最優(yōu)解我們只需要兩個(gè)線性數(shù)組， 一個(gè)記錄前面的狀態(tài)層另一個(gè)記錄后面的狀態(tài)層。以貨物裝袋為例，再來看一道全國(guó)信息學(xué)奧林匹克原題：某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。 但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷： 雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以 只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來的高度， 計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈。設(shè) hi表示第 i 個(gè)導(dǎo)

11、彈的高度，再通過預(yù)處理得到導(dǎo)彈數(shù)n按先前的思路進(jìn)行分析，假設(shè)fi表示到第i 個(gè)導(dǎo)彈時(shí)所能擊中的最大導(dǎo)彈數(shù)，但是發(fā)現(xiàn)接下來沒法寫出狀態(tài)轉(zhuǎn)移方程，因?yàn)樵谇骹i時(shí)還有一個(gè)條件是要考慮現(xiàn)在要打的導(dǎo)彈高度不能超過最近打下的一個(gè)導(dǎo)彈的高度。所以顯然我們的狀態(tài)轉(zhuǎn)移方程中要考慮到這一點(diǎn)。因此我們?cè)俅渭僭O(shè)fi表示在打下第i 個(gè)導(dǎo)彈的前提下所能打下的導(dǎo)彈數(shù)最大值。因?yàn)槲覀儗⒋蛳碌趇 個(gè)導(dǎo)彈列為前提，因此也就確定了fi這個(gè)狀態(tài)打的下一個(gè)導(dǎo)彈高度只需要<=hi。而且打下第i 個(gè)導(dǎo)彈數(shù)最大的情況一定是打下前面某個(gè)導(dǎo)彈最大數(shù)情況 , 再打下第i 個(gè)導(dǎo)彈，或者該系統(tǒng)打下的第一個(gè)導(dǎo)彈就是 i （最優(yōu)子結(jié)構(gòu)明顯的體現(xiàn)）

12、。將 f 數(shù)組的所有元素賦值為 1，就是說當(dāng)以該導(dǎo)彈為第一個(gè)打下的導(dǎo)彈時(shí)打下了 1 個(gè)導(dǎo)彈。For i:=2 to n doFor j:=1 to i-1 doif (hi<=hj) thenfi:=max(fi,fj+1)最后要線性掃描一下f 數(shù)組，找到其中的最大值。 （不能簡(jiǎn)單的將fn定為答案，因?yàn)樽顑?yōu)解的情況未必會(huì)打下最后一顆導(dǎo)彈）讓我們?cè)賮砜纯催@道較上面幾道相對(duì)另類的題。最長(zhǎng)公共子串：已知兩個(gè)字符串， 要求求出它們最長(zhǎng)的公共子串的長(zhǎng)度（子串中的每個(gè)字符都能在兩個(gè)原串中找到，而且每個(gè)字符的順序和原串中的順序一致，子串可不連續(xù)） 。例如： abbbdcdcd 和 abcdaabd的最

13、長(zhǎng)公共子串是abcdd, 其長(zhǎng)度為 5。這道題看上去很棘手， 怎么做？最直接的方法，從長(zhǎng)到短枚舉其中一個(gè)字符串的所有子串，在另一個(gè)字符串中一一比對(duì)，直到在另一個(gè)字符串中找到一個(gè)和枚舉的子串相符的子串，那么這個(gè)子串的長(zhǎng)度即為所求答案。假設(shè)兩個(gè)字符串長(zhǎng)度均為 n，枚舉子串時(shí)間復(fù)雜度為 2 的 n 次方，在另一個(gè)字符串中比對(duì)是否有相符子串的復(fù)雜度為 n*n, 所以理論復(fù)雜度為 n*n* （2 的 n 次方），用這種方法只能保證當(dāng) n 小于 20 時(shí)在 1 秒內(nèi)出結(jié)果。很明顯這不是我們想要的效率。讓我們來觀察一下這道題能否用動(dòng)態(tài)規(guī)劃解決， 試著利用最優(yōu)子結(jié)構(gòu)的思想分析后得到：設(shè)兩個(gè)子串分別為串 1 和

14、串 2，若串 1 和串 2 末尾字母相同則所求解即串 1 和串 2 分別去掉末尾字母后的最長(zhǎng)公共子串長(zhǎng)度 +1，否則所求解即串 1 去掉末尾字母后和串 2 的最長(zhǎng)公共子串長(zhǎng)度或串 2 去掉末尾字母后和串 1 的最長(zhǎng)公共子串長(zhǎng)度中較大的一個(gè)。 因?yàn)槿サ裟┪沧帜傅淖址挚梢钥闯梢粋€(gè)新字符串， 這樣就具有了最優(yōu)子結(jié)構(gòu)， 但是因?yàn)檫f歸的思想在程序中實(shí)現(xiàn)起來編寫難度和時(shí)間復(fù)雜度都比遞推大，而且這道題遞推的狀態(tài)轉(zhuǎn)移方法也比較簡(jiǎn)單，因此我們就用遞推來實(shí)現(xiàn)。用數(shù)學(xué)語(yǔ)言表示一下， 不妨設(shè)，a1,a2 分別表示 2 個(gè)字符串，fi,j表示 a1 字符串前 i 個(gè)字符與 a2 字符串前 j 個(gè)字符的最長(zhǎng)公共子串長(zhǎng)

15、度，l1,l2分別表示a1,a2字符串的長(zhǎng)度。動(dòng)歸的實(shí)現(xiàn)方法：For i:=1 to l1 doFor j:=1 to l2 doIf a1i=a2j then fi,j:=fi-1,j-1+1;Else fi,j:=max(fi-1,j,fi,j-1)這樣時(shí)間復(fù)雜度n*n的程序可以接受2 個(gè)長(zhǎng)度為10000 的字符串，幾乎不需要預(yù)處理（fi,j中i,j的下界應(yīng)為 0，數(shù)組清零）編寫起來也明顯比搜索簡(jiǎn)單得多， 看來動(dòng)態(tài)規(guī)劃確實(shí)是程序設(shè)計(jì)者一項(xiàng)利器。讓我們最后看看一道題， Tom的煩惱，希望在看完上面文字后，讀者能嘗試著自主完成此題。Tom是一個(gè)非常有創(chuàng)業(yè)精神的人，由于大學(xué)學(xué)的是汽車制造專業(yè)，所

16、以畢業(yè)后他用有限的資金開了一家汽車零件加工廠，專門為汽車制造商制造零件。由于資金有限，他只能先購(gòu)買一臺(tái)加工機(jī)器。 現(xiàn)在他卻遇到了麻煩，多家汽車制造商需要他加工一些不同零件（由于廠家和零件不同，所以給的加工費(fèi)也不同），而且不同廠家對(duì)于不同零件的加工時(shí)間要求不同（有些加工時(shí)間要求甚至是沖突的， 但開始和結(jié)束時(shí)間相同不算沖突）。Tom當(dāng)然希望能把所有的零件都加工完，以得到更多的加工費(fèi)，但當(dāng)一些零件的加工時(shí)間要求有沖突時(shí)，在某個(gè)時(shí)間內(nèi)他只能選擇某種零件加工（因?yàn)樗挥幸慌_(tái)機(jī)器），為了賺得盡量多的加工費(fèi)，Tom不知如何進(jìn)行取舍。設(shè)有 n 個(gè)廠家，每個(gè)廠家要求的起始時(shí)間si,結(jié)束時(shí)間ei，加工費(fèi) vi。讀者已經(jīng)有思路了嗎？讓我們看看分析。做這道題，切入點(diǎn)就在于找出最優(yōu)子結(jié)構(gòu)。先將廠家的任務(wù)以結(jié)束時(shí)間從小到大排序。設(shè)fx為到達(dá)第x 時(shí)間時(shí)能獲得的最大利潤(rùn) ,i 為第 i 個(gè)廠家的任務(wù)。因?yàn)橐呀?jīng)將任務(wù)以結(jié)束時(shí)間排列，而且每個(gè)