DP動態(tài)規(guī)劃ACM課件

1、DP動態(tài)規(guī)劃ACM課件 DP動態(tài)規(guī)劃ACM課件 DP是在20世紀50年代由一位卓越的美國數(shù)學 家Richcard Bellman發(fā)明的。它作為一種重 要的工具在應用數(shù)學中被廣泛的應用。它不 僅可以解決特定類型的優(yōu)化問題，還可以作 為一種通用的算法設計技術來使用。 DP動態(tài)規(guī)劃ACM課件 DP的實質(zhì) 利用問題的所具有的重疊子問題的性質(zhì)進行 記憶化求解。（用空間換時間） DP動態(tài)規(guī)劃ACM課件 求Fibonacci數(shù)： f(n) = f(n-1) + f(n-2) n2 f(1)=f(2)=1 DP動態(tài)規(guī)劃ACM課件 常規(guī)遞歸 int Non_DP(int n) if (n=1 | n=2) re

2、turn 1; else return Non_DP(n-1) + Non_DP(n-2); 指數(shù)級時間復雜度，無法忍受 DP動態(tài)規(guī)劃ACM課件 兩種實現(xiàn)方式 自底向上(bottom up) int DP_Bottom_Up(int n) memo1 = memo2 = 1; for (int i=3; i=n; i+) memoi = memoi-1 + memoi-2; return memon; DP動態(tài)規(guī)劃ACM課件 自頂向下（top down） int DP_Top_Down(int n) if (n = 1 | n = 2) return 1; if (memon != 0) re

3、turn memon; memon = DP_Top_Down(n-1) + DP_Top_Down(n-2); return memon; DP動態(tài)規(guī)劃ACM課件 基本概念 最短路問題 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 求A到E的最短路徑。 DP動態(tài)規(guī)劃ACM課件 直觀的方法是用回溯法搜索。時間復雜度為 指數(shù)級。 低效的原因：沒有充分利用重疊子問題的性 質(zhì)。 DP動態(tài)規(guī)劃ACM課件 此圖有明顯的次序，可以劃分為5階段。 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 階段0階段1階段2階段3階段4 DP動態(tài)規(guī)劃ACM課件 設 Diskx 為第k階段城

4、市x到城市E的最短路徑長度。 map i j 為i，j兩個城市間的距離。 遞歸方程為 Diskx = min Disk+1y+mapx,y 此問題時間復雜度降為O(n2). DP動態(tài)規(guī)劃ACM課件 狀態(tài)：貼切，簡潔的描述出事物性質(zhì)的單元量。例如： Disx。 要求：狀態(tài)與狀態(tài)之間可以轉(zhuǎn)移，以便有初始狀態(tài)逐漸轉(zhuǎn)移 到目標狀態(tài)，找到問題的解。 階段：若干性質(zhì)相近可以同時處理的狀態(tài)的集合。就是計算 狀態(tài)的順序。 要求：每個階段中狀態(tài)的取值只與這個階段之前的階段中的 狀態(tài)有關，與這個階段之后的階段中的狀態(tài)無關。 DP動態(tài)規(guī)劃ACM課件 狀態(tài)轉(zhuǎn)移方程：前一個階段中的狀態(tài)轉(zhuǎn)移到后一個 階段的狀態(tài)得演變規(guī)律

5、，即相鄰兩個階段的狀態(tài)變 化方程。 fk(i) = opt fk-1(j) + cost(i,j) k階段的i狀態(tài)與k-1階段的j狀態(tài)有關 決策：計算每個狀態(tài)時作出的選擇。 DP動態(tài)規(guī)劃ACM課件 適合用DP解決的問題的性質(zhì) 最優(yōu)子結(jié)構(gòu):若求解的問題是最優(yōu)化問題，則原問題 最優(yōu)當且僅當自問題最優(yōu)。 Mod 4 最優(yōu)路徑問題 找出1到4的一條長度mod 4的余數(shù)最小的路徑。 123 4 DP動態(tài)規(guī)劃ACM課件 此最優(yōu)化問題不滿足最優(yōu)子結(jié)構(gòu)，所以不適合用DP。 但如果我們增加狀態(tài)的維數(shù)，將最優(yōu)化問題轉(zhuǎn)化成 判定性問題，再運用DP，問題就可得以解決。 設 fki 為bool型數(shù)組，表示從1點到k點長

6、度mod4 為i的路徑是否存在。 fki= fk-1i-lenk1 | fk-1i-lenk2 | | fk-1i-lenkn DP動態(tài)規(guī)劃ACM課件 無后效性：決策之取決于當前狀態(tài)的特征因 素，而和到達此狀態(tài)的方式無關。也就是每 個階段中狀態(tài)的取值只與這個階段之前的階 段中的狀態(tài)有關，與這個階段之后的階段中 的狀態(tài)無關。 如果當前定義的狀態(tài)不滿足無后效性，應重 新定義。 DP動態(tài)規(guī)劃ACM課件 一維狀態(tài)存儲問題 硬幣問題1： 有n種硬幣，每種硬幣的面值為vi元，且只有一 枚，問用這n種硬幣找零S元的方法數(shù)。 設dij為前i種硬幣組成j元的方法數(shù)。 dij = di-1j + di-1j-vi

7、 d00=1,d01S=0 空間復雜度為O(n2),浪費！ DP動態(tài)規(guī)劃ACM課件 d0=1; d1S=0; for (i=1; i=vi; j-) dj += dj-vi; DP動態(tài)規(guī)劃ACM課件 0-1背包問題： 給定n種物品和一背包。物品i的重量是wi， 其價值為vi，背包的容量為c。問應如何選 擇裝入背包中的物品，使得裝入背包中物品 的總價值最大? DP動態(tài)規(guī)劃ACM課件 設m(i,j)是背包容量為j，可選擇物品為i， i+1，,n時，0-1背包問題的最優(yōu)值。 m(i,j) = max m(i+1,j), m(i+1,j-wi)+vi j=wi m(i+1,j)0=jwn 0 i=jw

8、n DP動態(tài)規(guī)劃ACM課件 d0c=0; for (i=1; i=wi; j-) dj = max(dj,dj-wi+vi); DP動態(tài)規(guī)劃ACM課件 推薦題目： POJ1384 Piggy-Bank DP動態(tài)規(guī)劃ACM課件 POJ1384參考代碼 #include using namespace std; int d100052; /第2維用0表示標記，1表示錢的值 int main() int x,y,weight; int w,m; int i,j,t,n; scanf(%d, while(t-) scanf(%d%d, weight=y-x; memset(d,0,sizeof(d);

9、 d00=1; /重要的初值 scanf(%d, for(i=1;i=n;i+) /階段 scanf(%d%d, for(j=0;j=weight-w;j+) /枚舉 if(dj0=1) /當前有，才可以疊加到后一層 x=j+w; if(dx0=0) dx1=dj1+m; else dx1=min(dx1,dj1+m); /最重要的比較部分！ dx0=1; if (dweight0=1) printf (The minimum amount of money in the piggy-bank is %d.n,dweight1); else printf (This is impossible

10、.n); return 0; DP動態(tài)規(guī)劃ACM課件 硬幣問題2： 有n種硬幣，每種硬幣的面值為vi元，有mi 枚，問用這n種硬幣找零S元的方法數(shù)。 DP動態(tài)規(guī)劃ACM課件 d0=1;d1S=0; for (i=1; i=vi; j-) for(k=1;k=0) dj += dj-k*vi; DP動態(tài)規(guī)劃ACM課件 硬幣問題3： 有n種硬幣，每種硬幣的面值為vi元，有無 數(shù)枚，問用這n種硬幣找零S元的方法數(shù)。 DP動態(tài)規(guī)劃ACM課件 d0=1;d1S=0; for (i=1; i=vi; j-) for(k=1;k+) if (j-k*vi=0) dj += dj-k*vi; else bre

11、ak; DP動態(tài)規(guī)劃ACM課件 d0=1; d1S=0; for (i=1; i=n; i+) for (j=vi;j=S; j+) dj += dj-vi; DP動態(tài)規(guī)劃ACM課件 POJ2614 Old Wine Into New Bottles 有n種小瓶子，每種瓶子容量范圍是Vi1Vi2，要 灌滿容量為L的大瓶子。問最少差多少體積沒有灌 滿。 設di表示體積為i是否可以達到。若v可取到，則 di=di | di-v DP動態(tài)規(guī)劃ACM課件 d0=1;d1L=0; for(i=0;in;i+) for(j=0;j=L-vi1;j+) if (dj=1) for(k=vi1;k=vi2;k

12、+) dj+k=1; DP動態(tài)規(guī)劃ACM課件 POJ2614參考代碼 #include using namespace std; int f450001=0,v1022; bool fff4600; int main() int i,j,k; int l,n; int ff=1; while(scanf(%d%d,i= 450000) printf(0n);continue; memset(f,0,sizeof(int)*(l+1); memset(fff,0,sizeof(fff); f0=1; for(i=1;i=n;i+) for(k=vi0;k=vi1;k+) if(fffk) con

13、tinue; for(j=0;j=l-k;j+) fffk=1; if(fj) fj+k=1; if(fl) goto out; out: for(i = 0;i = l; i+) if(fl-i) printf(%dn,i); break; return 0; DP動態(tài)規(guī)劃ACM課件 最大子段和問題： 給定由n個整數(shù)(可能為負整數(shù))組成的序列 a1,a2,an，求該序列形如的 子段和的 最大值。 j ik ka DP動態(tài)規(guī)劃ACM課件 設bi為到ai截至且包括ai的字段最大和。 int maxsum() int sum=0,b=0; for(int i=0;i0) b+=ai; /正的就連接

14、起來 else b=ai;/不然重新來過 if (bsum) sum=b;/sum記錄的一直是最大的值 return sum; DP動態(tài)規(guī)劃ACM課件 引申問題： 最大子矩陣和問題 最大m段子段和問題 DP動態(tài)規(guī)劃ACM課件 最長遞增子序列（LIS） 常規(guī)DP，時間復雜度為O(n2)。 存在一種特殊的方法，時間復雜度為 O（n*logk)。 DP動態(tài)規(guī)劃ACM課件 推薦題目： POJ1631 Bridging Signals DP動態(tài)規(guī)劃ACM課件 POJ1631參考代碼 #include using namespace std; int d40001; int main() int n,t;

15、 int i,p,num; int high,low,x; scanf(%d, while( t-) scanf(%d, scanf(%d, p=1; for(i=2;idp) p+;dp=num;continue; high=p,low=1; for(;highlow+1;) x=(high+low)/2; if(numdx) low=x; else if(numdx) high=x; if(numdlow) dhigh=num; else if(numdlow) dlow=num; printf(%dn,p); return 0; DP動態(tài)規(guī)劃ACM課件 二維狀態(tài)存儲問題 矩陣連乘問題矩陣

16、連乘問題 （MCM） A(m*n) * B(n*q) cost=m*n*q A1 (10 x 100), A2 (100 x 5), A3 (5 x 50) (A1 (A2 A3) = 100 x 5 x 50 + 10 * 100 * 50 = 75000 (A1 A2) A3) = 10 x 100 x 5 + 10 x 5 x 50 = 7500 DP動態(tài)規(guī)劃ACM課件 最優(yōu)子結(jié)構(gòu)： DP動態(tài)規(guī)劃ACM課件 重疊子問題： DP動態(tài)規(guī)劃ACM課件 狀態(tài)轉(zhuǎn)移方程： DP動態(tài)規(guī)劃ACM課件 階段劃分： DP動態(tài)規(guī)劃ACM課件 推薦題目： POJ1141 Brackets Sequence DP動態(tài)規(guī)劃ACM課件 POJ1141參考代碼 #include #include using namespace std; int n,l; string str; int opt101101; string ds101101; char ss101; void dynamic() int i,j,k,p; for(i=1;i=l;i+) optii=1; optii-1=0; dsii-1=; if (stri=( | stri=