牛X動(dòng)態(tài)規(guī)劃入門篇

1、動(dòng)態(tài)規(guī)劃入門篇ACM暑期集訓(xùn)2009/08/12前言縱觀ACM屆，大到每年的全球總決賽，小到TC的SRM抑或各個(gè)OJ的月賽，我們很輕易的發(fā)現(xiàn)一個(gè)共同的規(guī)律動(dòng)態(tài)規(guī)劃在其中穩(wěn)穩(wěn)的占據(jù)了一個(gè)重要的地位?？梢哉f(shuō)，掌握了動(dòng)態(tài)規(guī)劃，不一定會(huì)成為大牛，但是一只大牛，是肯定精通動(dòng)態(tài)規(guī)劃的。動(dòng)態(tài)規(guī)劃，和分治法一樣，是通過(guò)組合子問(wèn)題的解而解決整個(gè)問(wèn)題的。分治算法是指將問(wèn)題劃分成一些獨(dú)立的子問(wèn)題，遞歸求解各子問(wèn)題，然后合并子問(wèn)題的解而得到原問(wèn)題的解。于此不同，動(dòng)態(tài)規(guī)劃適用于子問(wèn)題不是獨(dú)立的情況，也就是各子問(wèn)題包含公共的子子問(wèn)題。動(dòng)態(tài)規(guī)劃對(duì)每個(gè)子子問(wèn)題只求解一次，將其結(jié)果保存在一張表中，從而避免每次遇到各個(gè)子問(wèn)題時(shí)重

2、新計(jì)算答案。動(dòng)態(tài)規(guī)劃通常應(yīng)用于最優(yōu)化問(wèn)題。此類問(wèn)題可能有許多種可行解。每個(gè)解都有一個(gè)值，而我們希望找到一個(gè)具有最優(yōu)（最大或最?。┲档慕狻７Q這樣的問(wèn)題為該問(wèn)題的“一個(gè)”最優(yōu)解（而不是“確定的”最優(yōu)解），因?yàn)榭赡艽嬖诙鄠€(gè)取最優(yōu)解的值?？偨Y(jié)：自從有了動(dòng)態(tài)規(guī)劃，這個(gè)世界變得好美妙！目錄0.動(dòng)態(tài)規(guī)劃的基本步驟1.一個(gè)例題2.什么時(shí)候需要?jiǎng)討B(tài)規(guī)劃3.最優(yōu)子結(jié)構(gòu)4.重疊子問(wèn)題5.動(dòng)態(tài)規(guī)劃的兩個(gè)重要元素狀態(tài)&狀態(tài)轉(zhuǎn)移方程6.備忘錄介紹7.例題 數(shù)字三角形花束擺放 最大數(shù)字子串積木游戲 Subsquence 炮兵陣地(狀態(tài)壓縮動(dòng)態(tài)規(guī)劃)8.練習(xí) : NOJ 江蘇省賽回放 C D E（三角形演變題） H 0.動(dòng)態(tài)

3、規(guī)劃的基本步驟1）描述最優(yōu)解的結(jié)構(gòu)2）遞歸定義最優(yōu)解的值3）按自底向上的方式計(jì)算最優(yōu)解的值4）由計(jì)算出的結(jié)果構(gòu)造一個(gè)最優(yōu)解第1-3步構(gòu)成問(wèn)題的動(dòng)態(tài)規(guī)劃解的基礎(chǔ)。第四步只要求計(jì)算最優(yōu)解的值時(shí)可以略去。如果的確做了第四步，則有時(shí)要在第三步的計(jì)算中記錄一些附加信息，使構(gòu)造一個(gè)最優(yōu)解變得容易。1.一個(gè)例題例一：裝配線調(diào)度問(wèn)題描述：某汽車工廠有2個(gè)裝配線，每個(gè)裝配線有n 個(gè)裝配站（按順序編號(hào)1n ），兩個(gè)裝配線對(duì)應(yīng)的裝配站執(zhí)行相同的功能，但所用的時(shí)間可能不同。經(jīng)過(guò)第i條流水線（i=1，2）的第j 個(gè)裝配站所花的時(shí)間為Aij。從第i條流水線的第j 個(gè)裝配站移到第j+1個(gè)裝配站的時(shí)間可以忽略，而移到另外一個(gè)

4、流水線的下一個(gè)裝配站則需要一定的時(shí)間Tij。汽車進(jìn)入流水線不需要花時(shí)間，出流水線時(shí)需要花時(shí)間Tin。汽車的裝配需要按順序經(jīng)過(guò)所有裝配站。現(xiàn)在已知裝配時(shí)間Aij 和轉(zhuǎn)移時(shí)間Tij，要求輸出裝配一輛汽車所需要的最短時(shí)間。 方案一：暴力搜索，窮舉所有裝配可能，然后選擇極小。顯然這個(gè)方案是不可行的，因?yàn)槲覀兎治隹芍?，裝配方式共有2N種（將所使用裝配站一內(nèi)的站看做一個(gè)集合，全集是1.N，子集就有2N），這時(shí)時(shí)間復(fù)雜度到達(dá)O（2N），顯然N太大的時(shí)候是一定會(huì)TE的。方案二：動(dòng)態(tài)規(guī)劃。步驟一：描述最優(yōu)解的結(jié)構(gòu)在這里就是通過(guò)工廠最快路線的結(jié)構(gòu)其實(shí)這里就是描述問(wèn)題是否具有一個(gè)最優(yōu)子結(jié)構(gòu)，即可以利用子問(wèn)題的最優(yōu)解

5、構(gòu)造原問(wèn)題的一個(gè)最優(yōu)解。在這道題中，觀察一條通過(guò)S1，j的最快路線，我們發(fā)現(xiàn)，它必然是通過(guò)S1，j-1或S2，j-1中的一個(gè)的最快路線（如果不是最快，則自我矛盾，S1，j就不是最快了）為了解決這個(gè)問(wèn)題，即尋找通過(guò)人一條裝配線上的裝配站J的最快路線，我們解決它的子問(wèn)題，即尋找通過(guò)兩條裝配線上的裝配站J-1的最快路線。所以，對(duì)于這個(gè)問(wèn)題，我們可以求子問(wèn)題的最優(yōu)解，從而得到原問(wèn)題的最優(yōu)解。PS：狀態(tài)，狀態(tài)轉(zhuǎn)移方程的概念將會(huì)在理脫出，后面會(huì)提到，只要找好了狀態(tài)方程（加元等手段），就能輕松使用動(dòng)態(tài)規(guī)劃。步驟二：一個(gè)遞歸的解利用子問(wèn)題的最優(yōu)解來(lái)遞歸定義一個(gè)最優(yōu)解的值。在這個(gè)問(wèn)題中，我們選擇在兩條裝備線上通

6、過(guò)裝配站j的最快路線的問(wèn)題作為子問(wèn)題（j=1，2，3.，n）。令fij表示一個(gè)底盤(pán)從起點(diǎn)到裝配站Si，j的最快可能時(shí)間。我們的最終目標(biāo)是確定底盤(pán)通過(guò)工廠的所有路線的最快時(shí)間，記做f*。f* = min(f1n + x1,f2n + x2)下面的問(wèn)題就是確定f11和f21顯然，不管是從那條線路開(kāi)始裝配的，底盤(pán)肯定是直接到達(dá)裝配站1的，也就是說(shuō)之前是不用計(jì)算轉(zhuǎn)移到裝配站1的時(shí)間的。則f11 = e1 + a1,1 f21 = e2 + a2,1現(xiàn)在計(jì)算fij，顯然簡(jiǎn)單遞推可知：fi1 = ei + ai,1;fij = min(fij-1 + ai,j , fij-1 + ti,j-1 + a2,

7、j)fij的值就是子問(wèn)題的最優(yōu)解的值。注意：這里，我們不需要知道最優(yōu)解到底是什么，我們只需要求出最優(yōu)解是多少即可，所以對(duì)構(gòu)造過(guò)程可以不進(jìn)行跟蹤。現(xiàn)在，寫(xiě)出一個(gè)遞歸算法計(jì)算通過(guò)工廠的最快路線是一件很簡(jiǎn)單的事情了。只需基于以下幾個(gè)公式即可：f* = min(f1n + x1,f2n + x2)fi1 = ei + ai,1;fij = min(fij-1 + ai,j , fij-1 + ti,j-1 + a2,j)現(xiàn)在我們來(lái)看這種算法的時(shí)間復(fù)雜度，發(fā)現(xiàn)它有一個(gè)問(wèn)題:它的執(zhí)行時(shí)間是關(guān)于n的指數(shù)形式即O（2n），這是一個(gè)時(shí)間復(fù)雜度很高的算法。我們來(lái)考慮是否能進(jìn)一步提高它的效率?，F(xiàn)在考慮這樣一種方式F

8、ASTEST-WAY(a , t , e , x , n)f11 = e1+a1,1f21 = e2 + a2,1 /這兩行計(jì)算f11和f21的值For j=2 to n /這個(gè)循環(huán)用來(lái)計(jì)算fij的值 do if f1j-1+a1,j=f2j-1+t2,j-1+a1,j then f1j = f1j-1+a1,j else f1j=f2j-1+t2,j-1+a2,j if f2j-1+a2,j=f1j-1+t1,j-1+a2,j then f2j = f2j-1+a2,jif f1n+x1= 0; -i ) /從最下層開(kāi)始，計(jì)算每個(gè)x，y位 /置的元素到 最后一行的最小值for ( j = 0

9、; j = i; +j ) /計(jì)算每一行的每一個(gè)數(shù)字tmp = soui + 1j;if ( soui + 1j + 1 tmp ) /*j在變化，j每循環(huán)完次都得到一個(gè)這一行到最底行最小的位置，同時(shí)也記錄了每個(gè)位置到最底行的值；這里的if是在找每個(gè)位置的下兩步路線中較小的一個(gè)*/tmp = soui + 1j + 1;souij += tmp;printf( %dn, sou00 );35例題二：花束擺放問(wèn)題描述 現(xiàn)在有F束不同品種的花束，同時(shí)有至少同樣數(shù)量的花瓶被按順序擺成一行，其位置固定于架子上，并從1至V按從左到右順序編號(hào)，V是花瓶的數(shù)目(FV)?；ㄊ梢砸苿?dòng)，并且每束花用1至F的整數(shù)

10、唯一標(biāo)識(shí)。標(biāo)識(shí)花束的整數(shù)決定了花束在花瓶中排列的順序，如果ij，花束i必須放在花束j左邊的花瓶中。每個(gè)花瓶只能放一束花。如果花瓶的數(shù)目大于花束的數(shù)目，則多余的花瓶空置。 每一個(gè)花瓶都具有各自的特點(diǎn)。因此，當(dāng)各個(gè)花瓶中放入不同的花束時(shí)，會(huì)產(chǎn)生不同的美學(xué)效果，并以一美學(xué)值(一個(gè)整數(shù))來(lái)表示，空置花瓶的美學(xué)值為零。為取得最佳美學(xué)效果，必須在保持花束順序的前提下，使花束的擺放取得最大的美學(xué)值。請(qǐng)求出具有最大美學(xué)值的一種擺放方式。372解題思路 狀態(tài)表示法一： 設(shè)A(i,j)表示第i種花束擺在第j個(gè)花瓶中獲得的美學(xué)值。S(i,k)表示第i種花束擺在第k個(gè)花瓶中時(shí)(這里ki)，前i種花束能夠獲得的最大美學(xué)

11、值(之和)。這樣，原問(wèn)題的最優(yōu)值可以通過(guò)計(jì)算maxS(F,k)FkV獲得。 下面要分析一下這種狀態(tài)表示法描述問(wèn)題的方式是否具備了用動(dòng)態(tài)規(guī)劃求解的基本要素。 38 最優(yōu)子結(jié)構(gòu)性質(zhì)：對(duì)滿足FkV的k，設(shè)T(F,k)是達(dá)到最優(yōu)值S(F,k)的一種最佳擺放方式，其中，第F-1種花束擺在第j個(gè)花瓶中(j1每走一步，計(jì)算出了所有i的花束擺放在所有可能的位置之后的所有值。最后，遞推出了s(F,*)的值取最大既得到結(jié)果。S(1,k)=A(1,k)第i-1個(gè)花擺在那里之后，下一步怎么擺，只跟現(xiàn)在花在哪里有關(guān)，而與前面的擺放順序無(wú)關(guān)，無(wú)后效性。大家用心想一下，問(wèn)題其實(shí)還是像裝配線一樣，被分解成了有限個(gè)分支的最大值

12、問(wèn)題。切記，使用DP的時(shí)候，眼光不要一直盯著最后的最優(yōu)，一步一步看，只要你現(xiàn)在最優(yōu)，并且無(wú)后效性，就可以DP下去。39 在計(jì)算S(i,k-1)時(shí)，已經(jīng)計(jì)算出了S(i-1,j)，i-1jk-2及其 maxS(i-1,j)i-1jk-2 。因此，計(jì)算S(i,k)時(shí)，只要將S(i-1,k-1)與max S(i-1,j)i-1jk-2 進(jìn)行比較即可求得,即子問(wèn)題重疊性質(zhì)。這樣做可以大大減少計(jì)算量。即不用每次都去全部比較，求最大值。 事實(shí)上，還可以有更直接的方法。 狀態(tài)表示法二： 設(shè)Si,k表示第i種花束擺在第k個(gè)之前(包括第k個(gè))的任意某個(gè)花瓶中，前i種花束能夠獲得的最大美學(xué)值(之和)。這樣，原問(wèn)題的

13、最優(yōu)值即為SF,V。這比前一個(gè)表示法更直接。 40 容易驗(yàn)證，計(jì)算SF,V的問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 其遞歸方程為： Si,k=maxSi-1,k-1+A(i,k)，Si,k-1，(i1，ki); /很精妙，注意理解 初始條件為：S1,1=A1,1; S1,k=maxA(1,k),S1,k-1，(k1);Si,i=Si-1,i-1+A(i,i)， (i1) 41算法設(shè)計(jì)(狀態(tài)表示法二) 算法的過(guò)程如下： s00 = a00; out00 = true;for ( j = 1; j a0j ? s0j - 1 :a0j;out0j = ( s0j != s0j - 1 );for ( i = 1

14、; i f & i ?= si - 1j - 1 + aij;outij = ( sij != sij - 1 );42sij = si - 1j - 1 + aij; outij = true;if ( i ?= sij - 1; outij = ( sij != sij - 1 );43例題三：最大數(shù)字子串NKOJ 1760 最大數(shù)字子串:問(wèn)題描述：輸入n(1=n0，如果后邊是正數(shù)的話，完全可以加上這3個(gè)數(shù)（比如后邊的5）-1 2 8 5 10 ？相同處理： -1 2 8 5 10 3 17 12？后面是-15，加上12（前面的子串能形成的最大和）也小于0，所以此處應(yīng)該斷開(kāi)了！記錄-15！

15、最后-1 2 8 5 10 3 17 12 -15 1 9 5 1447！還有一點(diǎn)，如果輸入全為非正數(shù)的話，那么最大子串就是最大的那個(gè)數(shù)了！48偽代碼：輸入數(shù)組ai,用數(shù)組si記錄當(dāng)前最大子串和,num記錄最大值。for(i=0;in;i+) 輸入ai; s0=a0; num記錄當(dāng)前最大的數(shù)； if(num=0) 最大就為num!for(i=1;in;i+)if(si-1 0 | (si-1 + ai) = 0) si = ai;elsesi = si-1 + ai;num = (num si) ? si:num;/*條件運(yùn)算符 （numbi true則bi,false則num）*/49例題四

16、：積木游戲LRJ的書(shū)，P119。這道題和我們程序設(shè)計(jì)大賽的時(shí)候的第四題（是不是第四？記不清了。）猩猩吃香蕉那題有異曲同工之妙。大家明白這題之后可以回憶一下我們的比賽。例題五： Subsequence 給定一個(gè)數(shù)串和一個(gè)數(shù)S，在數(shù)串中找出大于等于S的一個(gè)連續(xù)子列！且該子列是滿足上述條件的最短子列！數(shù)串?dāng)?shù)字個(gè)數(shù)N：10N100000,每個(gè)數(shù)小于10000。比如： 10 15 5 1 3 5 10 7 4 9 2 8 最短為2； 5 11 1 2 3 4 5 最短為3。該題簡(jiǎn)單分析：題意知所有數(shù)全為正數(shù) A sequence of N positive integers (10 N 100 000)

17、，每新增一個(gè)數(shù)，若前面的數(shù)不足S,加上此數(shù)，然后與S比較！小于S可不管！52大于S：假設(shè)此時(shí)新增項(xiàng)ai,設(shè)當(dāng)前和為sumi,用另一數(shù)組記錄當(dāng)前長(zhǎng)度位置長(zhǎng)度lengthi。那么現(xiàn)在在構(gòu)成sumi的數(shù)的最前端i-lengthi+1處，有可能出現(xiàn)多余的項(xiàng)，哪怕刪除它們也滿足剩下的數(shù)的和sumi(長(zhǎng)度已更改為新的lengthi! )逐項(xiàng)除之即可！lengthi記錄的是到達(dá)每個(gè)位置的時(shí)候，這個(gè)串現(xiàn)在有多長(zhǎng)。53尋找最短子列：Length全為0,沒(méi)有最短子列!否則為大于0的最小值。if(b1n-1=0) num=0;else num=n; for(i=0;i0) num=(b1inum)?b1i:num;

18、 54例題六：炮兵陣地POJ 1185經(jīng)典的DP問(wèn)題題意描述：司令部的將軍們打算在N*M的網(wǎng)格地圖上部署他們的炮兵部隊(duì)。一個(gè)N*M的地圖由N行M列組成，地圖的每一格可能是山地（用H 表示），也可能是平原（用P表示），如下圖。在每一格平原地形上最多可以布置一支炮兵部隊(duì)（山地上不能夠部署炮兵部隊(duì)）；一支炮兵部隊(duì)在地圖上的攻擊范圍如圖中黑色區(qū)域所示：如果在地圖中的灰色所標(biāo)識(shí)的平原上部署一支炮兵部隊(duì)，則圖中的黑色的網(wǎng)格表示它能夠攻擊到的區(qū)域：沿橫向左右各兩格，沿縱向上下各兩格。圖上其它白色網(wǎng)格均攻擊不到。從圖上可見(jiàn)炮兵的攻擊范圍不受地形的影響。 現(xiàn)在，將軍們規(guī)劃如何部署炮兵部隊(duì)，在防止誤傷的前提下（保證任何兩支