5/5動(dòng)態(tài)規(guī)劃算法實(shí)驗(yàn)報(bào)告材料實(shí)驗(yàn)標(biāo)題

1、矩陣連乘

2、最長(zhǎng)公共子序列

3、最大子段和

4、凸多邊形最優(yōu)三角剖分

5、流水作業(yè)調(diào)度

6、0-1背包問(wèn)題

7、最優(yōu)二叉搜索樹(shù)

實(shí)驗(yàn)?zāi)康恼莆談?dòng)態(tài)規(guī)劃法的基本思想和算法設(shè)計(jì)的基本步驟。

實(shí)驗(yàn)內(nèi)容與源碼1、矩陣連乘

#include

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)cerrw;

intp[w],s[w][w];

cout>p[0]>>p[1];

for(inti=2;i>p[i-1]>>p[i];

if(p[i-1]!=m)

{

cout

#include

#defineN100

usingnamespacestd;

//str1存儲(chǔ)字符串x，str2存儲(chǔ)字符串y

charstr1[N],str2[N];

//lcs存儲(chǔ)最長(zhǎng)公共子序列

charlcs[N];

//c[i][j]存儲(chǔ)str1[1...i]與str2[1...j]的最長(zhǎng)公共子序列的長(zhǎng)度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]=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];

}

//求出最長(zhǎng)公共子序列

char*getLCS(char*x,char*y,intlen,char*lcs){

inti=strlen(x);

intj=strlen(y);

while(i

i--;

j--;

}

elseif(flag[i][j]==1)

i--;

else

j--;

}

returnlcs;

}

intmain()

{

inti;

cout>str1;

cout0?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

usingnamespacestd;

intMaxSum(int*a,intn)

{

intsum=0,b=0;

for(inti=1;i0)b+=a[i];

elseb=a[i];

if(b>sum)sum=b;

}

returnsum;

}

intmain()

{

inta[8]={2,-3,-5,4,1,7,1,-5};

cout

#defineN50

usingnamespacestd;

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;

cout0)

{

p=p+1;

}

elseif(total[k]0

exit(1);

}

}

}

boolminWeightTriangulation()//計(jì)算最優(yōu)值算法

{

intM;

int**t,**s;

point*v;

for(inti=1;in;

Jobtype*d=newJobtype[N];

a=newint[N];

b=newint[N];

c=newint[N];

cout>d[i].index>>d[i].key;

}

cout1;i--)

{

jMax=min(w[i]-1,c);

for(intj=0;j>w[i];

cout>v[i];

knapsack(m,N,C,w,v);

traceback(m,N,C,x,w);

cout::max();//double的最大值

//a[i]為結(jié)點(diǎn)i被訪問(wèn)的概率

//b[i]為“虛結(jié)點(diǎn)”i被訪問(wèn)的概率

//m[i][j]用來(lái)存放子樹(shù)（i，j）的期望代價(jià)

//w[i][j]用來(lái)存放子樹(shù)（i，j）的所有結(jié)點(diǎn)（包括虛結(jié)點(diǎn)）的a,b概率之和//s[i][j]用來(lái)跟蹤root的

voidOptimalBinarySearchTree(double*a,double*b,intn)

{

ints[N][N];

doublem[N][N];

doublew[N][N];

inti,j,l,r;

for(i=1;i>n;

cout>a[i];

sum+=a[i];

}

cout<<"請(qǐng)輸入每個(gè)虛擬鍵的概率："<<endl;

for(i=0;i0.01)

{

cout<<"輸入的概率和不為1,請(qǐng)重新輸入"<<endl;

}

co