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

《動(dòng)態(tài)規(guī)劃算法實(shí)驗(yàn)報(bào)告》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、實(shí)驗(yàn)標(biāo)題1、矩陣連乘2、最長公共子序列3、最大子段和4、凸多邊形最優(yōu)三角剖分5、流水作業(yè)調(diào)度6、0-1背包問題7、最優(yōu)二叉搜索樹實(shí)驗(yàn)?zāi)康恼莆談?dòng)態(tài)規(guī)劃法的基本思想和算法設(shè)計(jì)的基本步驟。實(shí)驗(yàn)內(nèi)容與源碼1、矩陣連乘#include#includeusingnamespacestd;constintsize=4;//ra,ca和rb,cb分別表示矩陣A和B的行數(shù)和列數(shù)voidmatriMultiply(inta[][4],intb[][4],intc[][4],intra,intca,intrb,intcb){if(ca!=rb)cerr<<"矩陣不可

2、乘";for(inti=0;i

3、*p[i]*p[j];s[i][j]=i;for(intk=i+1;k

4、;}}intmain(){intw;cout<<"矩陣個(gè)數(shù)：";cin>>w;intp[w],s[w][w];cout<<"輸入矩陣A1維數(shù)：";cin>>p[0]>>p[1];for(inti=2;i<=w;i++){intm=p[i-1];cout<<"輸入矩陣A"<>p[i-1]>>p[i];if(p[i-1]!=m){cout<#include

5、#defineN100usingnamespacestd;//str1存儲(chǔ)字符串x，str2存儲(chǔ)字符串ycharstr1[N],str2[N];//lcs存儲(chǔ)最長公共子序列charlcs[N];//c[i][j]存儲(chǔ)str1[1...i]與str2[1...j]的最長公共子序列的長度intc[N][N];//flag[i][j]==0為str1[i]==str2[j]//flag[i][j]==1為c[i-1][j]>=s[i][j-1]//flag[i][j]==-1為c[i-1][j]

6、x,char*y){inti,j;//分別取得x,y的長度intm=strlen(x);intn=strlen(y);for(i=1;i<=m;i++)c[i][0]=0;for(i=0;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;flag[i][j]=0;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];flag[i][j]=1;}else{c[i][j]=c[i][j-1];flag[i]

7、[j]=-1;}}returnc[m][n];}//求出最長公共子序列char*getLCS(char*x,char*y,intlen,char*lcs){inti=strlen(x);intj=strlen(y);while(i&&j){if(flag[i][j]==0){lcs[--len]=x[i-1];i--;j--;}elseif(flag[i][j]==1)i--;elsej--;}returnlcs;}intmain(){inti;cout<<"請輸入字