动态规划算法实验报告

实验标题

实验目的

1、矩阵连乘 2、最长公共子序列 3、最大子段和 4、凸多边形最优三角剖分 5、流水作业调度 6、0-1背包问题 7、最优二叉搜索树

掌握动态规划法的基本思想和算法设计的基本步骤。 实验内容与源码

1、矩阵连乘

#include #include using namespace std;

const int size=4;

//ra,ca和rb,cb分别表示矩阵A和B的行数和列数

void matriMultiply(int a[][4],int b[][4],int c[][4],int ra ,int ca,int rb ,int cb ) {

if(ca!=rb) cerr<<\矩阵不可乘\ for(int i=0;i

int sum=a[i][0]*b[0][j]; for(int k=1;k

void MatrixChain(int *p,int n,int m[][4],int s[][4]) {

for(int i=1;i<=n;i++) m[i][i]=0;//对角线 for(int r=2;r<=n;r++)//外维 for(int i=1;i<=n-r+1;i++)//上三角 {

int j=i+r-1;

m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i;

for(int k=i+1;k

int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(t

m[i][j]=t; s[i][j]=k; } }

}

}

void Traceback(int i,int j,int s[][4]) {

if(i == j) {

cout<<\ }

else if(i+1 == j)

{

cout<<\ } else

{

cout<<\

Traceback(i,s[i][j],s); Traceback(s[i][j]+1,j,s); cout<<\ } }

int main() {

int w;

cout<<\矩阵个数：\ cin>>w;

int p[w],s[w][w];

cout<<\输入矩阵A1维数：\ cin>>p[0]>>p[1];

for(int i=2 ; i<=w ; i++)

{

int m = p[i-1];

cout<<\输入矩阵A\维数：\ cin>>p[i-1]>>p[i];

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

cout<

Traceback(1,w,s); return 0; }

运行结果

2、最长公共子序列

#include #include #define N 100

using namespace std;

//str1存储字符串x，str2存储字符串y char str1[N],str2[N];

//lcs存储最长公共子序列

char lcs[N];

//c[i][j]存储str1[1...i]与str2[1...j]的最长公共子序列的长度 int c[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]

//求长度

int LCSLength(char *x, char *y) {

int i,j;

//分别取得x,y的长度 int m = strlen(x); int n = 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;

flag[i][j] = 0; }

else if(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; } }

return c[m][n]; }

//求出最长公共子序列

char* getLCS(char *x, char *y,int len,char *lcs) {

int i = strlen(x); int j = strlen(y); while(i&&j) {

if(flag[i][j]==0) {

lcs[--len] = x[i-1]; i--;

j--; }

else if(flag[i][j]==1) i--; else j--; } return lcs; }

int main() {

int i;

cout<<\请输入字符串x：\ cin>>str1;

cout<<\请输入字符串y：\

cin>>str2;

int lcsLen = LCSLength(str1,str2);

cout<<\最长公共子序列长度：\ char *p = getLCS(str1,str2,lcsLen,lcs); cout<<\最长公共子序列为：\ for(i=0;i

return 0; }

运行结果

3、最大子段和

//分治法求最大子段和 #include using namespace std;

int MaxSubSum(int *a,int left,int right) {

int sum=0;

if(left==right) sum=a[left]>0?a[left]:0; else

{

int center = (left+right)/2;

//最大子段和在左边

int leftsum=MaxSubSum(a,left,center);

//最大子段和在右边

int rightsum=MaxSubSum(a,center+1,right);

//最大子段和在中间 int s1=0;

int lefts=0;

for(int i=center;i>=left;i--) {

lefts+=a[i]; if(lefts>s1) s1=lefts; }

int s2=0; int rights=0;

for(int i=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; }

return sum; }

int MaxSum(int *a,int n) {

return MaxSubSum(a,1,n-1); }

int main() {

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

cout<<\最大子段和为：\ return 0; }

//动态规划法 #include using namespace std; int MaxSum(int *a,int n)

{

int sum=0,b=0;

for(int i=1;i

if(b>0) b+=a[i]; else b=a[i]; if(b>sum) sum=b; }

return sum; }

int main()

{

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

cout<<\最大子段和为：\ return 0; }

运行结果

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

#include #include #include #define N 50 using namespace std;

struct point {

int x; int y;

};

int distance(point X, point Y)//两点距离

{

int dis = (Y.x-X.x)*(Y.x-X.x) + (Y.y-X.y)*(Y.y-X.y); return (int)sqrt(dis); }

int w(point a, point b, point c)//权值

{

return distance(a,b) + distance(b,c) + distance(a,c); }

bool JudgeInput()//判断是否能构成凸多边形

{

point *v; //记录凸多边形各顶点坐标 int *total; //记录坐标在直线方程中的值 int m,a,b,c;

cout<<\请输入凸多边形顶点个数：\

cin>>m;

int M = m-1;

for(int i=0 ; i

cout<<\输入顶点v\的坐标：\ cin>>v[i].x>>v[i].y;

}

//根据顶点坐标判断是否能构成一个凸多边形 for(int j=0 ; j

int p = 0; int q = 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(int k=0 ; k

{

total[k] = a * v[k].x - b * v[k].y + c; if(total[k] > 0) {

p = p+1; }

else if(total[k] < 0) {

q = q+1; } }

if((p>0 && q>0) || (p==0 && q==0)) {

cout<<\无法构成凸多边形！\ exit(1); } } }

bool minWeightTriangulation()//计算最优值算法 {

int M;

int **t, **s; point *v;

for(int i=1 ; i<=M ; i++) t[i][i] = 0;

for(int r=2 ; r<=M ; r++)

for(int i=1 ; i<=M-r+1 ; i++) {

int j = i+r-1;

t[i][j] = t[i+1][j] + w(v[i-1],v[i],v[j]); s[i][j] = i;

for(int k=i+1 ; k

{

int u = 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; } } }

return true; }

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<<\三角形：v\}

int main()

{

int **s; //记录最优三角剖分中所有三角形信息 int **t; //记录最优三角剖分所对应的权函数值 point *v; //记录凸多边形各顶点坐标 int *total; //记录坐标在直线方程中的值 int M=0;

t = new int *[N]; s = new int *[N];

for(int i=0 ; i

t[i] = new int[N]; s[i] = new int[N]; }

v = new point[N]; total = new int[N]; if(JudgeInput()) {

if(minWeightTriangulation()) {

Traceback(1,M,s);

cout<

cout<<\最优权值之和为：\ } } return 0; }

运行结果：

5、流水作业调度

#include #define N 100 using namespace std;

class Jobtype {

public:

/* int operator<=(Jobtype a)const {

return(key<=a.key); };

void sort(Jobtype *d,int n) { int i,j;

Jobtype temp;

bool exchange; //交换标志

for(i = 0;i < n;i ++){ //最多做n-1趟排序

exchange = false; //本趟排序开始前，交换标志应为假 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; //发生了交换，故将交换标志置为真 }

if(!exchange) //本趟排序未发生交换，提前终止算法 return; } }

int FlowShop(int n,int *a,int *b,int *c) {

Jobtype *d = new Jobtype[n]; for(int i=0;i

{

d[i].key=a[i]>b[i]?b[i]:a[i];// 执行时间 d[i].job=a[i]<=b[i];// 作业组 d[i].index=i;//作业序号 }

sort(d,n);;

int j=0; int k=n-1;

for(int i=0;i

if(d[i].job) {

c[j++]=d[i].index;

}*/ int key; int index; bool job;

}

else {

c[k--]=d[i].index; } } j=a[c[0]]; k=j+b[c[0]];

for(int i=1;i

j+=a[c[i]];

k=j

delete d;//回收空间 return k;//返回调度时间 }

int main() {

int n,*a,*b,*c;

cout<<\作业数：\

cin>>n;

Jobtype *d = new Jobtype[N]; a=new int[N]; b=new int[N];

c=new int[N];

cout<<\请输入作业号和时间：\ for(int i=0;i

cin>>d[i].index>>d[i].key; }

cout << endl;

int k=FlowShop(n,a,b,c);

cout<<\调度时间：\

cout<<\最优调度序列:\

for (int i = 0; i < n; i++) // 输出最优调度序列 {

cout << c[i] << \ } return 0; }

运行结果：

6、0-1背包问题 #include #include using namespace std;

const int C=10;//容量 const int N=5;//个数

int max(const int a,const int b) {

return a>b?a:b; }

int min(const int a,const int b) {

return a

m为记录数组 m[i][j]代表在剩有j容量的条件下，从i开始往后的物品中可以取得的最大价值 w为重量数组，v为价值数组 n为物品个数，c为开始容量

则m[1][c]即此背包能剩下的最大价值 */

void knapsack(int **m,int n, int c,int *w, int *v) {

int jMax = min(w[n]-1,c);//前n-1个物品 for(int j=0;j<=jMax;j++) m[n][j]=0;

for(int j=w[n];j<=c;j++)

m[n][j]=v[n]; for(int i=n-1;i>1;i--) {

jMax=min(w[i]-1,c); for(int j=0;j<=jMax;j++) m[i][j] = m[i+1][j]; for(int j=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]); }

//找出最优解，0表示不能装，1表示能装 void traceback(int **m,int n,int c,int *x,int *w) {

for(int i=1;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; }

int main() {

int *v=new int[N+1]; int *w=new int[N+1]; int **m=new int* [N+1]; int *x=new int [N+1]; for(int i=0;i

m[i]=new int[C+1]; }

cout<<\输入重量序列,\个\ for(int i=1;i<=N;i++) cin>>w[i];

cout<<\输入价值序列,\个\ for(int i=1;i<=N;i++)

cin>>v[i];

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

cout<<\最优值：\cout<<\是否装入背包的情况：\ for(int i=1;i<=N;i++) {

cout<

for(int i=0;i

delete m[i]; }

delete []m; return 0; }

运行结果

7、最优二叉搜索树

#include #include #include #define N 100

using namespace std;

const double MAX = numeric_limits::max(); //double的最大值

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

//m[i][j]用来存放子树（i，j）的期望代价

//w[i][j]用来存放子树（i，j）的所有结点（包括虚结点）的a,b概率之和 //s[i][j]用来跟踪root的

void OptimalBinarySearchTree(double *a,double *b,int n) {

int s[N][N];

double m[N][N];

double w[N][N]; int i,j,l,r;

for(i=1; i<=n+1; i++) {

m[i][i-1] = b[i-1]; w[i][i-1] = b[i-1]; }

for(l=1; l<=n; l++) {

for(i=1; i<=n-l+1; i++) {

j = l+i-1;

m[i][j] = MAX;

w[i][j] = w[i][j-1] + a[j] +b[j]; for(r=i; r<=j; r++)

{

double k = m[i][r-1] + w[i][j] + m[r+1][j]; if(k

m[i][j] = k; s[i][j] = k; } } } }

cout<

int main()

{

double a[N],b[N]; int n;

double sum = 0;

int i,j,l;

cout<<\请输入关键字的个数：\ cin>>n;

cout<<\请输入每个关键字的概率：\ for(i=1; i<=n; i++) {

cin>>a[i];

sum += a[i]; }

cout<<\请输入每个虚拟键的概率：\

for(i=0; i<=n; i++) {

cin>>b[i]; sum += b[i]; }

if(abs(sum-1)>0.01)

{

实验总结

cout<<\输入的概率和不为1,请重新输入\ }

cout<<\最优二叉查找树的期望搜索代价为：\ OptimalBinarySearchTree(a,b,n); return 0; }

运行结果：

通过实现动态规划的这个题目，对动态规划算法有了进一步的了解。先分析问题，判断是否具有最优子结果和重叠字问题的性质。

本文来源：https://www.bwwdw.com/article/92bd.html