动态规划算法实验报告.doc

实验标题

1、 矩阵连乘 2、最长公共子序列 3、最大子段和
4、 凸多边形最优三角剖分 5、流水作业调度
6、0-1背包问题 7、最优二叉搜索树
实验目的
掌握动态规划法的基本思想和算法设计的基本步骤。
实验内容与源码
1、 矩阵连乘
#include<iostream>
#include<cstdlib>
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<ra;i++)
for(int j=0;j<cb;j++)
{
int sum=a[i][0]*b[0][j];
for(int k=1;k<ca;k++)
sum+=a[i][k]*b[k][j];
c[i][j]=sum;
}
}

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<j;k++)
{
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}

void Traceback(int i,int j,int s[][4])
{
if(i == j)
{
cout<<"A"<<i;
}
else if(i+1 == j)
{
cout<<"(A"<<i<<"A"<<j<<")";
}
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"<<i<<"维数：";
cin>>p[i-1]>>p[i];
if(p[i-1] != m)
{
cout<<endl<<"维数不对，矩阵不可乘！"<<endl;
exit(1);
}
}
Traceback(1,w,s);
return 0;
}

运行结果

2、 最长公共子序列
#include<cstring>
#include<iostream>
#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]<s[i][j-1]
int flag[N][N];

//求长度
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："<<endl;
cin>>str1;
cout<<"请输入字符串y："<<endl;
cin>>str2;
int lcsLen = LCSLength(str1,str2);
cout<<"最长公共子序列长度："<<lcsLen<<endl;
char *p = getLCS(str1,str2,lcsLen,lcs);
cout<<"最长公共子序列为：";
for(i=0;i<lcsLen;i++)
cout<<lcs[i]<<" ";

return 0;
}

运行结果

3、最大子段和
//分治法求最大子段和
#include<iostream>
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<<"最大子段和为："<<MaxSum(a,8);
return 0;
}

//动态规划法
#include<iostream>
using namespace std;
int MaxSum(int *a,int n)
{
int sum=0,b=0;
for(int i=1;i<n;i++)//此处不能=n，
{
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<<"最大子段和为："<<MaxSum(a,8);
return 0;
}

运行结果

4、 凸多边形最优三角剖分
#include<iostream>
#include<cmath>
#include<cstdlib>
#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<m ; i++)
{
cout<<"输入顶点v"<<i<<"的坐标：";
cin>>v[i].x>>v[i].y;
}
//根据顶点坐标判断是否能构成一个凸多边形
for(int j=0 ; j<m ; 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<m ; 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<<"无法构成凸多边形！"<<endl;
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<i+r-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"<<i-1<<"v"<<s[i][j]<<"v"<<j<<endl;
}

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<N ; 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<<endl;
cout<<"最优权值之和为："<<t[1][M]<<endl;
}
}
return 0;
}

运行结果：

5、 流水作业调度
#include<iostream>
#define N 100
using namespace std;

class Jobtype
{
public:
/* int operator<=(Jobtype a)const
{
return(key<=a.key);
}*/
int key;
int index;
bool job;
};

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<n;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<n;i++)//最优调度
{
if(d[i].job)
{
c[j++]=d[i].index;
}
else
{
c[k--]=d[i].index;
}
}
j=a[c[0]];
k=j+b[c[0]];
for(int i=1;i<n;i++)
{
j+=a[c[i]];
k=j<k?k+b[c[i]]:j+b[c[i]];
}
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<n;i++)
{
cin>>d[i].index>>d[i].key;
}
cout << endl;
int k=FlowShop(n,a,b,c);
cout<<"\n调度时间："<<k<<endl;
cout<<"最优调度序列:";
for (int i = 0; i < n; i++) // 输出最优调度序列
{
cout << c[i] << " ";
}
return 0;
}

运行结果：

6、0-1背包问题
#include <iostream>
#include <iomanip>
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<b?a:b;
}

/*
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<n;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<N+1;i++)
{
m[i]=new int[C+1];
}
cout<<"输入重量序列,"<<N<<"个"<<endl;
for(int i=1;i<=N;i++)
cin>>w[i];
cout<<"输入价值序列,"<<N<<"个"<<endl;
for(int i=1;i<=N;i++)
cin>>v[i];
knapsack(m,N,C,w,v);
traceback(m,N,C,x,w);
cout<<"最优值："<<m[1][C]<<endl;
cout<<"是否装入背包的情况：";
for(int i=1;i<=N;i++)
{
cout<<x[i];
}
for(int i=0;i<N+1;i++)
{
delete m[i];
}
delete []m;
return 0;
}

运行结果

7、 最优二叉搜索树
#include<iostream>
#include<cmath>
#include<limits>
#define N 100
using namespace std;
const double MAX = numeric_limits<double>::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])
{
m[i][j] = k;
s[i][j] = k;
}
}
}
}
cout<<m[1][n];
}

int main()
{
double a[N],b[N];
int n;
double sum = 0;
int i,j,l;
cout<<"请输入关键字的个数："<<endl;
cin>>n;
cout<<"请输入每个关键字的概率："<<endl;
for(i=1; i<=n; i++)
{
cin>>a[i];
sum += a[i];
}
cout<<"请输入每个虚拟键的概率："<<endl;
for(i=0; i<=n; i++)
{
cin>>b[i];
sum += b[i];
}
if(abs(sum-1)>0.01)
{
cout<<"输入的概率和不为1,请重新输入"<<endl;
}
cout<<"最优二叉查找树的期望搜索代价为：";
OptimalBinarySearchTree(a,b,n);
return 0;
}

运行结果：

实验总结

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