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

實(shí)驗(yàn)標(biāo)題實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容與源碼1、矩陣連乘2、最長公共子序列3、最大子段和4、凸多邊形最優(yōu)三角剖分5、流水作業(yè)調(diào)度6、0-1背包問題7、最優(yōu)二叉搜索樹實(shí)驗(yàn)標(biāo)題實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容與源碼1、矩陣連乘#include<iostream>#include<cstdlib>usingnamespacestd;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<<"矩陣不可乘”；for(inti=0;i<ra;i++)for(intj=0;j<cb;j++){intsum=a[i][0]*b[0][j];for(intk=1;k<ca;k++)sum+=a[i][k]*b[k][j];c[i][j]=sum;}}voidMatrixChain(int*p,intn,intm[][4],ints[][4]){for(inti=1;i<=n;i++)m[i][i]=0;//對(duì)角線for(intr=2;r<=n;r++)//夕卜維for(inti=1;i<=n-r+1;i++)//上三角{intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}voidTraceback(inti,intj,ints[][4]){if(i==j){cout<<"A"<<i;}elseif(i+1==j){cout<<"(A"<<i<<"A"<<j<<")";}else{cout<<"(";Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout<<")";}}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"<<i<<"維數(shù)：";cin>>p[i-1]>>p[i];if(p[i-1]!=m){cout<<endl<<"維數(shù)不對(duì)，矩陣不可乘！"<<endl;exit(1);}}Traceback(1,w,s);return0;運(yùn)行結(jié)果Il'II：值法試。也\卸車連乘1.exe|gji0矩陣八■數(shù)：3陶入擔(dān)陣皿維數(shù)：礦3后俞人村陣M維數(shù):3'4葡入炬陣監(jiān)維數(shù)：45（（MA2）A3）2、最長公共子序列#include<cstring>#include<iostream>#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]<s[i][j-1]intflag[N][N];〃求長度intLCSLength(char*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;}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][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<<"請(qǐng)輸入字符串x："<<endl;cin>>str1;cout<<"請(qǐng)輸入字符串y："<<endl;cin>>str2;intIcsLen=LCSLength(str1,str2);cout<<"最長公共子序列長度："<<lcsLen<<endl;char*p=getLCS(str1,str2,lcsLen,lcs);cout<<"最長公共子序列為：";for(i=0;i<lcsLen;i++)cout<<lcs[i]<<"";return0;}運(yùn)行結(jié)果i-1法m曰d或公共子朝I.*請(qǐng)輸入字符串，:Abcdefghseabcf請(qǐng)輔魏字符串了：sesbcfgi最長公共子序舛氏度：6S'長公其子瘁列如，亦hcf3、最大子段和//分治法求最大子段和#include<iostream>usingnamespacestd;intMaxSubSum(int*a,intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{intcenter=(left+right)/2;//最大子段和在左邊intleftsum=MaxSubSum(a,left,center);//最大子段和在右邊intrightsum=MaxSubSum(a,center+1,right);//最大子段和在中間ints1=0;intlefts=0;for(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}ints2=0;intrights=0;for(inti=center+1;i<=right;i++){rights+=a[i];if(rights>s2)s2=rights;}sum=s1+s2;//前后子段和相加//判斷最大子段和if(sum>leftsum)sum=leftsum;if(sum>rightsum)sum=rightsum;}returnsum;}intMaxSum(int*a,intn){returnMaxSubSum(a,1,n-1);}intmain(){inta[8]={2,-3,-5,4,1,7,1,-5};cout<<"最大子段和為："<<MaxSum(a,8);return0;}〃動(dòng)態(tài)規(guī)劃法#include<iostream>usingnamespacestd;intMaxSum(int*a,intn){intsum=0,b=0;for(inti=1;i<n;i++)//此處不能=n,{if(b>0)b+=a[i];elseb=a[i];if(b>sum)sum=b;}returnsum;intmain(){inta[8]={2,-3,-5,4,1,7,1,-5};cout<<"最大子段和為："<<MaxSum(a,8);return0;}運(yùn)行結(jié)果最大手段口垣13ProcessTeti_nrtied0(.0x0)executionPim日:6.274sPress:mykeytoccn+inue.4、凸多邊形最優(yōu)三角剖分#include<iostream>#include<cmath>#include<cstdlib>#defineN50usingnamespacestd;structpoint{intx;inty;};intdistance(pointX,pointY)//兩點(diǎn)距離{intdis=(Y.x-X.x)*(Y.x-X.x)+(Y.y-X.y)*(Y.y-X.y);return(int)sqrt(dis);}intw(pointa,pointb,pointc)//權(quán)值{returndistance(a,b)+distance(b,c)+distance(a,c);}boolJudgeInput()//判斷是否能構(gòu)成凸多邊形{point*v;〃記錄凸多邊形各頂點(diǎn)坐標(biāo)int*total;〃記錄坐標(biāo)在直線方程中的值intm,a,b,c;cout<<”請(qǐng)輸入凸多邊形頂點(diǎn)個(gè)數(shù)：”；cin>>m;intM=m-1;for(inti=0;i<m;i++){cout<<"輸入頂點(diǎn)v"<<i<<"的坐標(biāo)：”；cin>>v[i].x>>v[i].y;}//根據(jù)頂點(diǎn)坐標(biāo)判斷是否能構(gòu)成一個(gè)凸多邊形for(intj=0;j<m;j++){intp=0;intq=0;if(m-1==j){a=v[m-1].y-v[0].y;b=v[m-1].x-v[0].y;c=b*v[m-1].y-a*v[m-1].x;}else{a=v[j].y-v[j+1].y;b=v[j].x-v[j+1].x;c=b*v[j].y-a*v[j].x;}for(intk=0;k<m;k++){total[k]=a*v[k].x-b*v[k].y+c;if(total[k]>0){p=p+1;}elseif(total[k]<0){q=q+1;}}if((p>0&&q>0)II(p==0&&q==0)){cout<<"無法構(gòu)成凸多邊形！"vvendl;exit(1);boolminWeightTriangulation()//計(jì)算最優(yōu)值算法{intM;int**t,**s;point*v;for(inti=1;i<=M;i++)t[i][i]=0;for(intr=2;r<=M;r++)for(inti=1;i<=M-r+1;i++){intj=i+r-1;t[i][j]=t[i+1][j]+w(v[i-1],v[i],v[j]);s[i][j]=i;for(intk=i+1;k<i+r-1;k++){intu=t[i][k]+t[k+1][j]+w(v[i-1],v[k],v[j]);if(u<t[i][j]){t[i][j]=u;s[i][j]=k;}}}returntrue;}voidTraceback(inti,intj,int**s){if(i==j)return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout<<"三角形：v”vvi-1vv”v”vvs[i][j]vv”v”vvjvvendl;}intmain(){int**s;〃記錄最優(yōu)三角剖分中所有三角形信息int**t;〃記錄最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值point*v;〃記錄凸多邊形各頂點(diǎn)坐標(biāo)int*total;〃記錄坐標(biāo)在直線方程中的值intM=0;t=newint*[N];s=newint*[N];

for(inti=0;i<N;i++){t[i]=newint[N];s[i]=newint[N];}v=newpoint[N];total=newint[N];if(JudgeInput()){if(minWeightTriangulation()){Traceback(1,M,s);cout<<endl;cout<<"最優(yōu)權(quán)值之和為："<<t[1][M]<<endl;}}return0;}運(yùn)行結(jié)果：尊法\匚混乎3,5口爹邊形最優(yōu)三定劑分難]?1夜頂頂頂吸頂形形形形形AAA人人A人角角角角角輸輸輜輸輸輸輸二------------生坐V2ME詞W

囹的VI崩展屹V4

V5詭V3展V3V4V32]?1夜頂頂頂吸頂形形形形形AAA人人A人角角角角角輸輸輜輸輸輸輸二------------生坐V2ME詞W

囹的VI崩展屹V4

V5詭V3展V3V4V32166O0012￡22L0275Bo-o-L2215、流水作業(yè)調(diào)度#include<iostream>#defineN100usingnamespacestd;classJobtype{public:/*intoperator<=(Jobtypea)const{return(key<=a.key);}*/intkey;intindex;booljob;};voidsort(Jobtype*d,intn){inti,j;Jobtypetemp;boolexchange;//交換標(biāo)志for(i=0;i<n;i++){//最多做n-1趟排序exchange=false;//本趟排序開始前，交換標(biāo)志應(yīng)為假for(j=n-1;j>=i;j--)if(d[j+1].key<d[j].key){temp=d[j+1];d[j+1]=d[j];d[j]=temp;exchange=true;//發(fā)生了交換，故將交換標(biāo)志置為真}if(!exchange)//本趟排序未發(fā)生交換，提前終止算法return;}}intFlowShop(intn,int*a,int*b,int*c){Jobtype*d=newJobtype[n];for(inti=0;i<n;i++)//初始化{d[i].key=a[i]>b[i]?b[i]:a[i];//執(zhí)行時(shí)間d[i].job=a[i]<=b[i];//作業(yè)組d[i].index=i;//作業(yè)序號(hào)}sort(d,n);;intj=0;intk=n-1;for(inti=0;i<n;i++)//最優(yōu)調(diào)度{if(d[i].job){c[j++]=d[i].index;}else{c[k--]=d[i].index;}}j=a[c[0]];k=j+b[c[0]];for(inti=1;i<n;i++){j+=a[c[i]];k=j<k?k+b[c[i]]:j+b[c[i]];}deleted;//回收空間returnk;//返回調(diào)度時(shí)間}intmain(){intn,*a,*b,*c;cout<<"作業(yè)數(shù)：”；cin>>n;Jobtype*d=newJobtype[N];a=newint[N];b=newint[N];c=newint[N];cout<<"請(qǐng)輸入作業(yè)號(hào)和時(shí)間：”；for(inti=0;i<n;i++){cin>>d[i].index>>d[i].key;}cout<<endl;intk=FlowShop(n,a,b,c);cout<<"\n調(diào)度時(shí)間："<<k<<endl;cout<<”最優(yōu)調(diào)度序列:”；for(inti=0;i<n;i++)//輸出最優(yōu)調(diào)度序列{cout<<c[i]<<"";}return0;}運(yùn)行結(jié)果:1?任\?法\cc?d巳流水作業(yè)調(diào)度白口叵IS3作業(yè)數(shù)：4請(qǐng)輸乳作業(yè)號(hào)和時(shí)間:091.2267調(diào)度時(shí)間己SS5S1S6易優(yōu)誦度序列：2'30.1Processreturned/0.(Ok0)■eKeci_i+rLiti+utla!27.283sPress:iiiykeytocontitiue.<|串|h6、0-1背包問題#include<iostream>#include<iomanip>usingnamespacestd;constintC=10;//容量constintN=5;//個(gè)數(shù)intmax(constinta,constintb){returna>b?a:b;}intmin(constinta,constintb){returna<b?a:b;}/*m為記錄數(shù)組m[i][j]代表在剩有j容量的條件下，從i開始往后的物品中可以取得的最大價(jià)值w為重量數(shù)組，v為價(jià)值數(shù)組n為物品個(gè)數(shù)，c為開始容量則m[1][c]即此背包能剩下的最大價(jià)值*/voidknapsack(int**m,intn,intc,int*w,int*v){intjMax=min(w[n]-1,c);//前n-1個(gè)物品for(intj=0;j<=jMax;j++)m[n][j]=0;for(intj=w[n];j<=c;j++)m[n][j]=v[n];for(inti=n-1;i>1;i--){jMax=min(w[i]-1,c);for(intj=0;j<=jMax;j++)m[i][j]=m[i+1][j];for(intj=w[i];j<=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}〃找出最優(yōu)解，0表示不能裝，1表示能裝voidtraceback(int**m,intn,intc,int*x,int*w){for(inti=1;i<n;i++){if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}}x[n]=(m[n][c]==0)?0:1;}intmain(){int*v=newint[N+1];int*w=newint[N+1];int**m=newint*[N+1];int*x=newint[N+1];for(inti=0;i<N+1;i++){m[i]=newint[C+1];}cout<<"輸入重量序列,"<<N<<"個(gè)"<<endl;for(inti=1;i<=N;i++)cin>>w[i];cout<<"輸入價(jià)值序列,"<<N<<"個(gè)"<<endl;for(inti=1;i<=N;i++)cin>>v[i];knapsack(m,N,C,w,v);traceback(m,N,C,x,w);cout<<"最優(yōu)值："<<m[1][C]<<endl;cout<<"是否裝入背包的情況："；for(inti=1;i<=N;i++){cout<<x[i];}for(inti=0;i<N+1;i++){deletem[i];}delete[]m;return0;}運(yùn)行結(jié)果!■'Il:\HJS\cade\3.1D0-1問題.段:…|d||回輸入重量序列「5個(gè)15245.愉M介值序列,淤34271最優(yōu)值；14是否裝氏苜包的情況；11§1。Fiocbssieturned0（0k!?）eKeGutiontime；12.726sI,In.i|?7、最優(yōu)二叉搜索樹#include<iostream>#include<cmath>#include<limits>#defineN100usingnamespacestd;constdoubleMAX=numeric_limits<double>::max();//double的最大值//a[i]為結(jié)點(diǎn)i被訪問的概率//b[i]為“虛結(jié)點(diǎn)”i被訪問的概率//m[i][j]用來存放子樹(i，j)的期望代價(jià)//w[i][j]用來存放子樹(i，j)的所有結(jié)點(diǎn)(包括虛結(jié)點(diǎn))的a,b概率之和//s[i][j]用來跟蹤root的voidOptim