《動態(tài)規(guī)劃算法 第四章 試驗報告》由會員分享，可在線閱讀，更多相關(guān)《動態(tài)規(guī)劃算法 第四章 試驗報告（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、實驗報告 實驗目的：理解動態(tài)規(guī)劃的基本思想，理解動態(tài)規(guī)劃算法的兩個基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題的重疊性質(zhì)。熟練掌握典型的動態(tài)規(guī)劃問題。掌握動態(tài)規(guī)劃思想分析問題的一般方法，對較簡單的問題能正確分析，設(shè)計出動態(tài)規(guī)劃算法，并能快速編程實現(xiàn)。 實驗內(nèi)容：編程實現(xiàn)講過的例題：最長公共子序列問題、矩陣連乘問題、凸多邊形最優(yōu)三角剖分問題、電路布線問題等。本實驗中的問題，設(shè)計出算法并編程實現(xiàn)。 實驗過程： 1. 最長公共子序列問題 1.1問題描述 若給定序列X=，則另一序列Z=是X的子序列是指存在一個嚴格遞增的下標序列

2、 ik>，使得對于所有j=1,2,…,k有 即求它們的公共子序列。 1.2算法分析 設(shè)序列X=和Y=的一個最長公共子序列Z=，則： i. 若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列； ii. 若xm≠yn且zk≠xm ，則Z是Xm-1和Y的最長公共子序列； iii. 若xm≠yn且zk≠yn ，則Z是X和Yn-1的最長公共子序列。 其中Xm-1=，Yn-1=，Zk-1=

3、z2, …, zk-1>。 最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 用c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=，Yj=。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故c[i,j]=0。建立遞歸關(guān)系如下： 1.3程序框圖 1.4程序源代碼 #include #include<

4、string.h> int lcs_length(char x[], char y[]); int main() { char x[100],y[100]; int len,i,n; scanf("%d",&n); for(i=0;i

5、 n=strlen(y); for(i=0;il[i-1][j]) l[i][j]=l[i][j-1]; else l[i][j]=l[i-1][j]; return

6、 l[m][n]; } 2. 矩陣連乘積問題 2.1問題描述 矩陣A和B可乘的條件是矩陣A的列數(shù)等于矩陣B的行數(shù)。 若A是一個p×q的矩陣，B是一個q×r的矩陣，則其乘積C=AB是一個p×r的矩陣。由該公式知計算C=AB總共需要pqr次的數(shù)乘。其標準計算公式為： 若給定n個矩陣{A1,A2,…,An}。其中Ai與Ai+1是可乘的，i=1,2,…,n-1。要求計算出這n個矩陣的連乘積A1A2…An。使得數(shù)乘的次數(shù)最少。 2.2算法思想 應用動態(tài)規(guī)劃，得到 遞歸公式： 2.3程序框圖

7、 2.4程序源代碼 #include int N; void main() { int p[101],i,j,k,r,t,v,n; int m[101][101]; //為了跟講解時保持一致數(shù)組從1開始 int s[101][101]; //記錄從第i到第j個矩陣連乘的斷開位置 scanf("%d",&N); for(v=0;v

8、 for(i=0;i<=n;i++) scanf("%d",&p[i]); //讀入p[i]的值(注意：p[0]到p[n]共n+1項) for(i=1;i<=n;i++) //初始化m[i][i]=0 m[i][i]=0; for(r=1;r

9、-1]*p[i]*p[j]; //給m[i][j]賦初值 s[i][j]=i; for(k=i+1;k

10、馬問題 3.1問題描述 田忌與齊王賽馬，雙方各有n匹馬參賽（n<=100），每場比賽賭注為1兩黃金，現(xiàn)已知齊王與田忌的每匹馬的速度，并且齊王肯定是按馬的速度從快到慢出場，現(xiàn)要你寫一個程序幫助田忌計算他最好的結(jié)果是贏多少兩黃金（輸用負數(shù)表示）。 3.2算法思想 先排序，齊王的馬的速度放在數(shù)組a中，田忌的馬的速度放在數(shù)組b中。本問題應用的算法是動態(tài)規(guī)劃和貪心算法相結(jié)合解決的。從兩人的最弱的馬入手： 若田忌的馬快，就讓這兩匹馬比賽； 若田忌的馬慢，干脆就讓他對付齊王最快的馬； 若兩匹馬的速度相等，這時有兩種選擇方案，或者它倆比賽，或者對付齊王最快的馬。 定義子問題：l(i，j)為齊王

11、的從第i匹馬開始的j匹馬與田忌的最快的j匹馬比賽，田忌所獲得的最大收益。 則： 程序具體實現(xiàn)時，為了適合c數(shù)據(jù)從0開始，稍加變動，定義子問題：l(i，j)為齊王的從第i匹馬開始到第i＋j匹馬共j+1匹馬與田忌的最快的j+1匹馬比賽，田忌所獲得的最大收益。初始化時：l[i][0]表示齊王的第i匹馬與田忌最快的馬比賽的結(jié)果。 3.3程序框圖 3.4程序源代碼 #include v

12、oid readdata(); void init(); int N,n,a[100],b[100],l[100][100]; void main() { int i,j,k; scanf("%d",&N);//測試例子得個數(shù) for(k=0;k=0;i--) for(j=1;j

13、f(a[i+j]>b[j]) l[i][j]=l[i+1][j-1]-1; else if(l[i+1][j-1]-1>l[i][j-1]) l[i][j]=l[i+1][j-1]-1; else l[i][j]=l[i][j-1]; printf("%d\n",l[0][n-1]); } } void readdata() { int i; scanf("%d",&n);//馬的個數(shù)：- for(i=0;i

14、的速度； for(i=0;i

15、 init() { int i; qsort(a,n); qsort(b,n); for(i=0;i