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

1、程序設(shè)計(jì)實(shí)踐程序設(shè)計(jì)方法之動(dòng)態(tài)規(guī)劃1任務(wù):摘桃子（1104)長滿桃子的樹很大，共有n層（最高層為第1層），第i層有i條樹枝，樹的形狀呈一個(gè)三角形（如圖）圖中的點(diǎn)表示樹枝，每個(gè)點(diǎn)上方的數(shù)字表示這條樹枝最多能摘到的桃子數(shù)在摘得某枝條的桃子之后，小猴子只能選擇往左上方爬或者是往右上方爬例如：摘了有6個(gè)桃子的樹枝之后只能摘有2個(gè)桃子的樹枝或是有3個(gè)桃子的樹枝），然后繼續(xù)摘桃子。小猴子現(xiàn)在想要從最低層開始一直爬到樹頂（也就是最上面的那個(gè)枝條），摘盡可能多的桃子。請你編程幫他解決這個(gè)問題。1234652解題思路題目似曾相識(shí)？滑雪、迷宮可以用遞歸回溯方法解決建議自寫遞歸回溯的代碼3換一種思路從最低一層爬到最

2、頂點(diǎn)，經(jīng)過的路徑上數(shù)字之和最大A:1B:2C:3D:4E:6F:5第1階段第2階段第0階段4思路先看第2階段，到達(dá)頂點(diǎn)有2條路BA，可以摘到1個(gè)桃子，則經(jīng)過B點(diǎn)到頂點(diǎn)最多摘得桃子數(shù)是：到達(dá)B點(diǎn)手中最多的桃子數(shù)+1CA，可以摘到1個(gè)桃子，則經(jīng)過C點(diǎn)到頂點(diǎn)最多摘得桃子數(shù)是：到達(dá)C點(diǎn)手中最多的桃子數(shù)+1從上述兩條路徑中選擇一條最優(yōu)的令令P(X)表示從底層到X點(diǎn)可以摘到最多桃子數(shù)目，包含X點(diǎn)可以摘到的桃子數(shù)目則：P(A) = maxP(B)，P(C)+15思路（續(xù)）而第1階段的P(B) = maxP(D), P(E)+2P(C) = maxP(E), P(F)+3按照題意，P(D),P(E),P(F)

3、分別初始化為4, 6, 5上述遞推公式說明，要求P(A)需要先求出階段1的P(B)和P(C)，而要得到P(B)和P(C)，需要知道P(D),P(E),P(F)6思路（續(xù)）顯然，根據(jù)前面的遞推過程求解，需要倒過來，從P(D),P(E),P(F)出發(fā)，先求出第1階段的P(B)和P(C)，最后得到P(A)。7數(shù)據(jù)結(jié)構(gòu)將長滿桃子的樹用二維數(shù)組保存數(shù)組行上存放桃樹上一層中每個(gè)樹枝上桃子數(shù)將節(jié)點(diǎn)上桃子數(shù)目存放在數(shù)組中只使用數(shù)組中對角線及下部分A:1B:2C:9D:7E:6F:5G:2H:3J:4I:68問題分析從二維數(shù)組最下面一行開始向上一行沿圖中的直線前進(jìn)，走到左上角的格子停止。行走路徑上經(jīng)過的格子中的

4、數(shù)字之和是猴子爬到樹頂能拿到桃子的數(shù)目，我們定義為路徑長度。原問題轉(zhuǎn)化為求所有路徑中路徑長度的最大值。9問題分析（續(xù)）按照前面的思路，最長路徑的長度是：P(A) = maxP(B), P(C)+1P(B) = maxP(D), P(E)+2P(C) = maxP(E), P(F)+9P(D) = maxP(G), P(H)+7P(E) = maxP(H), P(I)+6P(F) = maxP(I), P(J)+5P(G) = 2, P(H) = 3, P(I) = 6, P(J) = 4將底層到每個(gè)點(diǎn)的最長路徑P也存放在二維數(shù)組中ABCDEFGHJIyx10數(shù)據(jù)結(jié)構(gòu)(續(xù))#define MAX

5、LAYER 3int peachtreeMAXLAYERMAXLAYER = 1, -1, -1, -1, 2, 9, -1, -1, 7, 6, 5, -1,2, 3, 6, 4 ;int PMAXLAYERMAXLAYER原問題轉(zhuǎn)化為即求P03Px y = maxPx y-1, Px+1y-1+peachtreexyy 0, x + y = MAXLAYPER注意邊界條件，Px 0 = peachtreex011最多能摘到22個(gè)桃子，路徑如上圖紅色箭頭所示yx12參考程序如下#include #include #include using namespace std;#define MAX

6、LAYER 110int maxnum(int x, int y)/返回2個(gè)整數(shù)中的大者if (x y)return x;elsereturn y;13參考程序（續(xù)）int main()int peachtreeMAXLAYERMAXLAYER;int PMAXLAYERMAXLAYER;int i, j, k, n;/讀入數(shù)據(jù)cin n;k = 1;/當(dāng)前這層的節(jié)點(diǎn)數(shù)目for (i = 0; i n; i+)/ n-i層的的節(jié)點(diǎn)for (j = 0; j peachtreejn-i-1;k+;14參考程序（續(xù)）/初始化Px0for (i = 0; i n; i+)Pi0 = peachtre

7、ei0;/遞推過程Pxy = maxPxy-1, Px+1y-1+peachtreexyfor (j = 1; j n; j+)/ i是行號，j是列號for (i = 0 ; i + j n; i+)Pij = maxnum(Pij-1, Pi+1j-1)+peachtreeij;cout P0n-1 endl;return 0;15動(dòng)態(tài)規(guī)劃階段狀態(tài)決策狀態(tài)轉(zhuǎn)移方程16動(dòng)態(tài)規(guī)劃的幾個(gè)概念:階段：據(jù)空間順序或時(shí)間順序?qū)栴}的求解劃分階段。狀態(tài)：描述事物的性質(zhì)，不同事物有不同的性質(zhì)，因而用不同的狀態(tài)來刻畫。對問題的求解狀態(tài)的描述是分階段的。決策：根據(jù)題意要求，對每個(gè)階段所做出的某種選擇性操作。狀態(tài)

8、轉(zhuǎn)移方程：用數(shù)學(xué)公式描述與階段相關(guān)的狀態(tài)間的演變規(guī)律。17動(dòng)態(tài)規(guī)劃相關(guān)概念動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，是解決多階段決策過程最優(yōu)化的一種方法所謂多階段決策過程，是將所研究的過程劃分為若干個(gè)相互聯(lián)系的階段，在求解時(shí)，對每一個(gè)階段都要做出決策，前一個(gè)決策確定以后，常常會(huì)影響下一個(gè)階段的決策。18動(dòng)態(tài)規(guī)劃相關(guān)概念（續(xù)）動(dòng)態(tài)規(guī)劃所依據(jù)的是“最優(yōu)性原理”“最優(yōu)性原理”可陳述為：不論初始狀態(tài)和第一步?jīng)Q策是什么，余下的決策相對于前一次決策所產(chǎn)生的新狀態(tài)，構(gòu)成一個(gè)最優(yōu)決策序列。最優(yōu)決策序列的子序列，一定是局部最優(yōu)決策子序列。包含有非局部最優(yōu)的決策子序列，一定不是最優(yōu)決策序列。19動(dòng)態(tài)規(guī)劃相關(guān)概念（續(xù)）動(dòng)態(tài)規(guī)

9、劃的指導(dǎo)思想是：在做每一步?jīng)Q策時(shí)，列出各種可能的局部解，之后依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解的局部解。在每一步都經(jīng)過篩選，以每一步都是最優(yōu)的來保證全局是最優(yōu)的。篩選相當(dāng)于最大限度地有效剪枝（從搜索角度看），效率會(huì)十分高。但它又不同于貪心法。貪心法只能做到局部最優(yōu)，不能保證全局最優(yōu)，因?yàn)橛行﹩栴}不符合最優(yōu)性原理。20動(dòng)態(tài)規(guī)劃與貪心法區(qū)別貪心法產(chǎn)生一個(gè)按貪心策略形成的判定序列，該序列不保證解是全局最優(yōu)的。動(dòng)態(tài)規(guī)劃會(huì)產(chǎn)生許多判定序列，再按最優(yōu)性原理對這些序列加以篩選，去除那些非局部最優(yōu)的子序列。21 舉例說明動(dòng)態(tài)規(guī)劃思路 問題： 在數(shù)字串中插入若干乘號使 總的乘積最大22 * * * s

10、 3 2 1 5 1 2 5 0 1 2 3 4 5 6 請插入3個(gè)乘號使乘積最大 32*15*12*5=28800 3*215*12*5=38700 321*51*2*5=16371023 解題思路 定義 : 從 l 到 r 加入 k 個(gè)乘號的最大乘積值 * p( l , r , k ) l l+1 l+2 . . . q q+1 q+2 . . . r d ( l , q ) p( q+1,r,k-1 ) d ( l , q )= slsl+1sq 24 p( l,r,k )=max d( l, q ) * p( q+1, r ,k-1 ) q=l,l+1,r-k q=l=0 3 2 1

11、5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,0)=3 p( q+1,r,k-1 )=p( 1,6,2 ) (p( 0,6,3)|q=0) = 3 * p( 1,6,2 ) 25 q=l+1=1 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,1)=32 p( q+1,r,k-1 )=p( 2,6,2 ) (p( 0,6,3)|q=1) = 32 * p( 2,6,2 )26 q=l+2=2 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,2)=321 p( q+1,r,k-1 )=p( 3,6,2 ) (p

12、( 0,6,3)|q=2) = 321 * p( 3,6,2 )27 q=l+3=3 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,3)=3215 p( q+1,r,k-1 )=p( 4,6,2 ) ( p( 0,6,3)|q=3) = 3215 * p( 4,6,2 )28p( 0,6,3)= max 3 * p( 1,6,2 ) , / q=0 32 * p( 2,6,2 ) , / q=1 321* p( 3,6,2 ) , / q=2 3215 * p( 4,6,2 ) / q=3 29p( 1,6,2 ) 2 1 5 1 2 5 2 * p(2,6,

13、1 ) 1 2 3 4 5 6 2 1 5 1 2 5 21 * p(3,6,1) 1 2 3 4 5 6 2 1 5 1 2 5 215 * p(4,6,1) 1 2 3 4 5 6 2 1 5 1 2 5 2151 * p(5,6,1) 1 2 3 4 5 6 30 p( 2,6,1 ) 1 5 1 2 5 1* 5125 2 3 4 5 6 1 5 1 2 5 15 * 125 2 3 4 5 6 1 5 1 2 5 15 1* 25 2 3 4 5 6 1 5 1 2 5 1512 *5 2 3 4 5 6 31 p(2,6,1) = max 1 * 5125 , 15 * 125 ,

14、 151 * 25 , 1512 * 5 = 7560 32 p( 3,6,1 ) 5 1 2 5 5 * 125 3 4 5 6 5 1 2 5 51 * 25 3 4 5 6 5 1 2 5 5 12* 5 3 4 5 6 p( 3,6,1 )=max5*125, 51*25, 512*5 = 2560 33 p( 4,6,1 ) 1 2 5 1 * 25 4 5 6 1 2 5 12 * 5 4 5 6 p( 4,6,1 ) = max 1 * 25, 12 * 5 = 6034 p( 5,6,1 ) 2 5 2 * 5 5 6 p(5,6,1) = 1035 p( 1,6,2 )= m

15、ax 2 * p( 2,6,1 ) , 21 * p( 3,6,1) , 215 * p( 4,6,1) , 2151 * p( 5,6,1) =max2*7560,21*2560,215*60,2151*10 = 53760 36 p( 2,6,2 ) 1 5 1 2 5 1* p(3,6,1 ) 2 3 4 5 6 1 5 1 2 5 15 * p(4,6,1) 2 3 4 5 6 1 5 1 2 5 151 * p(5,6,1) 2 3 4 5 6 p( 2,6,2 )= 1 * 2560, 15 * 60, 151 * 10 = 256037 p( 3,6,2 ) 5 1 2 5 5

16、* p(4,6,1 ) 3 4 5 6 5 1 2 5 51 * p(5,6,1) 3 4 5 6 p( 3,6,2 ) = 5 * 60 , 51 * 10 = 510 38 p( 4,6,2 ) 1 2 5 1 * 2 * 5 4 5 6 p( 4,6,2 ) = 1039 p( 4,6,2 ) 1 2 5 1* p(5,6,1 ) 4 5 6 p(5,6,1) = 2 * 5 = 10 p(4,6,2) = 1 * p(5,6,1) = 10 40p( 0,6,3)= max 3 * p( 1,6,2 ) , / q=0 32 * p( 2,6,2 ) , / q=1 321* p( 3

17、,6,2 ) , / q=2 3215 * p( 4,6,2 ) / q=3 p( 1,6,2 ) = 53760 p( 2,6,2 ) = 2560 p( 3,6,2 ) = 510 p( 4,6,2 ) = 6041p( 0,6,3)= max 3 * p( 1,6,2 ) , / q=0 32 * p( 2,6,2 ) , / q=1 321* p( 3,6,2 ) , / q=2 3215 * p( 4,6,2 ) / q=3 p( 1,6,2 ) = 53760 p( 2,6,2 ) = 2560 p( 3,6,2 ) = 510 p( 4,6,2 ) = 6042p( 0,6,3)

18、= max 3 * 53760 , 32 * 2560 , 321* 510, 3215 * 60 = 163710 p( 1,6,2 ) = 53760 p( 2,6,2 ) = 2560 p( 3,6,2 ) = 510 p( 4,6,2 ) = 6043 P(l,r,k) k=0 k !=0 d(l,r) q=l q=l-k q=l+1 p(l+1,r,k-1) 求max值 d(l,l)* p(l+1,r,k-1) d(l,r-k)* p(r-k+1,r,k-1) p(r-k+1,r,k-1) p(l+2,r,k-1) d(l,l+1)* p(l+2,r,k-1) 44 dij j 0

19、1 2 3 4 5 6 i 0 3 32 321 3215 32151 321512 3215125 1 2 21 215 2151 21512 215125 2 1 15 151 1512 15125 3 5 51 512 5125 4 1 12 125 5 2 25 6 545 怎樣計(jì)算這張表 ? di6, i=0,1,2,3,4,5,6. d06=s = 3215125 d16= 215125 = 3215125 % 1000000 = s % 1000000 s1=1000000 = s % s1 s1= s1/10 d26= d16 % s146 s1=1000000; d06=s;

20、 for( i=1; i=0; j- ) for( i=0; i= j; i + ) dij=dij+1/10; 48 參 考 程 序 #include / 預(yù)編譯命令 #include / 預(yù)編譯命令 using namespace std; / 使用名字空間 const int S=3215125; /定義常整數(shù) int d77; /定義二維數(shù)組 49 int P( int l, int r, int k ) /計(jì)算P函數(shù)值 if ( k=0) return dlr; int x, ans=0; for( int q=1; qans ) ans=x; return ans; 50int m

21、ain() memset( d,0,sizeof(d); int s1,I,j; s1=1000000; d06=s; for( i=1; i=0; j- ) for( i=0; i= j; i + ) dij=dij+1/10; coutP( 0,6,3 )3 k=1 m=356 s(m,n)=min2*s(m,n-k)+s(m-1,k) k 1. s(m,n)=1, m=2, n=1 2. s(m,n)=1, m=3, n=1 3. s(m,n)=3, m=3, n=2 4. s(m,n)=3, m=4, n=2 5. s(m,n)=7, m=3, n=3 6. s(m,n)=5, m=4

22、, n=3 57 1 2 4 5 from temp1 temp2 to 358 分析 ： k值的選擇是關(guān)鍵1. 問題的解決有若干個(gè)階段，是一個(gè)多步 決策的過程。 2. 對于階段 b 而言，階段 a 的解決與之無關(guān), 相關(guān)的只是階段 a 解決后的狀態(tài)。問題的 階段劃分滿足無后效性的要求。3. 問題的最優(yōu)策略是各階段最優(yōu)子策略的組 合，若問題 h 取得最優(yōu)解，則其在階段a, b, c 上也必然取得最優(yōu)解。問題滿足動(dòng)態(tài) 規(guī)劃的最優(yōu)性原理。59 動(dòng)態(tài)規(guī)劃一般式 min s(m,n-k)+s(m-1,k)+s(m,n-k) k k=1,2,n m3 n1 s(m,n)= k=1 m=3 n1 1 m=

23、2 n=1 0 其它 60 m=3, n=2 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(3,2)=min 2*s(3,2-1)+s(3-1,1) =min 2*s(3,1)+s(2,1) =min 2*1 + 1 = 361 m=3, n=3 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(3,3)=min 2*s(3,3-1)+s(3-1,1) =min 2*s(3,2)+s(2,1) =min 2*3 + 1 = 762 m=3, n=4 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(3,4)=min 2*s(3,4-1)+s(3-1,1) =min 2*s(3,3)+s(2,1) =min 2*7 + 1 = 1563 m=3, n=5 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k)