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

实验标题

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;iin(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
{
cout<<"(A"<>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"<>p[i-1]>>p[i];
if(p[i-1] != m)
{
cout<
}

运行结果

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]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："<>str1;
cout<<"请输入字符串y："<
cin>>str2;
int lcsLen = LCSLength(str1,str2);
cout<<"最长公共子序列长度："<
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<<"最大子段和为："<
using namespace std;
int MaxSum(int *a,int n)
{
int sum=0,b=0;
for(int i=1;i0) 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<<"最大子段和为："<
#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>v[i].x>>v[i].y;
}
//根据顶点坐标判断是否能构成一个凸多边形
for(int j=0 ; j
b = v[j].x - v[j+1].x;
c = b * v[j].y - a * v[j].x;
}
for(int k=0 ; k 0)
{
p = p+1;
}
else if(total[k] < 0)
{
q = q+1;
}
}
if((p>0 && q>0) || (p==0 && q==0))
{
cout<<"无法构成凸多边形！"<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 *total; //记录坐标在直线方程中的值
int M=0;
t = new int *[N];
s = new int *[N];
for(int i=0 ; i)
{
if(minWeightTriangulation())
{
Traceback(1,M,s);
cout<
#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;ib[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 {
j+=a[c[i]];
k=j>n;
Jobtype *d = new Jobtype[N];
a=new int[N];
b=new int[N];
c=new int[N];
cout<<"请输入作业号和时间：";
for(int i=0;i>d[i].index>>d[i].key;
}
cout << endl;
int k=FlowShop(n,a,b,c);
cout<<"\n调度时间："<行结果：

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的最大价值
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;iw=new int[N+1];
int **m=new int* [N+1];
int *x=new int [N+1];
for(int i=0;i>w[i];
cout<<"输入价值序列,"<>v[i];
knapsack(m,N,C,w,v);
traceback(m,N,C,x,w);
cout<<"最优值："<lude
#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 s[i][j] = k;
}
}
}
}
cout<>n;
cout<<"请输入每个关键字的概率："< cin>>a[i];
sum += a[i];
}
cout<<"请输入每个虚拟键的概率："<>b[i];
sum += b[i];
}
if(abs(sum-1)>0.01)
{
cout<<"输入的概率和不为1,请重新输入"<