首页 / 算法 / 《算法导论》中动态规划求解钢条切割问题
《算法导论》中动态规划求解钢条切割问题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《算法导论》中动态规划求解钢条切割问题,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3370字,纯文字阅读大概需要5分钟。
内容图文
动态规划算法概述
动态规划(dynamic programming)1是一种与分治方法很像的方法,都是通过组合子问题的解来求解原问题。不同之处在于,动态规划用于子问题重叠的情况,比如我们学过的斐波那契数列。在斐波那契数列的求解问题中,我们经常要对一个公共子问题进行多次求解,而动态规划算法,则对每个子问题只求解一次,将其解保存在一个表格中,从而避免了大量的冗余计算量。
动态规划算法常用于寻找最优解问题(optimization problem)。而其规划大概可分为四步:
1.刻画一个最优解的结构特征。
2.递归的定义最优解的值。
3.计算最优解的值。
4.利用计算出的信息构造一个最优解2。
我们将以《算法导论》中的一个习例作为展示的对象,讲解动态规划算法的应用方法。
钢条切割问题
现有某公司,购买长钢条以切割成短钢条出售。若不计切割成本,请求出如何切割以使公司利益最大。该公司短钢条售价如下:
长度:1 2 3 4 5 6 7 8 9 10
价格:1 5 8 9 10 17 20 24 30
现假设一段钢条的长度为n,我们可以试求当 n = 4时,我们能获得的最大收益。此时,我们对于第一次分割有5种选择(0,1,2,3,4),以此类推,对于n = 4的情况,我们一共有8种情形:(4),(1,3),(2,2),(3,1),(1,1,2),(1,2,1),(2,1,1),(1,1,1,1)。易算得,最高价值为(2,2)情况下取得,最高收益为10.
那么,我们如何用函数来描述这一过程呢?首先,我们可以假设第一次切割所得的第一部分钢条长度为x (属于[0,n])。则我们现在有了两根钢条,一根长为x,另一根长为 n - x。那么长为n的钢条所得利益的最优解就来自于长为x 和 n - x两段钢条最优解的和。如此划分,即可将问题逐步化简为一个个子问题,以R来表示公司所得利益,P来表示钢条单价,则有R对n的函数:
R n = max(P x + R (n - x) )。
普通递归方法实现
可以看出上述公式是一个很明显的递归函数,我们很容易就可以得到下列代码:
1 #include<iostream> 2 #include<vector> 3 #include<algorithm> 4#define null -1 5using namespace std; 6 7int cut_rod(int n, vector<int> p) { 8if (n == 0) return 0; 9int q = null; 10for (int i = 1; i <= n; i++) { 11 q = max(q , p[i-1] + cut_rod(n - i, p) ); 12} 13return q; 14} 15 16int main() { 17 cout << "输入产品各段数所对应的价格(从小到大)" << endl; 18int n = 0; 19 vector<int> p; 20while (cin >> n && n != null) { //输入-1表示停止21p.push_back(n); 22 n = 0; 23} 24 vector<int> results(p.size() + 1, null); //在result中创建n + 1个元素([0,n]共n+1个),并统一赋值为null25 cout << "请输入所需切割钢材长度" << endl; 26 cin >> n; 27 cout << cut_rod(n, p); 28//cout << memo_cut_rod(n, p, results); 29//cout << bot_cut_rod(n, p, results);30return 0; 31 }
我们已在斐波那契数列的学习中证明了,这种算法的缺点是很明显的,随着递归的深入,其计算量会爆炸性的增长。易得其时间复杂度 : T = 2N。
那么我们要怎么利用动态规划的方法来进行简便运算呢?方法有两种:一种称之为带备忘的自顶向下法(top-down with memoization3),另一种则是自底向上法(bottom-up method)。
带备忘的自顶向下法
此方法与正常的递归方法并无太大区别,但在过程中,每一个子问题的解都会被保存下来,在每次求解之前都会验证是否已经对该子问题进行了求解,若是,则直接返回保存的值;不是,再进行正常运算。据此理论,易得代码:
1 int memo_cut_rod(int n, vector<int> p, vector<int> results) { 2if (results[n] > 0) return results[n]; 3if (n == 0) return 0; 4int q = null; 5for (int i = 1; i <= n; i++) { 6 q = max(q, p[i - 1] + memo_cut_rod(n - i, p,results)); 7} 8return q; 9} 10 11 12int main() { 13 cout << "输入产品各段数所对应的价格(从小到大)" << endl; 14int n = 0; 15 vector<int> p; 16while (cin >> n && n != null) { //输入-1表示停止17p.push_back(n); 18 n = 0; 19} 20 vector<int> results(p.size() + 1, null); //在result中创建n + 1个元素([0,n]共n+1个),并统一赋值为null21 cout << "请输入所需切割钢材长度" << endl; 22 cin >> n; 23//cout << cut_rod(n, p);24 cout << memo_cut_rod(n, p, results); 25return 0; 26 }
自底向上法
自底向上法采用了与正常递归相似的顺序,但免除了从顶到下的过程以及冗余的计算,直接从最小问题算起,最后构成最优解。其代码如下:
int bot_cut_rod(int n,vector<int> p,vector<int> results) { results[0] = 0; for (int j = 1; j <= n; ++j) { int q = null; for (int i = 1; i <= j; ++i) { q = max(q, p[i -1] + results[j - i]); } results[j] = q; } return results[n]; }
总结
自底向上法与带备忘的自顶向下法具有相同的渐进运行时间,两者的时间复杂度都为 T = n2。相比之前的2n强了太多。而使用动态规划算法的重中之重,是找好问题划分的方法,将问题一步一步化简到最小,把大问题化简成一个个小问题,小问题往往比大问题好解的多,最后再由小问题推导出大问题的答案,就算是大功告成了。
注释:
1.此处的programming是指一种表格法,而非编程
2.当我们仅仅需要一个最优解的值的时候,我们往往可以省略掉第4步。
3.此处并非拼写错误,确实为memoization,而非memorization。前者源自memo,为备忘之意。
参考文献:
《算法导论》
原文:http://www.cnblogs.com/PabloZeal/p/6657961.html
内容总结
以上是互联网集市为您收集整理的《算法导论》中动态规划求解钢条切割问题全部内容,希望文章能够帮你解决《算法导论》中动态规划求解钢条切割问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。