动态规划算法实验报告

4/4动态规划算法实验报告动态规划算法实验报告

————————————————————————————————:————————————————————————————————日期:

实验标题

1、矩阵连乘

2、最长公共子序列３、最大子段和

4、凸多边形最优三角剖分

5、流水作业调度

6、0－１背包问题

7、最优二叉搜索树

实验目的掌握动态规划法的基本思想和算法设计的基本步骤。

实验内容与源码1、矩阵连乘

#inclｕde

usiｎgｎamｅspacestd;

ｃｏnｓtｉntsize＝4;

//ra，ｃa和rb,cb分别表示矩阵A和Ｂ的行数和列数

vｏidmatriMuｌtiply(ｉnta［][4],intb[]［4]，iｎtｃ[]［４],ｉntｒａ，ｉｎtｃa,intrb,intcb)

{

ｉf(ｃａ!=rｂ)cerr>p[0]＞>p[１］;

fｏr(iｎｔi=2；i＜=w;i＋+)

{

ｉntm=p[i－1]；

cｏut＜>ｐ[i-1]>>p[i];

if(p[i-1]！＝ｍ)

{

couｔ

#inｃｌuｄe

＃defineN1０0

uｓingnameｓpaｃestd;

//ｓtr1存储字符串x，str2存储字符串y

ｃｈarstr1［Ｎ］,str２［N];

/／ｌcs存储最长公共子序列

cｈaｒlｃs[N]；

/／ｃ[i][j]存储stｒ1［１...i]与str２［１..．j］的最长公共子序列的长度intc［N][N];

／/fｌag[ｉ］[j]=＝0为str1[i]==stｒ2[j]

//flａg[i][j]==1为c［i－1][ｊ]>＝s[i］[j－1]

//flag［i][ｊ]==-1为ｃ[i-1]［j]=c[i][j-1])

｛

ｃ［i][ｊ］=ｃ[i-1][ｊ]；

flａg[ｉ］[j]＝1;

}

ｅlse

{

c[ｉ］[j］=c[i][ｊ-1];

ｆlａｇ［i]［j]=-１;

}

}

ｒeｔｕｒnｃ[m][n];

}

//求出最长公共子序列

char＊getLＣＳ(cｈar＊x,char＊y,inｔｌen，ｃｈａr＊ｌcs){

iｎti=sｔrleｎ(x);

intj=ｓtrlｅｎ(y);

ｗhile(i

j--;

}

elseif(ｆlaｇ［ｉ]［ｊ］==1)

i－-;

else

j--;

}

returｎlｃs；

}

ｉnｔｍaiｎ()

{

intｉ;

couｔ＜＜＂请输入字符串x:">str1;

cout=leｆt;i--）

{

lｅｆts+＝ａ[i];

ｉf(lefts>ｓ1)ｓ1=leftｓ;

}

ints2＝０；

intrights=0;

foｒ(inti=ｃenteｒ+1;is2)s2＝riｇｈtｓ;

}

sum=ｓ1+s２;/／前后子段和相加

／/判断最大子段和

if(suｍ＞lｅftsｕm)ｓum=leftｓuｍ;

if（sｕm>rｉghｔｓum)suｍ＝rightsum;

}

ｒetuｒnsum;

｝

intＭaｘＳuｍ(int＊a,intn)

{

reｔｕrnＭaxSuｂＳum（a,1,n-1);

}

iｎtmａｉn()

{

inta［8]=｛2,-３，-5,4,1，7,1，-5｝;

cｏｕｔｎ;

Ｊobtypｅ*d=ｎewJobtｙpe[N]；

a＝nｅwint[N];

b=newiｎｔ[N];

c=neｗinｔ［Ｎ];

cout>d[ｉ].ｉndex>>d[ｉ］.keｙ；

｝

cout=w［1］）

m[1][c]=mａx(m［1][c],m[2]［c-w[1]]+v[1］);

}

/／找出最优解,0表示不能装，１表示能装

vｏｉdtraｃeback(iｎt*＊m,intn,ｉntc，ｉnｔ＊ｘ,int*w)

{

foｒ(iｎｔi=１；i>w[i］；

cout

#incｌｕｄe：:maｘ();//double的最大值

//ａ[ｉ]为结点i被访问的概率

//b[i］为“虚结点”i被访问的概率

／/ｍ[i］[j]用来存放子树（ｉ,ｊ）的期望代价

//w［i][ｊ]用来存放子树(i,j）的所有结点（包括虚结点)的a,ｂ概率之和

//s[ｉ][j]用来跟踪root的

voidOptiｍalBｉnａｒｙSｅａｒcｈTree（doublｅ*ａ,doｕble*b,intn)

{

iｎts［N][Ｎ］;

ｄoｕｂlｅｍ[N][N];

ｄoublew[Ｎ][Ｎ];

inti,ｊ,l,r；

foｒ（i=1;in;

ｃouｔ＜＞a[i］；

sｕｍ+=a[i];

}

cout>b[i］；

sum+=ｂ［i］；

}

ｉf(aｂs(ｓｕm-1）＞0．01)

｛

ｃout<<"输入的概率和不为1，请重新输入"＜＜ｅnｄl;

}

cｏut＜<"最优二叉查找树的期望搜索代价为:";

Opｔ