實驗二動態(tài)規(guī)劃算法

1、本文格式為Word版，下載可任意編輯實驗二動態(tài)規(guī)劃算法 試驗 二 動態(tài)規(guī)劃算法 基本題一：最長公共子序列問題 一、試驗目的與要求 1 1 、熟識最長公共子序列問題的算法； 2 2 、初步把握動態(tài)規(guī)劃算法； 二、試驗題 若給定序列 X=x1,x2, ,xm ，則另一序列 Z=z1,z2, ,zk ，是 X X 的子序列是指存在一個嚴格遞增下標序列 i1,i2, ,ik 使得對于全部 j=1,2, k ,k 有： zj=xij 。例如，序列 Z=B ，C C ，D D ， B 是序列 X=A ，B B ，C C ，B B ，D D ，A A ， B 的子序列，相應的遞增下標序列為 2 ，3 3 ，

2、5 5 ， 7 。 給定 2 2 個序列 X X 和 和 Y Y ，當另一序列 Z Z 既是 X X 的子序列又是 Y Y 的子序列時，稱 Z Z是序列 X X 和 和 Y Y 的公共子序列。 給定 2 2 個序列 X=x1,x2, ,xm和 和 Y=y1,y2, ,yn ，找出 X X 和 和 Y Y 的最長公共子序列。 三 (1) 試驗源代碼: : / 最長公共子序問題: : / 問題描述 : 若給定序列 X=x1,x2, ,xm ，則另一序列 Z=z1,z2, ,zk ， /是 是 X X 的子序列是指存在一個嚴格遞增下標序列 i1,i2, ,ik 使得對于全部j=1,2, k ,k 有

3、： zj=xij 。 / 例如，序列 Z=B ，C C ，D D ， B 是序列 X=A ，B B ，C C ，B B ，D D ，A A ， B 的子序列 ，相應的遞增下標序列為 2 ，3 3 ，5 5 ， 7 。 / 給定 2 2 個序列 X X 和 和 Y Y ，當另一序列 Z Z 既是 X X 的子序列又是 Y Y 的子序列時，稱 Z Z 是序列 X X 和 和 Y Y 的公共子序列。 / 給定 2 2 個序列 X=x1,x2, ,xm和 和 Y=y1,y2, ,yn ，找出 X X 和 和 Y Y 的最長公共子序列。 #includebits/stdc+.h using namesp

4、ace std; #define max 1000 / 留意：這里使用的 r char 數(shù)組，可以按字符輸出，若改為 g string 類型， / 執(zhí)行 printf(%c,Am- - 1) 就會報錯; ; char A100,B100; / 輸入的兩個串 a a 和 和 b b / 這里定義全局變量可以不賦值 0 0 ，由于全局變量自動賦值 0; int cmaxmax; / 記錄最長公共子序的長度； int bmaxmax; / 記錄狀態(tài)號; void LCS(int m,int n) if(m=0|n=0) return; else if(bmn=1) LCS(m- - 1,n- - 1

5、); printf(%c,Am- - 1); els e if(bmn=2) m=m- -; 1; LCS(m,n); else if(bmn=3) n=n- -; 1; LCS(m,n); void LCS_length(int m,int n) for(int i=1;i=m;i+) for(int j=1;j=n;j+) if(Ai- - 1=Bj- - 1) cij=ci- - 1j- - 1+1; bij=1; else if(ci- - 1j=cij- - 1) cij=ci- - 1j; bij=2; else cij=cij- - 1; bij=3; int main() pr

6、intf( 請輸入兩個待測的字符串: : n); scanf(%s,A); scanf(%s,B); int m=strlen(A); /m 為 為 A A 串長度； n int n=strlen(B); /n 為 為 B B 串長度; LCS_length(m,n); printf( 其最長公共子序的長度為 :%d n,cmn); printf( 其最長公共子序為 :); LCS(m,n); return 0; (2) 運行結果為: : (3) 算法思路: : 最長公共子序列的結構有如下表示： 設序列 X=x 1 1 , x 2 2 , , x m m 和 Y=y 1 1 , y 2 2 ,

7、 , y n n 的一個最長公共子序列Z=z 1 1 , z 2 2 , , z k k ，則： 1. 若 若 x x m m =y n n ，則 z z k k =x m m =y n n 且 Z Z k k- -1 1 是 是 X X m m- -1 1 和 和 Y Y n n- -1 1 ； 的最長公共子序列； 2. 若 若 x x m m y n n 且 且 z z k k x m ， 則 Z Z 是 X X m m- -1 1 和 和 Y Y 的最長公共子序列； 3. 若 若 x x m m y n n 且 且 z z k k y n n ，則 Z Z 是 是 X X 和 和 Y Y

8、 n n- -1 1 的最長公共子序列。 其中 X X m m- -1 1 =x 1 1 , x 2 2 , , x m m- -1 1 ， ，Y Y n n- -1 1 =y 1 1 , y 2 2 , , y n n- -1 1 ， ，Z Z k k- -1 1 =z 1 1 , z 2 2 , , z k k- -1 1 。 。 基本題二：最大字段和問題 一、試驗目的與要求 1 1 、熟識最長最大字段和問題的算法； 2 2 、進一步把握動態(tài)規(guī)劃算法； 二、試驗題 若給定 n n 個整數(shù)組成的序列 a a 1 1 ，a a 2 2 ，a a 3 3 ，a a n n ，求該序列形如 a a

9、 i i a a i i 1 1 a a n n 的最大值。 三，試驗源代碼: : #includebits/stdc+.h #define max 1000 using namespace std; int N; / 表示一個數(shù)組的長度值; ; int dpmax; / 記錄以 i i 為結尾的最大子段和; / 通過 d dp p 數(shù)組記錄最優(yōu)下標的 t start 和 和 end; void Maxsum(int a) int maxx=0; int end,start; for(int i=1;i=N;i+) if(dpi- - 10) dpi=dpi- - 1+ai; else dpi

10、=ai; if(maxx=dpi) maxx=dpi; end=i; start=end; int i; for(i=start- - 1;i=0;i- -) ) if(dpi=0) start=i; else break; i+; start=i; printf(MaxSum:%d n,dpend); printf(Best start:%d n,start); printf(Best end:%d n,end); int main() printf( 請輸入一組數(shù)據(jù)的元素個數(shù) :); scanf( %d,N); int *a=new int N+1; printf( 請輸入元素的值 :);

11、 for(int i=1;i=N;i+) scanf(%d,ai); Maxsum(a); delete a; return 0; （2 2 ） 運行結果: : (3) 算法思路: : 其實，我們在選擇一個元素 aj 的時候，只有兩種狀況，將 ai至 至 aj- - 1 加上，或者從 從 aj以 以 j j 為起點開頭。我們用一個數(shù)組 dpi 表示以 i i 為結束的最大子段和，對于每一個 a i ，加上 dpi- - 1 成為子段，或以 ai 開頭成為新段的起點。由于我們只需要記錄 p dp 值，所以簡單度是 O(n) 。 這就是最大子段和的動態(tài)規(guī)劃算法。 我們甚至不需要 p dp 數(shù)組，只

12、需要定義一個 p dp 變量，由于最終要求的 p dp 值也是最大的，所以我們可以在求 p dp 的時候更新為最大的。 提高題一： 用動態(tài)規(guī)劃法求解 1 0/1 背包問題 一、試驗要求與目的 1、 、 把握動態(tài)規(guī)劃算法求解問題的一般特征和步驟。 2、 、 使用動態(tài)規(guī)劃法編程，求解 1 0/1 背包問題。 二、試驗內容 1、 、 問題描述：給定 n n 種物品和一個背包，物品 i i 的重 量是 W i i ，其價值為 V V i i ，問如何選擇裝入背包的物品，使得裝入背包的物品的總價值最大？ 2、 、 算法描述。 3、 、 程序實現(xiàn)；給出實例測試結果。 三 .(1) 試驗源代碼: : / 用

13、動態(tài)規(guī)劃的方法求解 1 0/1 背包問題 / 要求: : /input:n 表示總共有 n n 種物品 / W 表示每種物品的重量 / V 表示每種物品的價值 / c 表示背包的容量 #includebits/stdc+.h using namespace std; int n,c; int dp10051005; ; void Knapsack(int V,int W,int c,int n,int dp1005) int i,j; int jMax=min(Wn- - 1,c); / 這里必需是 Wn- -, 1, 否則，在 Wn- - 1 時刻也是合法狀況; for(j=0;j=jMax

14、;j+) dpnj=0; /i=n,jwn; for(j=Wn;j=c;j+) dpnj=Vn; for(i=n- -1 1 ;i1;i- -) ) jMax=min(Wi- - 1,c); for(j=0;j=jMax;j+) dpij=dpi+1j; / 若小于當前的背包涵量，則不裝入; for(j=Wi;j=c;j+) dpij=max(dpi+1j,dpi+1j- - Wi+Vi); / 比較裝入的代價，謀求最大代價; dp1c=dp2c; if(c=W1) dp1c=max(dp1c,dp2c- - W1+V1); void Traceback(int dp1005,int W,in

15、t c,int n,int x) x /x 數(shù)組用來存放是否第 i i 個元素被裝栽進來 for(int i=1;in;i+) if(dpic=dpi+1c) xi=0; else xi=1; c=c- - Wi; x x n=(dpnc)?1:0; for(int i=1;i=n;i+) if(xi=1) printf( 第d %d 個物品裝入 n,i); int main() printf( 請輸入物品的數(shù)量和背包的容量 :); scanf(%d %d,n,c); int *W=new int n; int *V=new int n; int *x=new int n; W0=0,V0=0

16、,x0=0; printf( 請輸入每個物品的重量: : n); for(int i=1;i=n;i+) scanf(%d,Wi); printf( 請輸入每個物品的價值: : n); for(int i=1;i=n;i+) scanf(%d,Vi); Knapsack(V,W,c,n,dp); Traceback(dp,W,c,n,x); return 0; (2) 運行結果: : (3) 算法思路： 令 V(i,j)表示在前 i(1=i=n)個物品中能夠裝入容量為就 j(1=j=C)的背包中的物品的最大價值，則可以得到如下的動態(tài)規(guī)劃函數(shù): (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) jw i V(i,j)=maxV(i-1,j) ,V(i-1,j-w i )+v i ) jw i (1)式表明：假如第 i 個物品的重量大于背包的容量，則裝人前 i 個物品得到的最大價值和裝入