《算法设计与分析》第章.pptVIP

算法设计与分析 第2部分 算法设计策略 第7章 动态规划法 7.1 一般方法和基本要素 动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题。 7.1.1 一般方法 7.1.2 基本要素 7.1.3? 多段图问题 7.1.4 资源分配问题 7.2 每对结点间的最短路径 7.2.1? ?问题描述 7.2.2 动态规划法求解 7.2.3?弗洛伊德算法 7.2.4 算法正确性 7.3 矩阵连乘 7.3.1? 问题描述 7.3.2 动态规划法求解 7.3.3?矩阵连乘算法 7.3.4? 备忘录方法 7.5 最优二叉有哪些信誉好的足球投注网站树 7.5.1 问题描述 7.5.2?动态规划法求解 7.5.3 最优二叉有哪些信誉好的足球投注网站树算法 7.6 0/1背包 7.6.1? 问题描述 7.6.2? 动态规划法求解 7.6.3? 0/1背包算法框架 7.6.5 性能分析 7.7 流水作业调度 7.7.1 问题描述 7.7.2 动态规划法求解 7.7.3 Johnson算法 【程序7－3】矩阵连乘算法 class MatrixChain { public: MatrixChain(int mSize,int *q); int MChain(); int LookupChain(); void Traceback(); …… private: void Traceback(int i,int j); int LookupChain(int i, int j); int *p,**m,**s,n; }; int MatrixChain::MChain() { //求A[0:n-1]的最优解值 for (int i=0;in;i++) m[i][i]=0; for (int r=2; r=n;r++) for (int i=0;i=n-r;i++) { int j=i+r-1; m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]; s[i][j]=i; for (int k=i+1;kj;k++) { int t=m[i][k] +m[k+1][j]+p[i]*p[k+1]*p[j+1]; if (tm[i][j]) { m[i][j]=t;s[i][j]=k; } } } return m[0][n-1]; } void MatrixChain::Traceback(int i,int j) { if(i==j) { coutAi;return;} if (is[i][j]) cout(; Traceback(i,s[i][j]);if (is[i][j])cout); if(s[i][j]+1j)cout(; Traceback(s[i][j]+1,j);if(s[i][j]+1j) cout); } void MatrixChain::Traceback() { cout(; Traceback(0,n-1);cout); coutendl; } 例7－5 6个矩阵连乘积A0A1A2A3A4A5，设它们的维数分别为A:30?35，B:35?15 C:15?5 D:5?10，E:10?20，F:20?25。 矩阵连乘的备忘录方法 备忘录方法为每个已经计算的子问题建立备忘录，即保存子问题的计算结果以备需要时引用，从而避免了相同