第3章-动态规划-复习.pptVIP

软件701 计算机05级-软件方向 租用游艇问题 长江游艇俱乐部在长江上设置了n 个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i 到游艇出租站j 之间的租金为r(i,j),1=ij=n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n 所需的最少租金。 编程任务： 对于给定的游艇出租站i 到游艇出租站j 之间的租金为r(i,j),1=ij=n，编程计算从游艇出租站1 到游艇出租站n所需的最少租金。 租用游艇问题 数据输入： 第1 行中有1 个正整数n（n=200），表示有n个游艇出租站。接下来的n-1 行是r(i,j),1=ij=n。 结果输出: 程序运行结束时，输出从游艇出租站1 到游艇出租站n所需的最少租金。 输入示例 3 5 15 7 输出示例 12 租用游艇问题 租用游艇问题 租用游艇问题 void dyna() { for (int k=2; kn; k++) for (int i=0; in-k; i++) { int j=i+k; for (int p=i+1; pj; p++) { int temp = f[i][p] + f[p][j]; if (f[i][j]temp) f[i][j] = temp; } } } 最优值在f[0][n-1]中. 第3章 动态规划复习课 完全加括号的矩阵连乘积 完全加括号的矩阵连乘积可递归地定义为： 单个矩阵是完全加括号的； 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC) 设有四个矩阵A, B, C, D，总共有五中完全加括号的方式: (A((BC)D)) (A(B(CD))) ((AB)(CD)) (((AB)C)D) ((A(BC)D)) 完全加括号的矩阵连乘积 设有四个矩阵A, B, C, D，它们的维数分别是： A=50×10, B=10×40, C=40×30, D=30×5 矩阵A和B可乘的条件是: 矩阵A的列数等于矩阵B的行数. 设A是p×q的矩阵, B是q×r的矩阵, 则乘积是p×r的矩阵;计算量是pqr. 上述5种完全加括号方式的计算工作量为: (A((BC)D)), (A(B(CD))), ((AB)(CD)), (((AB)C)D), ((A(BC)D)) 16000, 10500, 36000, 87500, 34500 BC: 10×40×30 = 12000, (BC)D: 10×30×5 = 1500, (A((BC)D)): 50×10×5 = 2500 矩阵连乘问题 穷举法 动态规划 将矩阵连乘积AiAi+1…Aj 简记为A[i:j], 这里i≤j; 考察计算A[i:n]的最优计算次序。 设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1≤kn，则其相应完全加括号方式为(A1A2…Ak)(Ak+1Ak+2…An) 计算量：A[1:k]的计算量加上A[k+1:n]的计算量，再加上A[1:k]和A[k+1:n]相乘的计算量 建立递归关系 设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n] 当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n 当ij 时， 这里Ai的维数是Pi-1×Pi 可以递归地定义m[i,j]为： 计算最优值 void MatrixChain(int *p，int n，int **m，int **s) { 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;} } } } 计算最优值 计算最优值 voi