文档介绍：学号 11770215
《算法设计与分析》
实验报告四
学生姓名
王志勇
专业、班级
软件2班
指导教师
唐国峰
成绩
计算机与信息工程学院软件工程系2013 年 11月 19日
实验四:动态规划运用练习
一、实验目的
本次实验是针对动态规划算法的算法设计及应用练习,旨在加深学生对该算法原理的理解,提高学生运用该算法解决问题的能力。
二、实验步骤与要求
;
;
,用统一的实验报告模板编写实验报告。
:
(1)电子版提交说明:
a 需要提交Winrar压缩包,文件名为“《算法设计与分析》实验一_学号_姓名”,
如“《算法设计与分析》实验一_09290101_张三”。
b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹,
其下为两个文件夹,一个文件夹命名为“源程序”,另一个文件夹命名为“实验
报告电子版”。其下分别放置对应实验成果物。
(2)打印版提交说明:
a 不可随意更改模板样式。
b 字体:中文为宋体,大小为10号字,英文为Time New Roman,大小为10号
字。
c 行间距:单倍行距。
(3)提交截止时间:2013年11月24日16:00。
实验项目
。
题目列表如下:
矩阵连乘问题
最长公共子序列
最大字段和
0—1背包问题
实验过程
(一)题目:矩阵连乘问题的算法设计与实现
题目分析
求矩阵连乘最优解就是求n个矩阵在可以连乘的情况下(矩阵可以连乘的条件是:第i+1个矩阵的行数要和第i个矩阵的列数相等)求出矩阵连乘积最小的运算顺序。用动态规划算法解决最优问题关键是求出k的位置(矩阵断开或者括号的位置),则可分情况考虑,具体算法构造如下。
算法构造
设矩阵A【i:j】,1<=i<=j<=n;所需的最少乘次数m[i][j].
M[i][j]=0 i=l
M[i][j]=min{m[i][k]+m[k+1][j]+pi-1pkpj}(i<=k<j) i<j
依次次序:先计算A【1:k】和A【k+1:n】,然后将计算结果相乘得到A【1:n】,依次计算顺序总金算量为A【1:k】的计算量加上A【k+1:n】的计算量,再加上A【1:k】和A【k+1:n】相乘的计算量。
算法实现
#include <iostream> // 预编译命令
using namespace std;
//*****************************************
void MatrixChain(int *p,int n, int **m,int **s) //计算最优值
{
int i,j,r,k,t;
for(i=1;i<=n;i++)
{
m[i][i]=0;
}
for(r=2;r<=n;r++)
{
for(i=1;i<=n-r+1;i++)
{
j=i+r-1;
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//按照顺序连乘
s[i][j]=i;
for(k=i+1;k<j;k++)//计算从k处断开的乘次
{
t =m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];//比较从k处断开和按顺序连乘的运算量
if(t<m[i][j]) //记录最优断开位置
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}
}
//构造最优解---按顺序由内而外
void Traceback(int i,int j,int **s)
{
if(i==j)
{
return;
}
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout << "Multiply A" << i << "," << s[i][j];
cout << "and A" << (s[i][j]+1) << "," << j <<endl;
}
//主函数
void main()
{
int i;
int n;
int j; //参与连乘的矩阵个数
int *p; //矩阵Ai的列数或Ai-1的行数
int **m; //纪录Ai - Aj的矩阵连乘的最小代价
int **s; //纪录Ai - Aj之间得到最小连乘代价时的分割点
cout << "输入矩阵的个数:" << endl ;