# 第15章：动态规划

一、综述

动态规划是通过组合子问题的解而解决整个问题的。 动态规划适用于子问题不是独立的情况，也就是各子问题的包含公共的子子问题。 动态规划对每个子问题只求解一次，将其结果保存在一张表中。 动态规划通常用于最优化问题。 动态规划的设计步骤：a.描述最优解的结构b.递归定义最优解的值c.按自底向上的方式计算最优觖的值d.由计算出的结构构造一个最优解

二、代码

15.1装配线调度

## include

using namespace std;

## define I 2

## define J 6

int a\[I+1]\[J+1], t\[I+1]\[J+1], e\[I+1], x\[I+1], n = J;//输入 int f\[I+1]\[J+1], l\[I+1]\[J+1],rf,rl; //输出 //书上的伪代码 void Fastest\_Way() { //初始化 f\[1]\[1] = e\[1] + a\[1]\[1]; f\[2]\[1] = e\[2] + a\[2]\[1]; int j; for(j = 2; j <= n; j++) { //根据公式15.6计算 if(f\[1]\[j-1] + a\[1]\[j] <= f\[2]\[j-1] + t\[2]\[j-1] + a\[1]\[j]) { //记录计算结果 f\[1]\[j] = f\[1]\[j-1] + a\[1]\[j];\
l\[1]\[j] = 1; } else { //记录计算结果 f\[1]\[j] = f\[2]\[j-1] + t\[2]\[j-1] + a\[1]\[j]; l\[1]\[j] = 2; } //根据公式15.7计算 if(f\[2]\[j-1] + a\[2]\[j] <= f\[1]\[j-1] + t\[1]\[j-1] + a\[2]\[j]) { //记录计算结果 f\[2]\[j] = f\[2]\[j-1] + a\[2]\[j]; l\[2]\[j] = 2; } else { //记录计算结果 f\[2]\[j] = f\[1]\[j-1] + t\[1]\[j-1] + a\[2]\[j]; l\[2]\[j] = 1; } } //最后一个结果另外记录 if(f\[1]\[n] + x\[1] <= f\[2]\[n] + x\[2]) { rf = f\[1]\[n] + x\[1]; rl = 1; } else { rf = f\[2]\[n] + x\[2]; rl = 2; } } //输出 void Print\_Stations() { cout<<"输出装配路线"<\<endl; int i = rl, j; //从后向前输出 cout<<"line "< 1; j--) { //获取记录的结果 i = l\[i]\[j]; cout<<"line "<\<i<<" station "<\<j-1<\<endl; } } //练习 //15.1-1 void Print\_Stations2(int i, int j) { cout<<"顺序输出装配路线"<\<endl; if(j != n) i = l\[i]\[j+1]; //先输出前面的 if(j > 1) Print\_Stations2(i, j-1); //再输出当前的 cout<<"line "<\<i<<" station "<\<j<\<endl; } //输入数据 void Input() { int i, j; cout<<"输入在装配站S(i,j)的装配时间a(i,j)："<\<endl; //7 9 3 4 8 4 8 5 6 4 5 7 for(i = 1; i <= I; i++) { for(j = 1; j <= J; j++) cin>>a\[i]\[j]; } cout<<"输入进入装配线i的花费时间e(i)："<\<endl; //2 4 for(i = 1; i <= I; i++) cin>>e\[i]; cout<<"输入从S(i,j)站移动S(i2,j+1)的花费时间t(i,j)："<\<endl; //2 3 1 3 4 2 1 2 2 1 for(i = 1; i <= I; i++) { for(j = 1; j < J; j++) cin>>t\[i]\[j]; } cout<<"输入从装配线i离开的花费时间x(i)："<\<endl; //3 2 for(i = 1; i <= I; i++) cin>>x\[i]; } void Output() { int i, j; cout<<"输出f\[i]\[j]"<\<endl; //f\[i]\[j]表示第j个站是在装配线i上完成的，完成1到j的装配最少需要的时间 for(i = 1; i <= I; i++) { for(j = 1; j <= J; j++) cout<\<f\[i]\[j]<<' '; cout<\<endl; } cout<<"输出l\[i]\[j]"<\<endl; //l\[i]\[j]表示使得f\[i]\[j]最小时在哪个装配线上装配j-1 for(i = 2; i <= I; i++) { for(j = 1; j <= J; j++) cout<\<l\[i]\[j]<<' '; cout<\<endl; } } int main() { Input(); Output(); Fastest\_Way(); Print\_Stations(); Print\_Stations2(rl, J); return 0; }

15.2矩阵链乘法

## include

using namespace std;

## define N 6

int m\[N+1]\[N+1] = {0}, s\[N+1]\[N+1] = {0}; void Matrix\_Chain\_Order(int _p) { int i, l, j, k, q; for(i = 1; i <= N; i++) m\[i]\[i] = 0; for(l = 2; l <= N; l++) { for(i = 1; i <= N - l + 1; i++) { j = i + l - 1; m\[i]\[j] = 0x7fffffff; for(k = i; k <= j - 1; k++) { q = m\[i]\[k] + m\[k+1]\[j] + p\[i-1]_&#x70;\[k]_p\[j]; if(q < m\[i]\[j]) { m\[i]\[j] = q; s\[i]\[j] = k; } } } } } //15.2-2递归算法 int Matrix\_Chain\_Order(int_ A, int start, int end) { //只有一个矩阵时，不需要括号 if(start == end) return 0; //如果已经有结果，直接使用结果 if(m\[start]\[end]) return m\[start]\[end]; int i, q; m\[start]\[end] = 0x7fffffff; //P199，公式15.15 for(i = start; i < end; i++) { q = Matrix\_Chain\_Order(A, start, i) + Matrix\_Chain\_Order(A, i+1, end) + A\[start-1] _A\[i]_ A\[end]; //选最小值 if(q < m\[start]\[end]) { m\[start]\[end] = q; s\[start]\[end] = i; } } return m\[start]\[end]; } //输出结果 void Print\_Optimal\_Parens(int \*A, int i, int j) { if(i == j) cout<<'A'<\<i; else { cout<<'('; Print\_Optimal\_Parens(A, i, s\[i]\[j]); Print\_Optimal\_Parens(A, s\[i]\[j]+1, j); cout<<")"; } } int main() { int A\[N+1] = {5, 10, 3, 12, 5, 50, 6}; int A2\[N+1] = {30, 35, 15, 5, 10, 20, 25}; Matrix\_Chain\_Order(A, 1, N); Print\_Optimal\_Parens(A, 1, N); return 0; }

15.3动态规划基础

## include

using namespace std;

## define N 6

int m\[N+1]\[N+1] = {0}, s\[N+1]\[N+1] = {0}; //重叠子问题 int Recursive\_Matrix\_Chain(int _p, int i, int j) { //只有一个矩阵时，不需要括号 if(i == j) return 0; //如果已经有结果，直接使用结果 if(m\[i]\[j]) return m\[i]\[j]; int k, q; m\[i]\[j] = 0x7fffffff; //P199，公式15.15 for(k = i; k < j; k++) { q = Recursive\_Matrix\_Chain(p, i, k) + Recursive\_Matrix\_Chain(p, k+1, j) + p\[i-1]_ p\[k] _p\[j]; //选最小值 if(q < m\[i]\[j]) { m\[i]\[j] = q; s\[i]\[j] = k; } } return m\[i]\[j]; } //做备忘录 int Lookup\_Chain(int_ p, int i, int j) { int k, q; if(m\[i]\[j] < 0x7fffffff) return m\[i]\[j]; if(i == j) m\[i]\[j] = 0; else { for(k = i; k < j; k++) { q = Lookup\_Chain(p, i, k) + Lookup\_Chain(p, k+1, j) + p\[i-1]_p\[k]_&#x70;\[j]; if(q < m\[i]\[j]) { m\[i]\[j] = q; s\[i]\[j] = k; } } } return m\[i]\[j]; } int Medorized\_Matrix\_Chain(int _p) { int n = N, i, j; for(i = 1; i <= n; i++) { for(j = i; j <= n; j++) m\[i]\[j] = 0x7fffffff; } return Lookup\_Chain(p, 1, n); } //输出结果 void Print\_Optimal\_Parens(int_ p, int i, int j) { if(i == j) cout<<'A'<\<i; else { cout<<'('; Print\_Optimal\_Parens(p, i, s\[i]\[j]); Print\_Optimal\_Parens(p, s\[i]\[j]+1, j); cout<<")"; } } int main() { int A\[N+1] = {5, 10, 3, 12, 5, 50, 6}; int A2\[N+1] = {30, 35, 15, 5, 10, 20, 25}; //重叠子问题 memset(s, 0, sizeof(s)); cout<\<Recursive\_Matrix\_Chain(A, 1, N)<\<endl; Print\_Optimal\_Parens(A, 1, N); cout<\<endl; //做备忘录 memset(s, 0, sizeof(s)); cout<\<Medorized\_Matrix\_Chain(A)<\<endl; Print\_Optimal\_Parens(A, 1, N); cout<\<endl; return 0; }

15.4最长公共子序列

## include

using namespace std;

## define M 8

## define N 9

int b\[M+1]\[N+1] = {0}, c\[M+1]\[N+1] = {0}; int c2\[2]\[M+1] = {0}; /_**\*\***_&#x4E66;上的伪代&#x7801;_**\***_/ void Lcs\_Length(int _x, int_ y) { int i, j; //初始化 for(i = 1; i <= M; i++) c\[i]\[0] = 0; for(j = 1; j <= N; j++) c\[0]\[j] = 0; //根据公式15.14计算 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; b\[i]\[j] = 2; } else { if(c\[i-1]\[j] >= c\[i]\[j-1]) { c\[i]\[j] = c\[i-1]\[j]; b\[i]\[j] = 1; } else { c\[i]\[j] = c\[i]\[j-1]; b\[i]\[j] = 3; } } } } } //输出 void Print\_Lcs(int _x, int i, int j) { if(i == 0 || j == 0) return; if(b\[i]\[j] == 2) { Print\_Lcs(x, i-1, j-1); cout<\<x\[i]<<' '; } else if(b\[i]\[j] == 1) Print\_Lcs(x, i-1, j); else Print\_Lcs(x, i, j-1); } //15.4-2 不使用表b的情况下计算最LCS并输出 void Lcs\_Length2(int_ x, int _y) { int i, j; //初始化 for(i = 1; i <= M; i++) c\[i]\[0] = 0; for(j = 1; j <= N; j++) c\[0]\[j] = 0; //求LCS的时间没有什么区别，只要把与b有关的去掉就可以了 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 Print\_Lcs2(int_ x, int i, int j) { //递归到初始位置了 if(i == 0 || j == 0) return; //三种情况，刚好与Lcs\_Length2中的三种情况相对应（不是按顺序对应） //第二种情况 if(c\[i]\[j] == c\[i-1]\[j]) Print\_Lcs2(x, i-1, j); //第三种情况 else if(c\[i]\[j] == c\[i]\[j-1]) Print\_Lcs2(x, i, j-1); //第一种情况 else { //匹配位置 Print\_Lcs2(x, i-1, j-1); cout<\<x\[i]<<' '; } } //15.4-3备忘录版本，类似于递归，只是对做过的计算记录下来，不重复计算 //每一次迭代是x\[1..m]和y\[1..n]的匹配 int Lcs\_Length3(int _x, int_ y, int m, int n) { //长度为0，肯定匹配为0 if(m == 0|| n == 0) return 0; //若已经计算，直接返回结果 if(c\[m]\[n] != 0) return c\[m]\[n]; //公式15.14的对应 if(x\[m] == y\[n]) c\[m]\[n] = Lcs\_Length3(x, y, m-1, n-1) + 1; else { int a = Lcs\_Length3(x, y, m-1, n); int b = Lcs\_Length3(x, y, m, n-1); c\[m]\[n] = a > b ? a : b; } return c\[m]\[n]; } //15.4-4(1)使用&#x32;_&#x6D;in(m,n)及O(1)的额外空间来计算LCS的长度 void Lcs\_Length4(int_ x, int _y) { int i, j; //c2是&#x32;_&#x6D;in(M,N)的矩阵，初始化 memset(c2, 0 ,sizeof(c2)); //类似于上文的循环，只是i%2代表当前行，(i-1)%2代表上一行，其余内容相似 for(i = 1; i <= N; i++) { for(j = 1; j <= M; j++) { if(y\[i] == x\[j]) c2\[i%2]\[j] = c2\[(i-1)%2]\[j-1] + 1; else { if(c2\[(i-1)%2]\[j] >= c2\[i%2]\[j-1]) c2\[i%2]\[j] = c2\[(i-1)%2]\[j]; else c2\[i%2]\[j] = c2\[i%2]\[j-1]; } } } //输出结果 cout<= c2\[i%2]\[j-1]) c2\[i%2]\[j] = c2\[(i-1)%2]\[j]; else c2\[i%2]\[j] = c2\[i%2]\[j-1]; } } } cout<\<c2\[N%2]\[M]<\<endl; } void Print() { int i, j; for(i = 1; i <= M; i++) { for(j = 1; j <= N; j++) cout<\<c\[i]\[j]<<' '; cout<\<endl; } } int main() { int x\[M+1] = {0,1,0,0,1,0,1,0,1}; int y\[N+1] = {0,0,1,0,1,1,0,1,1,0}; Lcs\_Length(x, y); // Print(); Print\_Lcs(x, M, N); // Lcs\_Length2(x, y); // Lcs\_Length3(x, y, M, N); // Print(); // Print\_Lcs2(x, M, N); // Lcs\_Length4(x, y); return 0; }

15.5最优二叉查找树

## include

using namespace std;

## define N 7

double e\[N+2]\[N+2] = {0};//期望 double w\[N+2]\[N+2] = {0};//概率 int root\[N+2]\[N+2] = {0};//记录树的根结点的位置 /**\***&#x8C03;试过程中用于输出中间信&#x606F;_**\***_/ void PrintE() { int i, j; for(i = 1; i <= N+1; i++) { for(j = 1; j <= N+1; j++) cout<\<e\[i]\[j]<<' '; cout<\<endl; } cout<\<endl; } void PrintW() { int i, j; for(i = 1; i <= N+1; i++) { for(j = 1; j <= N+1; j++) cout<\<w\[i]\[j]<<' '; cout<\<endl; } cout<\<endl; } void PrintRoot() { int i, j; for(i = 1; i <= N+1; i++) { for(j = 1; j <= N+1; j++) cout<\<root\[i]\[j]<<' '; cout<\<endl; } cout<\<endl; } /_**\*\***_&#x4E66;上的伪代码对应的程&#x5E8F;**\*\***/ //构造最做树 void Optimal\_Bst(double _p, double_ q, int n) { int i, j, r ,l; double t; //初始化。当j=i-1时，只有一个虚拟键d|i-1 for(i = 1; i <= n+1; i++) { e\[i]\[i-1] = q\[i-1]; w\[i]\[i-1] = q\[i-1]; } //公式15.19 for(l = 1; l <= n; l++) { for(i = 1; i <= n-l+1; i++) { j = i+l-1; e\[i]\[j] = 0x7fffffff; //公式15.20 w\[i]\[j] = w\[i]\[j-1] + p\[j] + q\[j]; for(r = i; r <= j; r++) { //公式15.19 t = e\[i]\[r-1] + e\[r+1]\[j] + w\[i]\[j]; //取最小值 if(t < e\[i]\[j]) { e\[i]\[j] = t; //记录根结点 root\[i]\[j] = r; } } } } } /_**\*\***_&#x7EC3;&#x4E60;_**\*\***_/ //15.5-1输出最优二叉查找树 void Construct\_Optimal\_Best(int start, int end) { //找到根结点 int r = root\[start]\[end]; //如果左子树是叶子 if(r-1 < start) cout<<'d'<\<r-1<<" is k"<\<r<<"'s left child"<\<endl; //如果左子树不是叶子 else { cout<<'k'<\<root\[start]\[r-1]<<" is k"<\<r<<"'s left child"<\<endl; //对左子树递归使用Construct\_Optimal\_Best Construct\_Optimal\_Best(start, r-1); } //如果右子树是叶子 if(end < r+1) cout<<'d'<\<end<<" is k"<\<r<<"'s right child"<\<endl; //如果右子树不是叶子 else { cout<<'k'<\<root\[r+1]\[end]<<" is k"<\<r<<"'s right child"<\<endl; //对右子树递归使用Construct\_Optimal\_Best Construct\_Optimal\_Best(r+1, end); } } int main() { int n = N; // double p\[N+1] = {0, 0.15, 0.10, 0.05, 0.10, 0.20}; // double q\[N+1] = {0.05, 0.10, 0.05, 0.05, 0.05, 0.10}; double p\[N+1] = {0, 0.04, 0.06, 0.08, 0.02, 0.10, 0.12, 0.14}; double q\[N+1] = {0.06, 0.06, 0.06, 0.06, 0.05, 0.05, 0.05}; Optimal\_Bst(p, q, n); // PrintE(); // PrintW(); // PrintRoot(); cout<<'k'<\<root\[1]\[N]<<" is root"<\<endl; Construct\_Optimal\_Best(1, N); return 0; }

[ 第15章 动态规划](http://blog.csdn.net/mishifangxiangdefeng/article/details/7744512)
