动态规划的学习
动态规划
( dynamic programming)与分治方法相似，都是通过组合子问题的解来求解原问题(在
这里，“ programming”指的是一种表格法，并非编写计算机程序)。分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题(子问题的求解是递归进行的，将其划分为更小的子子问题)。在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。动态规划方法通常用来求解最优化问题( optimization problem)。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值(最小值或最大值)的解。我们称这样的解为问题的一个最优解( an optimal solution)，而不是最优解( the optimal solution)，因为可能有多个解都达到。
我们第一个应用动态规划的例子是：
求解一个如何切割钢条的简单问题。 Serling公司条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切假定我们知道 Serling公司出售一段长度为i英寸的钢条的价格为p,(i=1,2,…，单元)。钢条的长度均为整英寸。
|
长度i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
价格pi |
1 |
5 |
8 |
9 |
10 |
17 |
17 |
20 |
30 |
切割钢条方案，使得销售收益r最大。注意，如果长度为n英寸的钢条的价格pn,足够大这不需要切割:给定一段长度为n英寸的钢条和一个价格表p(i=1,2,
考虑m=4的情况。图15-2给出了4英寸钢条所有可能的切割方案，包括根本不切割的方案。
切割钢条方案，使得销售收益r最大。注意，如果长度为n英寸的钢条的价格pn,足够大这不需要切割:给定一段长度为n英寸的钢条和一个价格表p(i=1,2,
考虑m=4的情况。图15-2给出了4英寸钢条所有可能的切割方案，包括根本不切割的方案。
长度为n英寸的钢条共有2n-1中方案。
我们用普通的加法符号表示切割方案，因此7=2+2+3表示将长度为7英寸的钢条切割为三段一两段长度为2英寸、一段长度为3英寸如果一个最优解将钢条切割为k段(对某个1≤k≤n)，那么最优切割方案
n=i1+i2+…in
将钢条切割为长度分别为i,,…，a的小段，得到最大收益
r(n)=p1+p2+…+pn
对于上述价格表样例，我们可以观察所有最优收益值r(=1,2,…，10)及对应的最优切割方案
r1=1,切割方案1=1(无切割)
r2=5,切割方案2=2(无切割
r3=8,切割方案3=3(无切割)
r4=10,切割方案4=2+
r5=13,切割方案5=2
r6=17切割方案6=6(无切
r7=18,切割方案7=1+6或7=2+2+3
r8=22,切割方案8=2+6
r9=25,切割方案9=3+6
n=30,切割方案10=10(无切割)
们将钢条从左边切割下长度为i的一段，只对右边剩下的长度为n-i的一段继续进行切割(递归求解)对左边的一段则不再进行切割。即问题分解的方式为：将长度为n的钢条分解为左边开始一段以及剩余部分继续分解的结果。
递归求解
下面给出递归求解的方法：
#include <iostream> #include <string> #include<stdlib.h> using namespace std; int pi[] = {0,1,5,8,9,10,17,17,20,24,30 }; int cutRod(int pi[], int n); int main() { int maxprice= cutRod(pi, 9); cout << maxprice; } int cutRod(int pi[],int n) { if (n == 0) return 0; int q = -1; for (int i = 1; i <= n; i++) { int m = pi[i] + cutRod(pi, n - i); q = __max(q, m); } return q; } #include <iostream> #include <string> #include<stdlib.h> int memoCouRod(int pi[], int n, int r[]); using namespace std; int pi[] = {0,1,5,8,9,10,17,17,20,24,30 }; int cutRod(int pi[], int n); int main() { int maxprice= cutRod(pi, 9); cout << maxprice; } int cutRod(int pi[],int n) { int* r = new int[n]; for (int i = 1; i <= n; i++) r[i] = -1; return memoCouRod(pi, n, r); } int memoCouRod(int pi[], int n, int r[]) { if (r[n] > 0) return r[n]; else { int q = -1; if (n == 0) q = 0; else { for (int i = 1; i <= n; i++) { int m = pi[i] + memoCouRod(pi, n - i, r); q = __max(q, m); } return r[n] = q; } } }
第一种方法称为带备忘的自顶向下法( p-down with memoization)。此方法仍按自然的递白形式编写过程，但过程会保存每个子问题的解(通常保存在一个数组或散列表中)。当需要一个今于向题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了机算时间；否则，按通常方式计算这个子问题。我们称这个递归过程是带备忘的( memoized)，因为它“记住”了之前已经计算出的结果
第二种方法称为自底向上法( bottom-up method)，这种方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因而我们可以将子问题按规模排序，按由小至大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它(也是第一次遇到它)时，它的所有前提子问题都已求解完成
两种方法得到的算法具有相同的渐近运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销，自底向上方法的时间复杂性函数通常具有更小的系数。
带备忘的自顶向下法
#include <iostream> #include <string> #include<stdlib.h> int memoCouRod(int pi[], int n, int r[]); using namespace std; int pi[] = {0,1,5,8,9,10,17,17,20,24,30 }; int cutRod(int pi[], int n); int main() { int maxprice= cutRod(pi, 9); cout << maxprice; } int cutRod(int pi[],int n) { int* r = new int[n]; for (int i = 1; i <= n; i++) r[i] = -1; return memoCouRod(pi, n, r); } int memoCouRod(int pi[], int n, int r[]) { if (r[n] > 0) return r[n]; else { int q = -1; if (n == 0) q = 0; else { for (int i = 1; i <= n; i++) { int m = pi[i] + memoCouRod(pi, n - i, r); q = __max(q, m); } return r[n] = q; } } }
自底向上法
#include <iostream> #include <string> #include<stdlib.h> using namespace std; int bottonCouRod(int pi[], int n, int r[]); int pi[] = {0,1,5,8,9,10,17,17,20,24,30 }; int cutRod(int pi[], int n); int main() { int maxprice= cutRod(pi, 4); cout << maxprice; } int cutRod(int pi[],int n) { int* r = new int[n]; for (int i = 1; i <= n; i++) r[i] = -1; return bottonCouRod(pi, n, r); } int bottonCouRod(int pi[], int n, int r[]) { r[0] = 0; for (int j = 1; j <= n; j++) { int q = -1; for (int i = 0; i <= j; i++) { q = __max(q, pi[i] + r[j - i]); } r[j] = q; } return r[n]; }