算法分析动态规划实验报告

重庆大学实验报告

实验题目：

学院：专业班级：年级：姓名：学号：完成时间：月指导教师：

重庆大学教务处制

重庆大学本科学生实验项目任务书

说明：学院、专业、年级均填全称，如：计算机学院、计算机科学与技术、2011。

实验报告正文

主要内容包括：

1算法思想

(a),使用动态规划自下而上方法，定义数组gem[i][j]表示第i排第j列木桩上的宝石数，数组ma_b[i][j]表示从第i排第j列木桩到最后一排木桩所获得的最大宝石数。公式为：

ma_b[i][j]=ma_{gem[i][j]+ma_b[i+1][j-1],gem[i][j]+ma_b[i+1][j],gem[i][j]+ma_b[i+1][j+1]}其中i从n取到1

求ma_b的伪代码如下：

Dynamic-Bottom-To-Up(ma_b,gem,row,line)

for(inti=1;i<=row;i++)

ma_b[line][i]=gem[line][i];初始化ma_bfor(inti=line-1;i=>1;i--)for(intj=row;j>=1;j--)

ma_b[i][j]=ma_{gem[i][j]+ma_b[i+1][j-1],gem[i][j]+ma_b[i+1][j],gem[i][j]+ma_b[i+1][j+1]}

由上述代码可知，最多两个for循环，所以，时间复杂度为O(n2).

(b),用数组path[]记录获得最大价值的路径，思想是自上而下比较每排的ma_b最大值，将位置赋给数组path[]，然后再判断该最大值的下排与之相邻的三个ma_b值，而后重复上面的操作，直到最后一排。

求path的伪代码如下：

path[1]=1因为每次都是从第一排的第一桩开始，所以，path[1]=1n=1;

for(inti=2;i<=line;i++)

ma_{ma_b[i][n-1],ma_b[i][n],ma_b[i][n+1]}

path[i]=n;如果ma_b[i][n]最大，则

n=n-1;

由该代码可知，求path的时间复杂度为O(n)。

2关键代码描述

include

include

usingnamespacestd;

voidmain()

ofstreamoutfile;实验结果读入outfile文件中

ifstreaminfile;实验数据从infile文件中读入

XXX("XXX",ios::trunc);

XXX("XXX",ios::in);

if(infile==NULL)

cout<<"文件内没有内容！";

intline,row;

infile>line;

infile>row;

intgem;

intma_b;数组gem表示柱桩的宝石，数组ma_b表示第i行第j列到最后一行所获得的最大宝石数；

intnum=abs(line-row);

gem=(int)newint[line+num+1];

ma_b=(int)newint[line+num+1];动态为数组gem和ma_b分配空间for(inti=0;i<=line;i++)

gem[i]=newint[row+num+1];

ma_b[i]=newint[row+num+1];

for(inti=1;i<=line;i++)

for(intj=1;j<=row;j++)

infile>gem[i][j];输入柱桩的宝石

for(inti=1;i<=row;i++)

ma_b[line][i]=gem[line][i];初始化ma_b

/ma_b[i][j]=ma_{gem[i][j]+ma_b[i+1][j-1],gem[i][j]+ma_b[i+1][j],gem[i][j]+ma_b[i+1][j+1]}其中i从line取到1

for(inti=line;i>1;i--)

for(intj=row;j>=1;j--)

intn=i-1;

if((gem[n][j]+ma_b[i][j-1])>=(gem[n][j]+ma_b[i][j])(gem[n][j]+ma_b[i][j-1])>=(gem[n][j]+ma_b[i][j+1]))

ma_b[n][j]=gem[n][j]+ma_b[i][j-1];

continue;

}outfile<=ma_b[m][n])(ma_b[m][n-1]>=ma_b[m][n+1])){path[m]=n-1;n=n-1;continue;}if((ma_b[m][n]>=ma_b[m][n-1])(ma_b[m][n]>=ma_b[m][n+1])){path[m]=n;n=n;continue;}if((ma_b[m][n+1]>=ma_b[m][n])(ma_b[m][n+1]>=ma_b[m][n-1])){path[m]=n+1;n=n+1;continue;}}cout<<"打开output文件查看结果！"<=(gem[n][j]+ma_b[i][j-1])(gem[n][j]+ma_b[i][j])>=(gem[n][j]+ma_b[i][j+1])){ma_b[n][j]=gem[n][j]+ma_b[i][j];continue;}if((gem[n][j]+ma_b[i][j+1])>=(gem[n][j]+ma_b[i][j-1])(gem[n][j]+ma_b[i][j+1])>=(gem[n][j]+ma_b[i][j])){ma_b[n][j]=gem[n][j]+ma_b[i][j+1];continue;}

}for(inti=0;i<=line;i++)delete[]gem[i];delete[]gem;for(inti=0;i<=line;i++)delete[]ma_b[i];delete[]ma_b;deletepath;XXX();XXX();

3运行效果

/XXX内的内容

2420

XXX111511XXX213XXXX3211XXXXXXXXX123XXXX075XXXX3145XXXX654XXXX21XXXX8XXXX4663574XXXX7845114XXXX845XXXX67126XXXX876XXXX345678XXXXXX4XXX77777XXXXXXXXX425XXXX42876XXXX345678XXXXXX4XXXXXXXXX88883XXX425XXXX4321XXXX8XXXX4663574XXXX7845114XXXX845XXXX6712

634XXXX75252XXXX8111/XXX内的内容

345(最大价值)

1(第1排位置)2(第2排位置)3(第3排位置)4(第4排位置)5(第5排位置)6(第6排位置)7(第7排位置)8(第8排位置)9(第9排位置)8(第10排位置)7(第11排位置)6(第12排位置)7(第13排位置)8(第14排位置)9(第15排位置)10(第16排位置)11(第17排位置)

12(第18排位置)

13(第19排位置)

14(第20排位置)

13(第21排位置)

14(第22排位置)

15(第23排位置)

16(第24排位置)

4总结(注明每个人的分工和工作量百分比)

本组由2011组成。

2011负责项目的所有部分，所作贡献占工作量的100%。

格式要求

1、学生：提交的实验报告电子文档命名为：“组号（2位数字）年级（两位数字

不要“级”字）专业（缩写：计算机科学与技术专业（计科）、网络工程专业（网络）、信息安全专业（信息）、物联网工程（物联网））项目组成

员（学号（八位数字）姓名）．doc。如第1组，专业为“计算机科学与技术”专业，项目组成员有：张三（学号6），李（学号6），王X（学号6），完成的课程设计报告命名为：01_10计科_6张三_6李_6王X。

2、教师：报告批阅完成后将评价后的实验报告转换为PDF格式文件刻光盘，连

同实验成绩单一起放入试卷袋存档。