動(dòng)態(tài)規(guī)劃算法章試驗(yàn)報(bào)告

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

2、2,ik>,使得對(duì)于所有j=1,2,k有即求它們的公共子序列。1.2算法分析設(shè)序列X=<x1, x2,xm>和Y=<y1, y2,yn>的一個(gè)最長公共子序列Z=<z1, z2, -zk>，則：i. 若Xm=yn,則Zk=Xm=yn且Zk-1是Xm-1和Y n-1的最長公共子序列；ii. 若XmMy且Zkxn，則Z是X m-1和丫的最長公共子序列；iii. 若XmMy且ZkMy，則Z是X和Yn-1的最長公共子序列。其中 Xm-仁<x1, x2, ,xm1>, Yn-仁<y1, y2, ,yn1> , Zk-仁<z1, z2,

3、zkl>。最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。用ci,j記錄序列Xi和Yj的最長公共子序列的長度。其中 Xi=<x1, x2,xi> Yj=<y1, y2,yj>。當(dāng)i=0或j=0時(shí)，空序列是 Xi和Yj的最長公共子序列，故 ci,j=0。建立遞歸 關(guān)系如下：'0當(dāng)i=0或j =0時(shí)ci,j=t ci -1, j -1 +1當(dāng)i, j >0且Xj=yj時(shí)max® , j -1, ci -1, j p 當(dāng) i, j > 0且Xj 芒 yj時(shí)1.3程序框圖1.4程序源代碼#in clude<stdio.h>#i nclude

4、<stri ng.h>in t lcs_le ngth(char x, char y); int mai n()char x100,y100;int len ,i, n;sea nf("%d",&n);for(i=0;i< n;i+)scan f("%s%s",x,y);len=lcs_le ngth(x,y);prin tf("%dn",le n);in t lcs_le ngth(char x, char y) _int m,n ,i,j,l100100;m=strle n(x);n=strle n(y)

5、;for(i=0;i<m+1;i+)li0=0;for(j=0;j< n+1;j+)l0j=0;for(i=1;i<=m;i+)for(j=1;j<=n ;j+)if(xi-1=yj-1)i,j從1開始，但字符串是從 0開始lij=li-1j-1+1;else if(lij-1>li-1j)lij=lij-1;elselij=li-1j;return lm n;2. 矩陣連乘積問題2.1問題描述矩陣A和B可乘的條件是矩陣 A的列數(shù)等于矩陣 B的行數(shù)。若A是一個(gè)p利的矩陣，B是一個(gè)qM的矩陣，則其乘積 C=AB是一個(gè)p>f的矩陣。由該公式知計(jì)算 C=AB總共需

6、要pqr次的數(shù)乘。其標(biāo)準(zhǔn)計(jì)算公式為：%二£張覘其中1引Sp,若給定n個(gè)矩陣A1,A2,An。其中Ai與Ai+1是可乘的，i=1,2,n1。要求計(jì)算出這 n 個(gè)矩陣的連乘積 A1A2-An。使得數(shù)乘的次數(shù)最少。2.2算法思想應(yīng)用動(dòng)態(tài)規(guī)劃，得到'0i = j遞歸公式：mij=.r r ir i i + ri +dir i +i -MJ minmik+mk+1j + pi_4PkPj i v ji空叮2.3程序框圖2.4程序源代碼#i nclude<stdio.h>int N; void main()in t p1O1,i,j,k,r,t,v, n; int m1011

7、01;/int s101101;/sca nf("%d",&N); for(v=0;v<N;v+) scan f("%d",&n);為了跟講解時(shí)保持一致數(shù)組從1開始 記錄從第i到第j個(gè)矩陣連乘的斷開位置for(i=0;i<=n ;i+) sca nf("%d",&pi);/讀入pi的值（注意：p0到pn共n+1 項(xiàng))初始化mii=0為i、j相差的值 為行為列for(i=1;i<=n ;i+)/mii=0;for(r=1;r <n ;r+)rfor(i=1;i <n ;i+)/ij=

8、i+r;/j給mij 賦初mij=mi+1j+pi-1*pi*pj;/ sij=i;for(k=i+1;k<j;k+) t=mik+mk+1j+pi-1*pk*pj;if(t<mij)mij=t;/mij取最小值sij=k;prin tf("%dn",m1 n);3. 田忌賽馬問題3.1問題描述田忌與齊王賽馬，雙方各有 n匹馬參賽（*=100 ）,每場比賽賭注為 1兩黃金，現(xiàn)已知 齊王與田忌的每匹馬的速度，并且齊王肯定是按馬的速度從快到慢出場，現(xiàn)要你寫一個(gè)程序幫助田忌計(jì)算他最好的結(jié)果是贏多少兩黃金（輸用負(fù)數(shù)表示）。3.2算法思想先排序，齊王的馬的速度放在數(shù)組a中

9、，田忌的馬的速度放在數(shù)組b中。本問題應(yīng)用的算法是動(dòng)態(tài)規(guī)劃和貪心算法相結(jié)合解決的。從兩人的最弱的馬入手：若田忌的馬快，就讓這兩匹馬比賽；若田忌的馬慢，干脆就讓他對(duì)付齊王最快的馬；若兩匹馬的速度相等，這時(shí)有兩種選擇方案，或者它倆比賽，或者對(duì)付齊王最快的馬。當(dāng) aij-1b：b j-1時(shí)當(dāng)aij-1=b j-1時(shí)當(dāng) aij-1bj-1時(shí)定義子問題：l（i，j）為齊王的從第i匹馬開始的j匹馬與田忌的最快的j匹馬比賽，田忌 所獲得的最大收益。Il(i, j -1)l(i 1, j -1)則：l(i, j) =<maxl(i +1,j 1),l(i,j 1)程序具體實(shí)現(xiàn)時(shí)，為了適合c數(shù)據(jù)從0開始，稍

10、加變動(dòng)，定義子問題： l（i , j）為齊王的從第i匹馬開始到第i + j匹馬共j+1匹馬與田忌的最快的j+1匹馬比賽，田忌所獲得的最大 收益。初始化時(shí)：li0表示齊王的第i匹馬與田忌最快的馬比賽的結(jié)果。3.3程序框圖#i nclude<stdio.h> void readdata();void ini t();int N, n,a100,b100,l100100;void main()int i,j,k;sca nf("%d",&N);測(cè)試?yán)拥脗€(gè)數(shù)for(k=0;k<N;k+)readdata(); in it();for(i=n-2;i>

11、;=0;i-) for(j=1;j <n-i;j+)if(ai+j<bj) lij=lij-1+1； else if(ai+j>bj) lij=li+1j-1-1；else if(li+1j-1-1>lij-1) lij=li+1j-1-1； elselij=lij-1；prin tf("%dn",lO n-1);void readdata()int i;馬的個(gè)數(shù)：-sca nf("%d",&n);/for(i=0;i< n;i+)每只馬的速度；每只馬的速度；對(duì)輸入的馬的速度的無序序列進(jìn)行排序scan f("

12、;%d",&ai);/ for(i=0;i< n;i+)scan f("%d",&bi);/int* qsort(int a100,int n)/int i,j,t;for(i=0;i< n;i+) for(j=i+1;j <n ;j+) if(ai<aj)t=ai;ai=aj;aj=t;/ for(i=0;i< n;i+)/ prin tf("%3d",ai);/ prin tf("n"); return a; void in it()int i;qsort(a, n);qsort(b ,n);for(i=0;i< n;i+)if(ai<b