正文之前
其实动态规划老早之前就看过, 但是可惜的是印象不深, 到今天彻底忘得差不多了, 这两天看算法导论终于让我啃下了二叉搜索树和红黑树两个家伙, 虽然还未曾熟练于胸, 但是基本能用了... 现在看到了动态规划, 这就不得不来搞一搞了.. 以一个最简单的钢条切割的示例来详解下我的收获
正文
首先发代码, 这个是自底向上的版本, 其他的版本不做多的解释, 这个最好用最直观.
- #include <iostream>
- #include<time.h>
- using namespace std;
- int max(int a,int b){
- return a>b?a:b;
- }
- int BOTTOM_UP_CUT(int p[], int n){
- int r[n];
- r[0]=0;
- for (int i = 1; i <= n; ++i)
- {
- int q=0;
- for (int j = 1; j <= i && j<11; ++j)
- {
- q = max(q,p[j] + r[i-j]);
- }
- r[i] = q;
- }
- return r[n];
- }
- int main(){
- // 输入数据
- int p[11] = {0,1,5,8,9,10,17,17,20,24,30};
- // 输入数据
- clock_t start = clock();
- cout<<BOTTOM_UP_CUT(p,10)<<endl;
- cout<<"Usage of Time:"<<clock()-start<<endl;;
- return 0;
- }
结果也是喜人:
大概的意思就是:
段 ---> 售价: 0
段 ---> 售价: 1
段 ---> 售价: 5
段 ---> 售价: 8
段 ---> 售价: 9
段 ---> 售价: 10
段 ---> 售价: 17
段 ---> 售价: 17
段 ---> 售价: 20
段 ---> 售价: 24
段 ---> 售价: 30
需要我们规划一个算法来解出对于任意的长度 n, 又怎样的切割方式来获取最大的利润?
那么, 我们以自底向上的思想来考虑的话, 对于任何一个长度 n 的钢条, 最大利润下的分割方案总是由左边的一段长度 i 和另外一段组合 (还要继续细分) 长度 n-i 组成. 假设最佳方案下的 i 不变, 那么我们只要考虑 n-i 的分割方案. 于是我们就可以考虑 n-i 长度的钢条如何切割.(至于如何确定 i? 当然是遍历了~)然后这么一直考虑下去, 最后总归会到 1 这个长度的. 这样的话就无法继续细分. 所以我们完全有:
那么代码就很好解释了
初始化 r[0] = 0, 这个意思是长度为 0 的时候总收益为 0;
- int BOTTOM_UP_CUT(int p[], int n){
- int r[n];
- r[0]=0;
对于左边的 i 的长度, 我们理所当然的从 1 开始算起, 这样的话, 就可以直接利用 r[1] = max(p[1],p[1]+r[0] )算出来了. 这样, 当我们需要算 r[2]的时候, 就可以看看, 到底是 p[1]+r[1] 大还是 p[2]+r[0]大了.. 然后就这么一路平推过去..
- for (int i = 1; i <= n; ++i)
- {
q 是在一次 i 分段过程中, 设置的最大收益寄存器.
int q=0;
这个过程就是来考察既定的左边段长 i 下如何获得右边 n-i 的最大收益的循环了. 别看一开始就用上了 r, 但是考虑到我们的 i 从 1 开始, 所以一开始只需要 r[0]就可以计算出 r[1], 等到后面要别的了. 就会发现前面已经把所有的子问题都铺垫好了.
- for (int j = 1; j <= i && j<11; ++j)
- {
- q = max(q,p[j] + r[i-j]);
- }
不得不说这个 q 真的用的妙, 初始为 0 的话, 完全就可以视作为 r[0]使用. 而后每一次循环结束都会刷新它的值, 也就是对于 n-i 这一段, 如果再把它细分, 每一次细分之下的结果中的最大值会放到 q 中去, 自然而然, 一轮循环下来, q 就存储了 r[n-i]的最大值了..
- r[i] = q;
- }
- return r[n];
- }
正文之后
不缩了不缩了.. 撤撤撤.. 准备吃饭去了晚上还接了个音控岗的班还要去冲饮水卡.. 贼恼火...
来源: http://www.jianshu.com/p/7de9f30e7655