算法设计与分析实验报告华北电力大学.doc

华北电力大学实 验 报 告| 实验名称 算法设计与分析实验 课程名称 算法设计与分析 | 专业班级：计科1203 学生姓名： 学 号： 成 绩：指导教师：牛为华 实验日期：2014年10月实验一、矩阵连乘1、 实验目的及要求 1、了解并掌握动态规划算法解矩阵连乘问题的原理； 2、通过上机实验，对矩阵连乘的知识进行巩固； 3、用程序实现矩阵连乘。2、 实验原理 1、两个矩阵相乘，第一个矩阵的列数=第二个矩阵的行数； 2、三个矩阵相乘时： A1 * A2 * A3 =(A1 * A2 ) * A3 ) A1 * A2 * A3 =(A1 * ( A2 * A3 ) 不同的运算顺序，所需的乘法次数就不一样；在算分设计与 分析中，我们知道，乘法的次数越多，消耗的空间就越大，所需 的时间就越多。 3、当多个矩阵相乘时： 我们假设Mi，j就是第i个矩阵到第j个矩阵的矩阵连乘， 即 Mi，j=Mi Mi+1 Mj 选中一个k值，i=k=j，使得： Mi，k-1 = MiMi+1Mk-1，Mk，j =MkMk+1Mj 用数组Cij表示第i个矩阵到第j个矩阵的矩阵连乘 最优解，有： 三、问题分析及算法设计思路 1、计算最优值算法：建立两张表（，一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵、直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2、输出矩阵结合方式算法：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程两次，构造出最优加括号方式。四、程序代码#include using namespace std;#define N 100int n,q;int mNN,sNN,pN+1;/计算最优值和最优解，最优值存储在mij，最优解存储在sijvoid matrixChain() for(int i=1;i=n;i+)mii=0;for(int r=2;r=n;r+) for(int i=1;i=n-r+1;i+) int j = r+i-1; mij=mii+mi+1j+pi-1*pi*pj; sij=i; for(int k = i+1;kj;k+) int temp=mik+mk+1j+pi-1*pk*pj; if(tempmij) mij=temp; sij=k; /显示输出void Traceback(int i,int j) if(i = j) coutAi; else if(i+1 = j) cout(AiAj); else cout(; Traceback(i,sij); Traceback(sij+1,j); cout); void main()using namespace std;coutn;cout输入第一个矩阵行数和第一个到第n个矩阵的列数：;coutendl;for(int i=0;ipi;coutendl;matrixChain();cout最优计算次序为：;Traceback(1,n);coutendl;cout矩阵连乘的最优数乘次数为：m1nendl; /最终解值为m1n coutendl;for(int i=1;i=n;i+)for(int j=i+1;j=n;j+)cout第i个矩阵与第j个矩阵连乘的最优解为:mij;system(PAUSE);5、 实验结果实验二、动态规划解0-1背包1、 实验目的与要求 1. 理解动态规划算法的原理和基本要素； 2了解并掌握动态规划算法解0-1背包问题的原理 3用程序实现该算法，可输入背包容量，物品重量数组，物品价值数组； 2、 实验内容给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的所能够容纳的重量为c。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？三、问题分析及算法设计思路 在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入物品i的一部分。 0-1背包问题具有最优子结构性质，可以据此定义递归关系，建立递归方程，并以自底向上的方式计算最优值，根据计算最优值时的得到的信息，构造最优解。 设所给0-1背包问题的子问题的最优值V(i,j)，即V(i,j)是背包重量为j，可选物品为i，i+1，n-1时的最优值。由最优子结构性质，可以计算出V(i,j)的递归式如下： 0 if i=0 or j=0; if j0 and jwi上述式子表明：如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi的背包中的价值加上第i个物品的价值vi; (b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。3、 程序代码#include#include int V200200;/前i个物品装入容量为j的背包中获得的最大价值 int max(int a,int b) if(a=b) return a; else return b; int KnapSack(int n,int w,int v,int x,int C) int i,j; for(i=0;i=n;i+) Vi0=0; for(j=0;j=C;j+) V0j=0; for(i=0;i=n-1;i+) for(j=0;j=C;j+) if(j=0;i-) if(VijVi-1j) xi=1; j=j-wi; else xi=0; printf(选中的物品是:n); for(i=0;in;i+) printf(%d ,xi); printf(n); return Vn-1C; void main() int s;/获得的最大价值 int w15;/物品的重量 int v15;/物品的价值 int x15;/物品的选取状态 int n,i; int C;/背包最大容量 n=5; printf(请输入背包的最大容量:n); scanf(%d,&C); printf(输入物品数:n); scanf(%d,&n); printf(请分别输入物品的重量:n); for(i=0;in;i+) scanf(%d,&wi); printf(请分别输入物品的价值:n); for(i=0;in;i+) scanf(%d,&vi); s=KnapSack(n,w,v,x,C); printf(最大物品价值为:n); printf(%dn,s); system(PAUSE); 4、 实验结果实验三、回溯法解0-1背包1、 实验目的与要求 1. 理解回溯法的基本思想； 2了解并掌握回溯法法解0-1背包问题的原理 3用程序实现该算法，可输入背包容量，物品重量数组，物品价值数组； 二、实验内容给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的所能够容纳的重量为c。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？3、 问题分析与算法设计思路对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树： 10AFEDBC110011G 可知该问题的解空间为子集树，基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。由父亲节点往下搜索的时候，往右表示选择该物品，并且将该物品的重量和价值追加到总重量和总价值中，最后，当到达第n+1层的时候，表示所有的物品都已经决策完了，可以比较和更新最优值。当所有的分支和节点都遍历完时，此时的最优值就是原问题的最优值。 回溯法的优化方法： 剪枝一：可以进行剪枝，因为很多情况是没有意义的，当重量大于背包容量的时候，没有必要对剩下的物品再来决策了。 剪枝二：将剩下的所有物品都选取其总价值也没有目前已经求得的方案的价值还大的话，也可以返回。3、 程序代码 #include using namespace std; double c;/背包容量 int n; /物品数 double w100;/物品重量数组 double p100;/物品价值数组 double cw=0;/当前重量 double cp=0;/当前价值 double bestp=0;/当前最优值 double bound(int i) double cleft,b; cleft=c-cw;/剩余容量 b=cp; /以物品单位重量价值递减序装入物品 while(i=n&wi=cleft) cleft-=wi; b+=pi; i+; /装满背包 if(in) if(cpbestp) bestp=cp; return; if(cw+wibestp)/搜索右子树 Backtrack(i+1); double Knapsack (double pp,double ww,double d) int i; double TP=0, TW=0; cw=0.0; cp=0.0; bestp=0.0; for(i=1;i=n;i+) TP=TP+ppi; TW=TW+wwi; if(TW=d) bestp=TP; else Backtrack(1); return bestp; int main() int i,j; double t,a,x100;