實(shí)驗(yàn)三動(dòng)態(tài)規(guī)劃

1、實(shí)驗(yàn)三動(dòng)態(tài)規(guī)劃 算法 分析 與 設(shè)計(jì) 實(shí)驗(yàn)報(bào)告 學(xué)號 姓名 班級 上課地點(diǎn) 教師 上課時(shí)間 實(shí)驗(yàn) 三 動(dòng)態(tài)規(guī)劃 1. 實(shí)驗(yàn)?zāi)康?1.1 理解動(dòng)態(tài)規(guī)劃算法的主要設(shè)計(jì)思想和基本步驟； 1.2 掌握用動(dòng)態(tài)規(guī)劃策略解決實(shí)際問題。 2. 實(shí)驗(yàn)環(huán)境 2.1 eclipse 2.2 window xp 3. 實(shí)驗(yàn)內(nèi)容 3.1 矩陣連乘問題 3.2 最長公共子序列問題 3.3 0-1 背包問題 4. 教師批改意見 簽字： 日期： 成績 實(shí)驗(yàn)報(bào)告細(xì)表 1 1. . 矩陣連乘問題 1.1 算法設(shè)計(jì)思想 (1) 分析最優(yōu)解：計(jì)算 ai:j的最優(yōu)次序所包含的計(jì)算矩陣子鏈 ai:k和ak+1:j的次序也是最優(yōu)的 (2)

2、建立遞歸關(guān)系：設(shè)計(jì)算 ai:j，1ijn，所需要的最少數(shù)乘次數(shù) mi,j，則原問題的最優(yōu)值為 m1,n 當(dāng) i=j 時(shí)，ai:j=ai，因此，mi,i=0，i=1,2,n 當(dāng) ij 時(shí)，j k ip p p j k m k i m j i m1 , 1 , , -+ + + = 可以遞歸地定義 mi,j為： ïîïíì< + + +=-< £j i p p p j k m k i mj ij i mj k i , 1 , min0 , 1j k i k 的位置有 j-i 種可能 （3）計(jì)算最優(yōu)值：用動(dòng)態(tài)規(guī)劃算法解此問題，可

3、依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題答案。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只要簡單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法 public static void matrixchain(int p,int m,int s) int n=p.length-1; 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+1ij; sij=i; for(int k=i+1;kj;k+) int t=mik+mk+1

4、j+pi-1kj; if(tmij) mij=t; sij=k; （4）構(gòu)造最優(yōu)解：算法 matrixchain 記錄了構(gòu)造最優(yōu)解所需的全部信息。 sij=k 表明計(jì)算矩陣鏈 ai:j的最佳方式在矩陣 a k 和 a k+1 之間斷開，即最優(yōu)的加括號方式為(ai:k)(ak+1:j)。 因此，從 s1n記錄的信息可知計(jì)算 a1:n的最優(yōu)加括號 方式為 (a1:s1n)(as1n+1:n)。而 a1:s1n的最 優(yōu)加括號方式為 (a1:s1s1n)(as1s1n+1:s1s1n)。 同理可以確定 as1n+1:n的最優(yōu)加括號方式在 ss1n+1n處斷開。 照此遞推下去，最終可以得到 a1:n的最

5、優(yōu)完全加括號方式， 即構(gòu)造出問題的一個(gè)最優(yōu)解。 public static void traceback(int s,int i,int j) if(i=j)return; traceback(s,i,sij); traceback(s,sij+1,j); system.out.println(multiply a+i+,+sij+and a+(sij+1)+,+j); 1.2 程序源碼 矩陣連乘 代碼： /* * 下面是矩陣連乘問題的動(dòng)態(tài)規(guī)劃算法 * 假設(shè)有6個(gè)矩陣： * a1 a2 a3 a4 a5 a6 * 30*35 35*15 15*5 5*10 10*20 20*25 則matri

6、xchain為 * 30, 35, 15, 5, 10, 20, 25 結(jié)果為 * (a1 * (a2 * a3) * (a4 * a5) * a6) ) * author zhanlingxia */ package juzhenliancheng; public class juzhenliancheng public static void main(string args) intp = 30, 35, 15, 5, 10, 20, 25; / 矩陣的維數(shù)存放于數(shù)組p中 matrixmultiply (p); /矩陣連乘 public static void matrixmultipl

7、y( int p) int dimen = p.length; intm = new intdimendimen; /定義了存放最優(yōu)值數(shù)組m ints = new intdimendimen; /定義了記錄斷開位置的數(shù)組s matrixchain (p,m,s); system. out .println(最優(yōu)乘法次數(shù)： + m1dimen - 1); system. out .println(劃分規(guī)則為：); traceback (s, 1, dimen - 1); /*1：首先計(jì)算出mii 2：然后根據(jù)遞歸式按矩陣鏈長遞增的方式以此計(jì)算mii+1i=1,2,3.。 3：計(jì)算mij時(shí)，只要用

8、到mik和mk+1j*/ public static void matrixchain( int p, int m, int s) int n=p.length-1; for( int i=1;i=n;i+)mii=0;/計(jì)算單一矩陣 /根據(jù)遞歸式按矩陣鏈長遞增的方式以此計(jì)算mii+1i=1,2,3.。 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;kj;k+) int t=mik+mk+1j+pi-1*pk*pj; /更新mij，si

9、j的值 f if(tmij) mij=t; sij=k; / 按算法matrixchain計(jì)算出斷點(diǎn)矩陣s指示的加括號方式 public static void traceback( int s, int i, int j) f if(i=j) return; traceback (s,i,sij); traceback (s,sij+1,j); system. out .println(multiply a+i+,+sij+and a+(sij+1)+,+j); 1.3 實(shí)驗(yàn)結(jié)論 4 1.4 心得體會(huì) 算法設(shè)計(jì)真的需要邏輯思維，能得到結(jié)果挺開心的。 : 2: 最長公共子序列 2.1 算法設(shè)計(jì)

10、思想 (1) 設(shè) 序 列 x=x 1 ,x 2 ,x m 和 y=y 1 ,y 2 ,y n 的 最 長 公 共 子 序 列 為z=z 1 ,z 2 ,z k ，則 若 x m =y n ，則 z k =x m =y n ，且 z k-1 是 x m-1 和 y n-1 的最長公共子序列。 若 x m y n 且 z k x m ，則 z 是 x m-1 和 y 的最長公共子序列。 若 x m y n 且 z k y n ，則 z 是 x 和 y n-1 的最長公共子序列 (2)建立遞歸關(guān)系：由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用 cij記錄序列和的最長公共子序列的

11、長度。其中， x i =x 1 ,x 2 ,x i ；y j =y 1 ,y 2 ,y j 。當(dāng) i=0 或 j=0 時(shí)，空序列是 x i 和 y j 的最長公共子序列。故此時(shí) cij=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下： ïîïíì¹ >= >= =- -+ - - =j ij iy x j iy x j ij ij i c j i cj i c j i c; 0 ,; 0 ,0 , 0 1 , 1 max1 1 1 0 （3）計(jì)算最優(yōu)值：算法 lcslength 以序列 x=x1,x2xm和 y=y1，

12、y2ym作為輸入。輸出兩個(gè)數(shù)組 c 和 b。其中，cij存儲(chǔ) xi 和 yj 的最長公共子序列的長度，bij記錄 cij的值是由哪一個(gè)子問題的解得到的，問題的最優(yōu)值存放于 cmn中 public static int lcslength ( charx, chary, intb) int m=x.length-1; int n=y.length-1; intc= new intm+1n+1; for( int i=1;i=m;i+)ci0=0; for( int i=1;i=n;i+)c0i=0; for( int i=1;i=m;i+) for( int j=1;j=n;j+) f if(x

13、i=yj) cij=ci-1j-1+1; bij=1; else f if(ci-1j=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; return cmn; （4）構(gòu)造最優(yōu)解： public static void lcs( int i, int j, charx, intb) f if(i=0|j=0) return; f if(bij=1) lcs (i-1,j-1,x,b); system. out .print(xi); else f if(bij=2) lcs (i-1,j,x,b); else lcs (i,j-1,x,b); 2.

14、2 程序源碼 最長公共子序列代碼： /* * 下面是最長公共子序列問題的動(dòng)態(tài)規(guī)劃算法 * charx="a","b","c","d","a","b" * chary="b","d","c","a","b","a" * 打印結(jié)果為cab * author zhanlingxia */ package zuichanggonggongzixulie; publi

15、c class zuichanggonggongzixulie /*計(jì)算最優(yōu)值 cij存儲(chǔ)xi和yi的最長公共子序列的長度 bij記錄cij的值是由最長公共子序列*/ public static int lcslength ( charx, chary, intb) int m=x.length-1; int n=y.length-1; intc= new intm+1n+1; /空序列最長公共子序列 for( int i=1;i=m;i+)ci0=0; for( int i=1;i=n;i+)c0i=0; /對角線+1 for( int i=1;i=m;i+) for( int j=1;j=

16、n;j+) f if(xi=yj) cij=ci-1j-1+1; bij=1; /和上面一樣 else f if(ci-1j=cij-1) cij=ci-1j; bij=2; /和左邊一樣 else cij=cij-1; bij=3; return cmn; /打印最長公共子序列 public static void lcs( int i, int j, charx, intb) f if(i=0|j=0) return; f if(bij=1) lcs (i-1,j-1,x,b); system. out .print(xi); else f if(bij=2) lcs (i-1,j,x,b

17、); else lcs (i,j-1,x,b); public static void main(string args) charx="a","b","c","d","a","b" chary="b","d","c","a","b","a" intb= new intx.length+1y.length+1; system. out .println(最長

18、公共子序列：); int n= lcslength (x,y,b); system. out .println(); system. out .println(其長度為：+n); system. out .println(最長公共子序列為：); lcs (x.length-1,y.length-1,x,b); 2.3 實(shí)驗(yàn)結(jié)論 4 2.4 心得體會(huì)： 最長公共子序列比較好理解哦。做起來也相較簡單多了 3 3 0 0- -1 1 背包 問題 3.1 算法設(shè)計(jì)思想 (1) 分析最優(yōu)解： 設(shè)(y 1 ,y 2 ,y n )是所給 0-1 背包問題的一個(gè)最優(yōu)解，則 (y 2 ,y n )是下面相應(yīng)子問

19、題的一個(gè)最優(yōu)解。 å=nii i xv2max ïîïíì£ £ Î- £å=n i xy w c x winii i2 , 1 , 0 1 12 (2)建立遞歸關(guān)系： 設(shè)所給 0-1 背包問題的子問題 å=ni kk k xv max ïîïíì£ £ Σå=n k i xj x wkni kk k, 1 , 0 的最優(yōu)值為 m(i，j)，即 m(i，j)是背包容量為 j，

20、可選擇物品為 i，i+1，n 時(shí) 0-1 背包問題的最優(yōu)值。由 0-1 背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算 m(i，j)的遞歸式如下。 ii i iw jw jj i mv w j i m j i mj i m< £³îíì+ - + +=0 ) , 1 ( ) , 1 ( ), , 1 ( max) , ( nn nw jw j vj n m< £³îíì=0 0) , ( （3）計(jì)算最優(yōu)值： public static void knapsack( int v, int w,

21、 n int t c, int m) int n = v.length-1; int jmax = math. min (wn-1, c); for( int j = 0; j = jmax; j+) mnj = 0; /當(dāng)wnj 有 mnj=0 /mnj 表示只有n物品，背包的容量為j時(shí)的最大價(jià)值 for ( int j = wn; j = c; j+) mnj = vn; /當(dāng)wn=j 有mnj=vn /遞規(guī)調(diào)用求出m其它值，直到求出m0c for( int i = n-1; i =1; i-) jmax = math. min (wi-1,c); for( int j = 0; j=jm

22、ax; j+) mij = mi+1j; for( int j = wi; j = c; j+) mij = math. max (mi+1j,mi+1j-wi+vi); m0c = m1c; f if(c = w0) m0c = math. max (m0c,m1c-w0+v0); system. out .println(+m0c); （4）構(gòu)造最優(yōu)解： public static void traceback( int m, int w, int c, int x) / 根據(jù)最優(yōu)值求出最優(yōu)解 int n = w.length-1; for( int i = 0; in;i+) f if(

23、mic = mi+1c) xi = 0; else xi = 1; c -= wi; xn = (mnc0)?1:0; 3.2 程序源碼 0 0- -1 1 背包問題 代碼： /* * 下面是0-1的動(dòng)態(tài)規(guī)劃算法 *v w c 分別是價(jià)值、重量、和背包容量數(shù)組 *mij表示有in個(gè)物品，背包容量為j的最大價(jià)值。 * author zhanlingxia */ public class beibao public static void knapsack( int v, int w, int c, int m) int n = v.length-1; int jmax = math. min (wn-1, c); for( int j = 0; j = jmax; j+) mnj = 0; /當(dāng)wnj 有 mnj=0 /mnj 表示只有n物品，背包的容量為j時(shí)的最大價(jià)值 for ( int j = wn; j = c; j+) mnj = vn; /當(dāng)wn=j 有mnj=vn /遞規(guī)調(diào)用求出m其它值，直到求出m0c fo