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

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

nn≤1F(n)＝

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

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

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

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

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

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

1具有最優(yōu)子結(jié)構(gòu)性質(zhì)

2具有重疊子問題性質(zhì)

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求解二項式系數(shù) 求解步驟：

1具有最優(yōu)子結(jié)構(gòu)性質(zhì)

2具有重疊子問題性質(zhì)

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

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

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

S0={} S1={，}

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

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

Pascal三角形n011112121313314146415151010516161520156171721353521713.3動態(tài)規(guī)劃法的基本步驟例2求解二項式系數(shù)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求解二項式系數(shù) 求解方法：

2備忘錄法：

備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復求解。3.3動態(tài)規(guī)劃法的基本步驟例2求解二項式系數(shù)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應(yīng)用舉例－0/1背包問題0-1背包問題給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?0-1背包問題是一個特殊的整數(shù)規(guī)劃問題。3.4應(yīng)用舉例－0/1背包問題1最優(yōu)子結(jié)構(gòu)性質(zhì)考查

2建立遞歸方程

3重疊子問題性質(zhì)考查

4求解

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

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

//權(quán)為整數(shù)的迭代法思考：備忘錄法0-1背包問題---權(quán)為整數(shù)的迭代法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