动态规划 (Dynamic Programming)
什么是动态规划?
动态规划算法通常基于一个递推公式及一个或多个初始状态当前子问题的解将由上一个子问题的解推出
动态规划和分治法相似, 都是通过分解, 求解, 并组合子问题来求解原问题分治法将问题划分成相互独立互不相交的子问题, 递归求解子问题, 再将它们的解组合起来, 求出原问题的解与之相反, 动态规划应用于子问题重叠的情况, 即不同的子问题具有公共的子子问题在这种情况下, 分治算法会做出许多不必要的工作, 它会反复的求解那些公共子子问题而动态规划算法对每个子子问题只求解一次, 将结果保存到表格 (数组) 中, 从而无需每次求解一个子子问题都要重新计算
动态规划之钢条切割问题
假定我们知道某公司出售一段长度为 i 英寸的钢条的价格为 p[i](i=1,2,3.)钢条长度为整英寸如图给出价格表的描述(任意长度的钢条价格都有)
现在先给一段长度为 n 的钢条, 问怎么切割, 获得的收益最大 rn?
考虑 n=4 的时候, 有以下 8 种切割方式
假如一个最优解把 n 段切成了 k 段(1<=k<=n), 那么最优切割方案:
i 及下标表示第 i 段的长度, n 为钢条的总长度
最大收益:
p 及下标表示第 i 段的收益, r 为钢条的总收益
接下来对这个问题进行求解, 我们先用普通的递归方法求解:
我们从钢条的左边切下长度为 i 的一段, 只对右边剩下长度为 n-i 的一段继续进行切割, 对左边的不再切割
这样, 当第一段长度为 n 的时候, 收益为 p[n], 剩余长度为 0, 收益为 0(这也是递归的基本问题), 对应的总收益为 p[n]
当第一段长度为 i 的时候, 收益为 p[i], 剩余长度为 n-i, 对应的总收益为 p[i]加上剩余的 n-i 段再进行当第一段长度为 i 的时候, 收益为 p[i], 剩余长度为 n-i-i,.... 直到剩余长度为 0, 收益为 0
所以递归方程式为:
pi 就是就是 p[i], 可以看出每次都要进行从 1 到 n 的遍历
代码实现 - 自顶向下递归实现
- #include <iostream>
- int UpDown(int n, int * p)// 参数 n 是长度, 参数 p 是价格表
- {
- if (n == 0) return 0;// 递归的基本问题
- int tempMaxPrice = 0;
- for (int i = 1; i <n + 1; i++)
- {
- int maxPrice = p[i] + UpDown(n - i, p);
- if (maxPrice> tempMaxPrice)
- {
- tempMaxPrice = maxPrice;
- }
- }
- return tempMaxPrice;
- }
- int main()
- {
- int p[11]{ 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };// 索引代表 钢条的长度, 值代表价格
- std::cout <<UpDown(4,p) <<std::endl;
- }
动态规划的方法进行求解
上面的方法之所以效率很低, 是因为它反复求解相同的子问题比如求 r[9]和 r[8]的时候都求解了 r[7], 就是说 r[7]被求解了两次因此, 动态规划算法安排求解的顺序, 对每个子问题只求解一次, 并将结果保存到数组中如果随后再次需要此子问题的解, 只需查找保存的结果, 不必重新计算因此动态规划的方法是付出额外的内存空间来节省计算时间
动态规划有两种等价的实现方法(我们使用上面的钢条切割问题为例, 实现这两种方法)
第一种方法是 带备忘的自顶向下法:
此方法依然是按照自然的递归形式编写过程, 但过程中会保存每个子问题的解 (通常保存在一个数组中) 当需要计算一个子问题的解时, 过程首先检查是否已经保存过此解如果是, 则直接返回保存的值, 从而节省了计算时间; 如果没有保存过此解, 按照正常方式计算这个子问题我们称这个递归过程是带备忘的
代码实现 - 自顶向下动态规划实现
- #include <iostream>
- int result[11]{ 0 };
- int UpDown(int n, int* p)// 求得长度为 n 的最大收益
- {
- if (n == 0) return 0;
- if (result[n] != 0)// 这里直接返回记录的结果
- {
- return result[n];
- }
- int tempMaxPrice = 0;
- for (int i = 1; i <n + 1; i++)
- {
- int maxPrice = p[i] + UpDown(n - i, p);
- if (maxPrice> tempMaxPrice)
- {
- tempMaxPrice = maxPrice;
- }
- }
- result[n] = tempMaxPrice;// 将计算过的长度为 n 的钢条切割的最大收益记录起来
- return tempMaxPrice;
- }
- int main()
- {
- int p[11] = { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };// 索引代表 钢条的长度, 值代表价格
- std::cout <<UpDown(4,p);
- }
第二种方法是 自底向上法(常用的方法):
首先恰当的定义子问题的规模, 使得任何问题的求解都只依赖于更小的子问题的解因而我们将子问题按照规模排序, 按从小到大的顺序求解当求解某个问题的时候, 它所依赖的更小的子问题都已经求解完毕, 结果已经保存到了数组中
代码实现 - 自底向上动态规划实现
- #include <iostream>
- int result[11]{ 0 };
- int BottomUp(int n, int* p)
- {
- for (int i = 1; i <n + 1; i++)
- {
- int tempMaxPrice = 0;
- for (int j = 1; j <= i; j++)// 下面取得 钢条长度为 i 的时候的最大收益
- {
- int maxPrice = p[j] + result[i - j];
- if (maxPrice> tempMaxPrice)
- {
- tempMaxPrice = maxPrice;
- }
- }
- result[i] = tempMaxPrice;
- }
- return result[n];
- }
- int main()
- {
- int p[11] = { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };// 索引代表 钢条的长度, 值代表价格
- std::cout << BottomUp(4,p);
- }
可以看出自顶向下的动态规划求解和普通的递归求解差不多, 不过动态规划递归调用时带了备忘录, 记录了已经解决的问题, 所以对于上文提到的 r[7], 我们只求解了一次
自底向上的动态规划也用了备忘录, 不过它只是迭代求解, 并没有进行递归, 所以这也是我们常用方法
以上有什么不足的地方和应该改进的地方, 欢迎各路大神批评指正, 笔者一定虚心接受谢谢!
来源: https://www.cnblogs.com/DA799422035/p/8684219.html