《算法設計與分析》第三章-動態(tài)規(guī)劃課件

第3章動態(tài)規(guī)劃（Dynamic-Programming）3.1動態(tài)規(guī)劃法的基本思想3.2動態(tài)規(guī)劃法的適用條件3.3動態(tài)規(guī)劃法的基本步驟3.4應用舉例－0/1背包問題3.1動態(tài)規(guī)劃法的基本思想為求解給定問題，有一系列子問題需要解答。對這些子問題按照某種方式仔細設計，使得其后的每一個子問題都可以通過上面已經求出的一個或多個子問題的合并而獲得其解。3.1動態(tài)規(guī)劃法的基本思想動態(tài)規(guī)劃法與分治法的異同：與分治法類似，動態(tài)規(guī)劃法也是對問題進行遞歸分解。而當遞歸分解得到的子問題不互相獨立時，用分治法求解，則有些子問題被重復計算了許多次。而動態(tài)規(guī)劃法通過保存已解決的子問題的解，在需要時再找出已求得的解，可以避免大量重復計算。3.2動態(tài)規(guī)劃法的適用條件動態(tài)規(guī)劃法解所能解決的問題一般具有以下兩個基本因素：一、最優(yōu)子結構性質

當問題的最優(yōu)解包含著其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結構性質。二、重疊子問題性質 遞歸算法求解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質稱為子問題的重疊性質。其它同分治法3.2動態(tài)規(guī)劃法的適用條件一、最優(yōu)子結構性質 當問題的最優(yōu)解包含著其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結構性質。例1：Fibonacci數問題

nn≤1F(n)＝

F(n-1)＋F(n-2)n>13.2動態(tài)規(guī)劃法的適用條件一、最優(yōu)子結構性質 當問題的最優(yōu)解包含著其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結構性質。例2：求解二項式系數11m=0n=m其它＝3.2動態(tài)規(guī)劃法的適用條件一、最優(yōu)子結構性質

在分析問題的最優(yōu)子結構性質時，所用的方法具有普遍性：首先假設由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的，然后再設法說明在這個假設下可構造出比原問題最優(yōu)解更好的解，從而導致矛盾。3.2動態(tài)規(guī)劃法的適用條件一、最優(yōu)子結構性質

例3最短路徑問題 設G是有向圖，若G中從頂點i到頂點j有路徑存在，找出最短的一條。下面證明最短路徑問題具有最優(yōu)子結構性質3.2動態(tài)規(guī)劃法的適用條件一、最優(yōu)子結構性質證明：設i,i1,i2,…,ik,j是從i到j的一條最短路徑。從初始頂點i開始，設從i到下一頂點i1的判定已經做出。接下去，問題就轉化為用i1替代i，重復原來的問題，找出一條從i1到j的路徑。顯然，i1,i2,…,ik,j一定構成了從從i1到j的最短路徑（與原問題相同的最優(yōu)子序列）

3.2動態(tài)規(guī)劃法的適用條件一、最優(yōu)子結構性質證明： 若不然，設i1,r1,r2,…,rp,j是一條從i1

到j的最短路徑，則i,i1,r1,r2,…,rp,j將是一條從i到j的路徑且比路徑i,i1,i2,…,ik,j要短，得出矛盾。所以，最短路徑問題具有最優(yōu)子結構性質。3.2動態(tài)規(guī)劃法的適用條件一、最優(yōu)子結構性質

利用問題的最優(yōu)子結構性質，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構造出整個問題的最優(yōu)解。最優(yōu)子結構是問題能用動態(tài)規(guī)劃算法求解的前提。3.2動態(tài)規(guī)劃法的適用條件二、重疊子問題性質 遞歸算法求解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質稱為子問題的重疊性質。3.2動態(tài)規(guī)劃法的適用條件二、重疊子問題性質 例1：Fibonacci數問題的遞歸樹Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)T(n)=O(Fib(n))3.2動態(tài)規(guī)劃法的適用條件二、重疊子問題性質 例2：求解二項式系數的遞歸樹T(n)=O()3.3動態(tài)規(guī)劃法的基本步驟找出最優(yōu)解的性質，并刻劃其結構特征。－－考察是否適合采用動態(tài)規(guī)劃法。遞歸地定義最優(yōu)值(建立遞歸式或動態(tài)規(guī)劃方程)。以自底向上迭代的方式（或以自頂向下的備忘錄方法）計算出最優(yōu)值；根據計算最優(yōu)值時得到的信息，構造最優(yōu)解。3.3動態(tài)規(guī)劃法的基本步驟例1Fibonacci數問題 求解步驟：

1具有最優(yōu)子結構性質

2具有重疊子問題性質

3建立遞歸式或動態(tài)規(guī)劃方程

4求解值。3.3動態(tài)規(guī)劃法的基本步驟intFib(intn){f1=f2=0;for(f=1,i=0;i<=n;i++){ f2=f1;f1=f;f=f1+f2;}returnf;}3.3動態(tài)規(guī)劃法的基本步驟例2求解二項式系數 求解步驟：

1具有最優(yōu)子結構性質

2具有重疊子問題性質

3建立遞歸式或動態(tài)規(guī)劃方程

4求解。3.3動態(tài)規(guī)劃法的基本步驟例2求解二項式系數 求解方法：

1動態(tài)規(guī)劃法：計算如下序列：

S0={} S1={，}

S2={，，}Sn={，，，…,}3.3動態(tài)規(guī)劃法的基本步驟例2求解二項式系數

1動態(tài)規(guī)劃法：

Pascal三角形n011112121313314146415151010516161520156171721353521713.3動態(tài)規(guī)劃法的基本步驟例2求解二項式系數intBinom（intn,intm）{ intb[MAXSIZE]; b[0]=1; for(i=1;i<=n;i++){ b[i]=1 for(j=i-1;j>0;j++) b[j]=b[j]+b[j-1]; } returnb[m];}3.3動態(tài)規(guī)劃法的基本步驟例2求解二項式系數 求解方法：

2備忘錄法：

備忘錄方法的控制結構與直接遞歸方法的控制結構相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復求解。3.3動態(tài)規(guī)劃法的基本步驟例2求解二項式系數2備忘錄法：

intBinom（intn,intm）{ if(n==m||m==0){filltable(n,m,0);return1;}else{ if(!lookupTable(n-1,m,t1)){ t1=Binom(n-1,m);filltable(n-1,m,t1); } if(!lookupTable(n-1,m-1,t2)){ t2=Binom(n-1,m-1);filltable(n-1,m-1,t2); }returnt1+t2;}}3.4應用舉例－0/1背包問題0-1背包問題給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?0-1背包問題是一個特殊的整數規(guī)劃問題。3.4應用舉例－0/1背包問題1最優(yōu)子結構性質考查

2建立遞歸方程

3重疊子問題性質考查

4求解

0-1背包問題設所給0-1背包問題的子問題的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結構性質，可以建立計算m(i，j)的遞歸式如下。3.4應用舉例－0/1背包問題求解：

1動態(tài)規(guī)劃法

//權為整數的迭代法思考：備忘錄法0-1背包問題---權為整數的迭代法voidKnapSack(intv[],intw[],intc,intn,intm[][])//求m[][]{intjMax=min(w[n]-1,c);for(j=0;j<=jMax;j++)//m(n,j)=00=<j<w[n] m[n][j]=0;for(j=w[n];j<=c;j++)//m(n,j)=v[n]j>=w[n] m[n][j]=v[n];for(i=n-1;i>1;i--){ intjMax=min(w[i]-1,c); for(j=0;j<=jMax;j++)//m(i,j)=m(i+1,j)0=<j<w[i] m[i][j]=m[i+1][j]; for(j=w[i];j<=c;j++)//m(n,j)=v[n]j>=w[n] m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1]) m[1][c