兰州交通大学《算法设计与分析》实验报告3题目03-动态规划专业计算机科学与技术班级计算机科学与技术2016-02班学号201610333姓名石博洋第3章动态规划1. 实验题目与环境1.1实验题目及要求(1) 用代码实现矩阵连乘问题。
给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,…,n-1。
考察这n 个矩阵的连乘积A1A2…A n。
由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定，则可以依此次序反复调用2个矩阵相乘的标准算法（有改进的方法，这里不考虑）计算出矩阵连乘积。
确定一个计算顺序，使得需要的乘的次数最少。
(2) 用代码实现最长公共子序列问题。
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。
确切地说，若给定序列X= < x1, x2,…, xm>，则另一序列Z= < z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列< i1, i2,…, ik>，使得对于所有j=1,2,…,k有Xij=Zj 。
例如，序列Z=是序列X=的子序列，相应的递增下标序列为<2,3,5,7>。
给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
例如，若X= < A, B, C, B, D, A, B>和Y= < B, D, C, A, B, A>，则序列是X和Y的一个公共子序列，序列也是X和Y的一个公共子序列。
而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。
(3) 0-1背包问题。
现有n种物品，对1<=i<=n，已知第i种物品的重量为正整数W i，价值为正整数V i，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。
（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分）使用动态规划使得装入背包的物品价值之和最大。
1.2实验环境：CPU：Intel(R) Core(TM) i3-2120 3.3GHZ内存：12GB操作系统：Windows 7.1 X64编译环境：Mircosoft Visual C++ 62. 问题分析(1) 分析。
由于矩阵乘法满足结合律，所以计算矩阵连乘的连乘积可以与许多不同的计算计算次序，这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定，也就是说连乘积已完全加括号，那么可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。
完全加括号的矩阵连乘积可递归地定义为：（1）.单个矩阵是完全加括号的；（2）.矩阵连乘积A是完全加括号的，则A可以表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，及A=（BC）;举个例子，矩阵连乘积A1A2A3A4A5，可以有5种不同的完全加括号方式：(A1(A2(A3A4))),(A1((A2A3)A4)),((A1A2)(A3A4)),((A1(A2A3))A4),(((A1A2)A3)A4)每一种完全加括号的方式对应一种矩阵连乘积的计算次序，而矩阵连乘积的计算次序与其计算量有密切的关系，即与矩阵的行和列有关。
补充一下数学知识，矩阵A与矩阵B可乘的条件为矩阵A的列数等于矩阵B的行数，例如，若A是一个p*q的矩阵，B是一个q*r的矩阵，则其乘积C=AB是一个p*r的矩阵。
(2) 分析。
设X= { A, B, C, B, D, A, B},Y= {B, D, C, A, B, A}。
求X，Y的最长公共子序列最容易想到的方法是穷举法。
对X的多有子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列。
由集合的性质知，元素为m的集合共有2^m个不同子序列，因此，穷举法需要指数级别的运算时间。
进一步分解问题特性，最长公共子序列问题实际上具有最优子结构性质。
设序列X={x1,x2,……xm}和Y={y1,y2,……yn}的最长公共子序列为Z={z1,z2,……zk}。
则有：(1)若xm=yn,则zk=xm=yn,且zk-1是Xm-1和Yn-1的最长公共子序列。
(2)若xm!=yn且zk!=xm，则Z是Xm-1和Y的最长公共子序列。
(3)若xm!=yn且zk!=yn，则Z是X和Yn-1的最长公共子序列。
其中，Xm-1={x1,x2……xm-1}，Yn-1={y1,y2……yn-1},Zk-1={z1,z2……zk-1}。
(3) 分析。
动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
但是经分解得到的子问题往往不是互相独立的。
不同子问题的数目常常只有多项式量级。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
它把已知问题分为很多子问题，按顺序求解子问题，在每一种情况下，列出各种情况的局部解，按条件从中选取那些最有可能产生最佳的结果舍弃其余。
前一子问题为后面子问题提供信息，而减少计算量，最后一个子问题的解即为问题解。
采用此方法求解0-1背包问题的主要步骤如下：①分析最优解的结构：最有子结构性质；②建立递归方程；③计算最优值；④构造最优解。
3. 设计过程(1) 代码#include"pch.h"#include<iostream>#include<string.h>using namespace std;struct SIGN {int num;//加括号的个数}l[100 + 5], r[100 + 5]; //l为左括号,r为右括号//矩阵的个数int n;//矩阵的维数第i个矩形的维数为p[i*2]和p[i*2+1]int p[200 + 5];//m[i][j]表示当前i到j最少的计算次数int m[100 + 5][100 + 5];//s[i][j]表示当前i到j最少计算次数需要断开的位置s[i][j]int s[100 + 5][100 + 5];//x[i]表示第i个矩阵要加括号的个数void MatrixChain(){memset(m, 0, sizeof(m));//当前矩阵的长度for (int r = 2; r <= n; r++){//矩阵的起始位置for (int i = 1; i <= n - r + 1; i++){//矩阵的结束位置（矩阵开始+矩阵长度-1）int j = i + r - 1;if (i > n || j > n) continue;//m[i][j]初值m[i][j] = m[i + 1][j] + p[2 * i] * p[2 * i + 1] * p[2 * j + 1];//记录当前s[i][j]的最优断开位置s[i][j] = i;//循环找i,j之间的最优断点kfor (int k = i + 1; k < j; k++){int t = m[i][k] + m[k + 1][j] + p[i * 2] * p[k * 2 + 1] * p[j * 2 + 1];if (t < m[i][j]){//更新i 到j的最优解m[i][j] = t;//更新当前s[i][j]的最优断开位置s[i][j] = k;}}// cout<<i<<" "<<j<<" "<<m[i][j]<<endl;}}}//加括号void Traceback(int i, int j){if (i == j) return;Traceback(i, s[i][j]);Traceback(s[i][j] + 1, j);cout <<"Multiply A("<<i<<","<< s[i][j];cout <<")and A("<< (s[i][j] + 1) <<","<<j<<")"<< endl;l[i].num++;r[j].num++;}//输出括号void dealSign(){cout <<"计算次序：";//加括号for (int i = 1; i <= n; i++){int leftCount = l[i].num;int rightCount = r[i].num;//先输出左括号再输出当前矩阵最后输出右括号for (int j = 0; j < leftCount; j++){cout <<"(";}cout << i;for (int k = 0; k < rightCount; k++){cout <<")";}}cout <<"\n";}int main(){cout <<"请输入矩阵的个数：";cin >> n;cout <<"请输入各矩阵的维数，空格分开"<< endl;for (int i = 1; i <= n; i++){cin >> p[i * 2];cin >> p[i * 2 + 1];}MatrixChain();//输出1到n的最优结果cout <<"最小计算次数为："<< m[1][n] << endl;memset(l, 0, sizeof(l));memset(r, 0, sizeof(r));Traceback(1, n);dealSign();return 0;}(2) 代码#include"pch.h"#include<iostream>using namespace std;const int M = 7;const int N = 6;void output(char *s, int n);void LCSLength(int m, int n, char *x, char *y, int **c);void LCS(int i, int j, char *x, int **c);int main(){//X={A,B,C,E,F,B,A}//Y={B,D,E,F,B,A}char x[] = { ' ','A','B','C','E','F','B','A', };char y[] = { ' ','B','D','E','F','B','A' };int **c = new int *[M + 1];for (int i = 0; i <= M; i++){c[i] = new int[N + 1];}cout <<"序列X："<< endl;output(x, M);cout <<"序列Y："<< endl;output(y, N);LCSLength(M, N, x, y, c);cout <<"序列X、Y最长公共子序列长度为："<< c[M][N] << endl;cout <<"序列X、Y最长公共子序列为："<< endl;LCS(M, N, x, c);cout << endl;}void output(char *s, int n){for (int i = 1; i <= n; i++){cout <<s[i] <<" ";}cout << endl;}void LCSLength(int m, int n, char *x, char *y, int **c) {int i, j;for (i = 1; i <= m; i++)c[i][0] = 0;for (i = 1; i <= n; i++)c[0][i] = 0;for (i = 1; i <= m; i++){for (j = 1; j <= n; j++){if (x[i] == y[j]){c[i][j] = c[i - 1][j - 1] + 1;}else if (c[i - 1][j] >= c[i][j - 1]){c[i][j] = c[i - 1][j];}else{c[i][j] = c[i][j - 1];}}}}void LCS(int i, int j, char *x, int **c){if (i == 0 || j == 0){return;}if (c[i][j] == c[i - 1][j - 1] + 1){LCS(i - 1, j - 1, x, c);cout <<x[i] <<" ";}else if (c[i - 1][j] >= c[i][j - 1]){LCS(i - 1, j, x, c);}else{LCS(i, j - 1, x, c);}}(3) 代码。