实验报告32014110451余双.doc

实验编号：3 四川师大算法设计与分析实验报告 2016 年5月1日计算机科学学院14 级4班 实验名称：动态规划及其应用姓名：余双 学号：2014110451 指导老师：_苏菡_ 实验成绩:_实验一 动态规划及其应用一 实验目的及要求目的要求：（1）理解动态规划算法的概念和基本要素，并能和分治法进行比较。（2）掌握设计动态规划算法的步骤，并编程实现有关算法。（3）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。二 实验内容（1） 编程实现矩阵连乘问题的求解。（2）编程实现最大子段和问题的求解（分别采用分治法和动态规划法求解）。（3）编程实现01背包问题的求解。（4）设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。（5）编程实现最长公共子序列(LCS)问题的求解。（6）设计算法求解数字三角形问题，并编程实现。（P80算法实现题34）（7）设计算法求解独立任务最优调度问题，并编程实现。问题描述：欧诺个2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai=bi,而对于某些j,j不等于i，有ajbj.既不能讲一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，是的这2台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总时间）。研究一个实例：（a1，a2，a3，a4，a5，a6）=（2,5,7,10,5,2）；（b1,b2,b3,b4,b5,b6）=（3,8,4,11,3,4）如：（8）设计算法求解最少硬币问题，并编程实现。注：至少选择其中3题完成。主要仪器设备及软件（1） PC机（2） TC、VC+、Java等任一编程语言三 实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现矩阵连乘问题的求解。程序代码：main.cpp#include #include head.husing namespace std;int main() int i,n,*p; cout请输入矩阵的个数：n; p=new intn+1; cout请输入矩阵的维数(相邻矩阵的行列相等，只输入一次就行！); for(i=0;ipi; int *m,*s; m=new int*n+1; s=new int*n+1; for(i=1;i=n;i+) mi=new intn+1; si=new intn+1; MatrixChain(p,n,m,s); TraceBack(1,n,s); return 0;MatrixChain.cpp#include #include head.husing namespace std;void MatrixChain(int *p,int n,int *m,int *s) int i,j,r,k; for(i=1;i=n;i+) mii=0; sii=0; for(r=2;r=n;r+) for(i=1;in;i+)j=i+r-1; if(j7) mij=mii+mi+1j+pi-1*pi*pj; sij=i; for(k=i+1;kj;k+) int temp; temp=mik+mk+1j+pi-1*pk*pj; if(tempmij) mij=temp; sij=k; TraceBack.cpp#include #include head.husing namespace std;void TraceBack(int i,int j,int *s) if(i=j) return ; TraceBack(i,sij,s); TraceBack(sij+1,j,s); coutMultiply Ai,sij and Multiply Asij+1,jendl;head.h:#ifndef HEAD_H_INCLUDED#define HEAD_H_INCLUDEDvoid MatrixChain(int *p,int n,int *m,int *s);void TraceBack(int i,int j,int *s);#endif / HEAD_H_INCLUDED运行结果：（2）编程实现最大子段和问题的求解（分别采用分治法和动态规划法求解）。分治法：main.cpp:#include #include head.husing namespace std;int main()int n,i,*a;cout请输入序列长度：n;a=new intn+1;cout请输入该序列具体的数：;for(i=1;iai; int sum=MaxSubSum(1,n,a);cout该序列的最大字段和为：sumendl;MaxSubSum.cpp:#include #include head.hint MaxSubSum(int left,int right,int *a)int sum=0;if(left=right) sum=aleft0? aleft:0;else int center=(left+right)/2;int leftsum =MaxSubSum(left,center,a);int rightsum =MaxSubSum(center+1,right,a);int s1=0;int lefts=0;for(int i=center;i=left;i-)lefts+=ai;if(leftss1)s1=lefts;int s2=0;int rights=0;for(int j=center+1;js2)s2=rights;sum=s1+s2;if(leftsumsum) sum=leftsum;if(rightsumsum) sum=rightsum;return sum;head.h:#ifndef H#define H int MaxSubSum(int left,int right,int *a);#endif运行结果：动态规划法：main.cpp#include #include head.husing namespace std;int main()int n,i,*a;cout请输入序列长度：n;a=new intn+1;cout请输入该序列具体的数：;for(i=1;iai; int sum=MaxSubSum(n,a);cout该序列的最大字段和为：sumendl;MaxSubSum.cpp#include #include head.husing namespace std;int MaxSubSum(int n,int *a)int sum=0,b=0;for(int i=1;i0) b+=ai;else b=ai;if(bsum) sum=b; return sum;head.h:#ifndef H#define Hint MaxSubSum(int n,int *a);#endif运行结果：（3）编程实现01背包问题的求解main.cpp:#include #include head.husing namespace std;int main()int i,n,c,*v,*w,*m;cout请输入物品个数：n;cout请输入背包总容量：c;v=new int n+1; w=new int n+1; cout请输入每个物品的价值：endl;for(i=1;ivi;cout请输入每个物品的重量：endl;for(i=1;iwi;m=new int* n+1;for(i=0;i=n;i+)mi=new int n+1; package(n,c,v,w,m);cout物品装入背包的情况如下：（0表示该物品未放入背包，1表示该物品放入了背包）endl;traceBack(1,c,w,m,n);package.cpp:#include #include head.husing namespace std;void package(int n,int c,int *v,int *w,int *m) int i,j;for(i=0;i=n;i+)mi0=0; for(j=0;jj)mnj=0;elsemnj=vn;for(i=n-1;i0;i-)for(j=c;j0;j-)if(wij) mij=mi+1j;else if(mi+1jvi+mi+1j-wi) mij=vi+mi+1j-wi;else mij=mi+1j;traceBack.cpp:#include #include head.husing namespace std;void traceBack(int i,int j,int *w,int *m,int n)if(i=n)if(wi=j)cout物品i:1endl;elsecout物品i:0endl;return ;if(mij=mi+1j)cout物品i:0endl;i+;traceBack(i,j,w,m,n);else cout物品i:1endl;j-=wi;i+;traceBack(i,j,w,m,n);head.h:#ifndef H#define Hvoid package(int n,int c,int *v,int *w,int *m);void traceBack(int i,int j,int *w,int *m,int n);#endif运行结果：（4）设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。程序代码：main.cpp:#include #include Sub.husing namespace std;int main()int n,*a,*b,*c,i;cout请输入序列长度：n;a=new intn+1; b=new intn+1;c=new intn+1;cout请输入该序列的每一个数:endl;for(i=1;iai;bn=1; Sub(n,a,b,c);int temp=b1,j=1;for(i=1;i=n;i+) if(tempbi)temp=bi;j=i;cout最长单调递增子序列长度为temp,如下所示：endl;while(cj!=j) coutaj ; j=cj;coutajendl;sub.cpp:#include #include Sub.husing namespace std;int Sub(int n,int *a,int *b,int *c) int i,k,j,temp,temp2;for(i=n;i0;i-) temp=ai;j=0;temp2=0;bi=1;for(k=i+1;k=n;k+) if(aitemp2)j=k;temp=ak;temp2=bk;if(temp=ai) bi=1; ci=i;elsebi=1+temp2;ci=j;return 0;sub.h:#ifndef H#define Hint Sub(int n,int *a,int *b,int *c);#endif运行结果：（5）编程实现最长公共子序列(LCS)问题的求解程序代码：main.cpp:#include #include head.husing namespace std;int main()char *x,*y;int m,n;cout请输入第一个序列的长度:m;x=new charm+1;cout请输入第一个序列:endl;for(int i=1;ixi;cout请输入第二个数序列长度:n; y=new charn+1;cout请输入第二个序列:endl;for(int j=1;jyj;int *c,*b;c=new int*m+1; b=new int*m+1; for(int k=0;k=m;k+)ck=new int n+1;bk=new int n+1; LCSLegth(m,n,x,y,c,b);char * z=new char cmn+1; LCS(m,n,x,b,z,cmn);cout最长公共子序列如下：endl; for(i=1;i=cmn;i+)coutzi;coutendl; return 0;LCS.cpp:#include #include head.husing namespace std;int LCS(int i,int j,char * x,int *b,char * z,int k)if(i=0|j=0)return 0;else if(bij=1) zk=xi; i-; j-; LCS(i,j,x,b,z,k-1);elseif(bij=2)i-; LCS(i,j,x,b,z,k);elsej-;LCS(i,j,x,b,z,k);LCSLegth.cpp:#include #include head.husing namespace std;int LCSLegth(int m, int n, char *x, char *y,int* c,int *b)int i,j; for(i=0;i=m;i+)ci0=0;for(j=0;j=n;j+)c0j=0;for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;bij=2;else cij=cij-1;bij=3;return 0;head.h:#ifndef H#define Hint LCSLegth(int m, int n, char *x, char *y,int* c,int *b);int LCS(int i,int j,char * ,int *b,char * z,int k);#endif运行结果：（6） 设计算法求解数字三角形问题