動態(tài)規(guī)劃復習

1、1軟件軟件701周數(shù)周數(shù)5678910111213141516周二周二下午下午67節(jié)節(jié)TTTTTTTTTTP PTTTTTTTTTT考查考查TT周四周四12節(jié)節(jié)P PP PP PP PP PP PP PP PP PP PP P2計算機計算機05級級-軟件方向軟件方向周數(shù)周數(shù)56789101112周二周二12節(jié)節(jié)TTTTTTTTTTTTP PP P周四周四34節(jié)節(jié)P PP PP PP PP PP PTTTT3租用游艇問題租用游艇問題 長江游艇俱樂部在長江上設置了長江游艇俱樂部在長江上設置了n 個游艇出租站個游艇出租站1，2，n。游客可在這些游艇出租站租用游艇，并在下游的任何。游客可在這些游艇出租

2、站租用游艇，并在下游的任何一個游艇出租站歸還游艇。游艇出租站一個游艇出租站歸還游艇。游艇出租站i 到游艇出租站到游艇出租站j 之之間的租金為間的租金為r(i,j),1=ij=n。試設計一個算法，計算出從。試設計一個算法，計算出從游艇出租站游艇出租站1 到游艇出租站到游艇出租站n 所需的最少租金。所需的最少租金。編程任務：編程任務：對于給定的游艇出租站對于給定的游艇出租站i 到游艇出租站到游艇出租站j 之間的租金為之間的租金為r(i,j),1=ij=n，編程計算從游艇出租站，編程計算從游艇出租站1 到游艇出租站到游艇出租站n所需的最少租金。所需的最少租金。4租用游艇問題租用游艇問題數(shù)據(jù)輸入：數(shù)據(jù)

3、輸入：第第1 行中有行中有1 個正整數(shù)個正整數(shù)n（n=200），表示有），表示有n個游艇個游艇出租站。接下來的出租站。接下來的n-1 行是行是r(i,j),1=ij=n。結果輸出結果輸出:程序運行結束時，輸出從游艇出租站程序運行結束時，輸出從游艇出租站1 到游艇出租站到游艇出租站n所需的最少租金。所需的最少租金。輸入示例輸入示例35 157輸出示例輸出示例121 2 351575input:713 15 24 44 29 50 16 18 8 21 53 7 26 4 38 12 1 29 9 4 11 Output:25租用游艇問題租用游艇問題1 2 3 4 5 6 713152444295

4、001234560131524442950116188215327264383121294945116原始數(shù)據(jù)原始數(shù)據(jù)6租用游艇問題租用游艇問題012345601315244429501161882153272643831212949451160123456013152221192510161881712200719415300012112400009450000011601234560131522212950101618817532007194383000121124000094500000116012345601315224429501016188215320071943830001212

5、94000094500000116原始數(shù)據(jù)原始數(shù)據(jù)運算結束運算結束7租用游艇問題租用游艇問題void dyna() for (int k=2; kn; k+)for (int i=0; in-k; i+) int j=i+k;for (int p=i+1; ptemp) fij = temp;最優(yōu)值在最優(yōu)值在f0n-1中中.9完全加括號的矩陣連乘積可遞歸地定義為：完全加括號的矩陣連乘積可遞歸地定義為：n 單個矩陣是完全加括號的；單個矩陣是完全加括號的；n 矩陣連乘積矩陣連乘積A是完全加括號的，則是完全加括號的，則A可表示為可表示為2個完全加個完全加括號的矩陣連乘積括號的矩陣連乘積B和和C的乘積

6、并加括號，即的乘積并加括號，即A=(BC) 設有四個矩陣設有四個矩陣A, B, C, D，總共有五中完全加括號的方式，總共有五中完全加括號的方式:(A(BC)D)(A(B(CD)(AB)(CD)(AB)C)D)(A(BC)D)10設有四個矩陣設有四個矩陣A, B, C, D，它們的維數(shù)分別是：，它們的維數(shù)分別是：A=5010, B=1040, C=4030, D=305矩陣矩陣A和和B可乘的條件是可乘的條件是: 矩陣矩陣A的列數(shù)等于矩陣的列數(shù)等于矩陣B的行數(shù)的行數(shù).設設A是是pq的矩陣的矩陣, B是是qr的矩陣的矩陣, 則乘積是則乘積是pr的矩陣的矩陣;計算量是計算量是pqr.上述上述5種完全

7、加括號方式的計算工作量為種完全加括號方式的計算工作量為:(A(BC)D), (A(B(CD), (AB)(CD), (AB)C)D), (A(BC)D)16000, 10500, 36000, 87500, 34500BC: 104030 = 12000, (BC)D: 10305 = 1500,(A(BC)D): 50105 = 250011窮舉法窮舉法動態(tài)規(guī)劃動態(tài)規(guī)劃將矩陣連乘積將矩陣連乘積AiAi+1Aj 簡記為簡記為Ai:j, 這里這里ij;考察計算考察計算Ai:n的最優(yōu)計算次序。的最優(yōu)計算次序。設這個計算次序在矩陣設這個計算次序在矩陣Ak和和Ak+1之間將矩陣鏈斷開，之間將矩陣鏈斷開

8、，1kn，則其相應完全加括號方式為，則其相應完全加括號方式為(A1A2Ak)(Ak+1Ak+2An)計算量：計算量：A1:k的計算量加上的計算量加上Ak+1:n的計算量，再的計算量，再加上加上A1:k和和Ak+1:n相乘的計算量相乘的計算量12設計算設計算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)，所需要的最少數(shù)乘次數(shù)mi,j，則，則原問題的最優(yōu)值為原問題的最優(yōu)值為m1,n 當當i=j時，時，Ai:j=Ai，因此，因此，mi,i=0，i=1,2,n當當ij 時，時，這里這里Ai的維數(shù)是的維數(shù)是Pi-1Pi可以遞歸地定義可以遞歸地定義mi,j為：為：jkipppjkmkimjim1, 1,jipp

9、pjkmkimjijimjki, 1,min0,1jki 的位置只有的位置只有 種種可能可能kij 13rj void MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*

10、pj; if (t mij) mij = t; sij = k; 14A1A2A3A4A5A630 3535 1515 55 1010 2020 25113752010350437555427125205351000262554 3213000201535250005322min52541531521pppmmpppmmpppmmm15void MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n -

11、 r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t 0時時bj=bj-1+aj，否則，否則bj=aj。則計算則計算bj的動態(tài)規(guī)劃遞歸式的動態(tài)規(guī)劃遞歸式bj=maxbj-1+aj，aj，1jn。jnjjikkjinjjkknjijikkjijbaanjab111111maxmaxmaxmax1max為，則所求的最大子段和，若記123456ai-211-413-5-2b(初值初值=0)-211720151

12、3sum01111202020203. 動態(tài)規(guī)劃方法求解動態(tài)規(guī)劃方法求解據(jù)此，可設計出求最大子段和的動態(tài)規(guī)劃算法如下：據(jù)此，可設計出求最大子段和的動態(tài)規(guī)劃算法如下：int MaxSum(int n, int a)int sum=0; /sum是是bj(1jn)的最大值的最大值int b=0;for (int i=1;i0) b+=ai; else b=ai;if (bsum) sum=b;return sum;顯然該算法的計算時間為顯然該算法的計算時間為O(n)。123456ai-211-413-5-2b(初值初值=0)-2117201513sum0111120202021若給定序列若給定序列

13、X=x1,x2,xm，則另一序列，則另一序列Z=z1,z2,zk，是是X的子序列是指存在一個嚴格遞增下標序列的子序列是指存在一個嚴格遞增下標序列i1,i2,ik使得對于所有使得對于所有j=1,2,k有：有：zj=xij。例如，序列例如，序列Z=B，C，D，B是序列是序列X=A，B，C，B，D，A，B的子序列，相應的遞增下標序列為的子序列，相應的遞增下標序列為2，3，5，7。給定給定2個序列個序列X和和Y，當另一序列，當另一序列Z既是既是X的子序列又是的子序列又是Y的的子序列時，稱子序列時，稱Z是序列是序列X和和Y的的公共子序列公共子序列。給定給定2個序列個序列X=x1,x2,xm和和Y=y1,

14、y2,yn，找出，找出X和和Y的最長公共子序列。的最長公共子序列。 222個序列的最長公共子序列包含了這個序列的最長公共子序列包含了這2個序列的個序列的前綴的最長公共子序列前綴的最長公共子序列。最長公共子序列問題具有最長公共子序列問題具有最優(yōu)子結構性質最優(yōu)子結構性質。 設序列設序列X=x1,x2,xm和和Y=y1,y2,yn的最長公共子序的最長公共子序列為列為Z=z1,z2,zk ，則，則q 若若xm=yn，則，則zk=xm=yn，且，且zk-1是是xm-1和和yn-1的最長公共的最長公共子序列。子序列。q 若若xmyn且且zkxm，則，則Z是是xm-1和和Y的最長公共子序列。的最長公共子序列

15、。q 若若xmyn且且zkyn，則，則Z是是X和和yn-1的最長公共子序列。的最長公共子序列。23jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110由最長公共子序列問題的最優(yōu)子結構性質建立子問題最優(yōu)由最長公共子序列問題的最優(yōu)子結構性質建立子問題最優(yōu)值的遞歸關系。值的遞歸關系。用用cij記錄序列和的最長公共子序列的長度。記錄序列和的最長公共子序列的長度。 Xi=x1,x2,xi；Yj=y1,y2,yj。當當i=0或或j=0時，空序列是時，空序列是Xi和和Yj的最長公共子序列。的最長公共子序列。故此時故此時Cij=0。其它情況下，由最優(yōu)子結構性質可建

16、立遞歸關系如下：其它情況下，由最優(yōu)子結構性質可建立遞歸關系如下：24void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 由于在所考慮的子問題空間中，總共有由于在所考慮的子問題空間中，總共有(mn)個不同的子問題，個不同

17、的子問題，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。01234.n000000 010203040 m 0ij25void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bi

18、j=3; 0123456yiBDCABA0 xi00000001A00001112B01111223C01122224B01122335D01222336A01223347B0122344ij26由數(shù)組由數(shù)組b構造最長公共子序列構造最長公共子序列void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b);0123456yiBDCABA0 xi000000

19、01A00001112B01111223C01122224B01122335D01222336A01223347B0122344ij0123456yiBDCABA0 xi1A 2B 3C 4B 5D 6A 7B ij27n個作業(yè)個作業(yè)1，2，n要在由要在由2臺機器臺機器M1和和M2組成的流水線上組成的流水線上完成加工。完成加工。每個作業(yè)加工的順序都是先在每個作業(yè)加工的順序都是先在M1上加工，然后在上加工，然后在M2上加工。上加工。M1和和M2加工加工作業(yè)作業(yè)i所需的時間分別為所需的時間分別為ai和和bi。流水作業(yè)調度問題要求確定這流水作業(yè)調度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使得從個作業(yè)的

20、最優(yōu)加工順序，使得從第一個作業(yè)在機器第一個作業(yè)在機器M1上開始加工，到最后一個作業(yè)在機器上開始加工，到最后一個作業(yè)在機器M2上上加工完成所需的加工完成所需的時間最少時間最少。123456A2571052B384113428流水作業(yè)調度問題的流水作業(yè)調度問題的Johnson算法算法(1) 令令(2) 將將N1中作業(yè)依中作業(yè)依ai的非減序排序；的非減序排序； 將將N2中作業(yè)依中作業(yè)依bi的非增序排序；的非增序排序；(3) N1中作業(yè)接中作業(yè)接N2中作業(yè)構成滿足中作業(yè)構成滿足Johnson法則的最優(yōu)調度。法則的最優(yōu)調度。;|,|21iiiibaiNbaiNN1中作業(yè)依中作業(yè)依ai的非減序排序的非減序

21、排序N2中作業(yè)依中作業(yè)依bi的非增序排序的非增序排序123456A2571052B384113429int FlowShop(int n, int *a, int *b, int *c) class Jobtype public: int operator= (Jobtype a) const /排序重載函數(shù)排序重載函數(shù) return key=a.key; int key; int index; bool job; ; Jobtype *d=new Jobtypen; for(int i=0; ibi?bi:ai; di.job = ai=bi; di.index = i; sort(d,n)

22、;012345A2571052B3841134key2541032jobTTFTFTindex01234530int j=0, k=n-1; for(int i=0; in; i+) if(di.job) cj+ = di.index; else ck- - = di.index; j = ac0; k = j+bc0; for(int i=1; in; i+) j += aci;k = jj,無法裝入無法裝入背包容量背包容量: j1. 0jwi;2. jwi34C=6123wi234vi125xi1010123456100000062000255530000555jiiiiiwjwjjimv

23、wjimjimjim0), 1(), 1(), 1(max),(nnnwjwjvjnm00),(m23=max(m33,m30+2)=2;m24=max(m34,m31+2)=5;m25=max(m35,m32+2)=5;m26=max(m36,m33+2)=5;m16=max(m26,m24+1)=6;cn35代碼分析代碼分析#define NUM 100void knapsack(int v , int w , int c, int n, int m NUM) int jMax=min(wn-1,c); for( int j=0; j=jMax; j+) mnj=0; for( int j

24、=wn; j1; i-) jMax=min(wi-1,c); for( int j=0; j=jMax; j+) mij=mi+1j; for(int j=wi; j=w1) m1c=max(m1c, m2c-w1+v1); nnnwjwjvjnm00),(iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(36代碼分析代碼分析void traceback( int m NUM, int w , int c, int n, int x ) for(int i=1; i0)? 1:0; C=6123wi234vi125xi1010123456100000062

25、000255530000555ic37最長單調遞增子序列最長單調遞增子序列(習題習題3-1)設計一個設計一個O(n2)時間的算法時間的算法, 找出由找出由n個數(shù)組成的序列的最個數(shù)組成的序列的最長單調遞增子序列。長單調遞增子序列。輸入輸入第第1個整數(shù)個整數(shù)n(0n100),表示后面有表示后面有n個數(shù)據(jù)，全部為整數(shù)個數(shù)據(jù)，全部為整數(shù)輸出輸出輸出最長單調遞增子序列的長度；輸出最長單調遞增子序列的長度；樣例輸入樣例輸入8 65 158 170 155 239 300 207 389樣例輸出樣例輸出638最長單調遞增子序列最長單調遞增子序列用數(shù)組用數(shù)組b0:n-1記錄以記錄以ai (0in) 為結尾元素

26、的最長遞增子為結尾元素的最長遞增子序列的長度。序列的長度。序列序列a的最長遞增子序列的長度為：的最長遞增子序列的長度為：max bi顯然，顯然，bi滿足最優(yōu)子結構性質，可以遞歸的定義為：滿足最優(yōu)子結構性質，可以遞歸的定義為：b0 = 1;bi = max bk + 1即即k在在0(i-1)范圍內范圍內, 若若ak ai, 尋找最大的尋找最大的bk.據(jù)此將計算據(jù)此將計算bi轉化為轉化為i個規(guī)模更小的子問題。個規(guī)模更小的子問題。0in0kiak ai6515817015523930020738912324546ik39最長單調遞增子序列最長單調遞增子序列int main() int n;scanf

27、(%d, &n);int a100;for (int i=0; in; i+) scanf(%d, &ai);printf(%dn, LISdyna( a, n);樣例輸入樣例輸入8 65 158 170 155 239 300 207 38940最長單調遞增子序列最長單調遞增子序列int main() int n;scanf(%d, &n);int a100;for (int i=0; in; i+) scanf(%d, &ai);printf(%dn, LISdyna(a, n);int LISdyna(int a , int n) int b100=0;i

28、nt i,j;b0 = 1;for (i=1;in; i+) int k = 0;/0i-1之間，之間，b的最大值的最大值for (j=0; ji; j+) if (aj=ai & kbj) k=bj;bi = k+1;int max = 0;for (i=0; imax) max = bi;return max;41編輯距離問題編輯距離問題設設A 和和B 是是2 個字符串。要用最少的字符操作將字符串個字符串。要用最少的字符操作將字符串A 轉換為字符串轉換為字符串B。這里所說的字符操作包括：。這里所說的字符操作包括：q 刪除一個字符；刪除一個字符；q 插入一個字符；插入一個字符；q 將

29、一個字符改為另一個字符。將一個字符改為另一個字符。將字符串將字符串A變換為字符串變換為字符串B 所用的最少字符操作數(shù)稱為字所用的最少字符操作數(shù)稱為字符串符串A到到B 的的編輯距離編輯距離，記為，記為d(A,B)。試設計一個有效算。試設計一個有效算法，對任給的法，對任給的2 個字符串個字符串A和和B，計算出它們的編輯距離，計算出它們的編輯距離d(A,B)。編程任務：編程任務：對于給定的字符串對于給定的字符串A和字符串和字符串B，編程計算其編輯距離，編程計算其編輯距離d(A,B)。42編輯距離問題編輯距離問題數(shù)據(jù)輸入：數(shù)據(jù)輸入：第一行是字符串第一行是字符串A，第二行是字符串，第二行是字符串B。結果輸出結果輸出:程序運行結束時，輸出編輯距離程序運行結束時，輸出編輯距離d(A,B) 。輸入文件示例輸入文件示例fxpimuxwrs輸出文件示例輸出文件示例543編輯距離問題編輯距離問題設所給的設所給的2個字符串為個字符串為A1m和和B1n，定義，定義:Di, j=(A1i, B1j)，單字符，單字符a, b之間的距離為：之間的距離為：考察從字符串考察從字符串A1i到字符串到字符串B1j的變換：的變換：q 字符字符Ai改為字符改為字符Bj，需要，需要(Ai, Bj)次操作；次操作；q 刪除字符刪除字符Ai，需要，需要1次操作；次操作；q 插