钢条切割问题：给定一段长度为n英寸的钢条和一个价格表pi（i=1,2,...,n）.求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条价格pn足够大，最优解可能就是完全不需要切割。
|
长度i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
价格p |
1 |
5 |
8 |
9 |
10 |
17 |
17 |
20 |
24 |
30 |
n = 4
方案 收益
1+1+1+1 r = 4
1+1+2 r = 7
2+2 r = 10
4 r =9
递归求解：采用朴素递归算法效率很低，需要反复求解相同的子问题。
将钢条从左边切割长度为i+1的一段（i从0开始），只对剩下的长度为n-(i+1)的一段进行切割（递归求解）。
公式：rn = max（pi+rn-i）
在此公式中，原问题的最优解只包含一个相关问题（右端剩余部分）的解，而不是两个。方法考察了所有的2n-1种可能的方案。T（n） = 2n
使用动态规划求解：仔细安排求解顺序，对每个问题只求解一次，并将结果保存下来。T（n） = Θ（n2）
n 带备忘的自顶向下法（top-down with memoization).
n 自底向上法（bottom-up method)。将子问题按规模排序，按由小到大的顺序进行求解。
两种方法仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销，自底向上方法的时间复杂性函数通常具有更小的系数。
#include<iostream> #include<algorithm> usingnamespace std; int cutRod(int * p, int n);//递归迭代，低效版。复杂度指数级 2^n int m_TD(int *p, int n, int *r);//memoized_top-down 备忘-自顶向下 N^2 int BD(int *p, int n);//button-up 自底向上法N^2 int ** ext_BD(int * p, int n);//exetenden button-up 自底向上的扩展算法。保存切割方案，保留第一段钢条的最优切割长度 void printSolution(int * p, int n); int main(){ int r[100];//保存子问题的求解值。 int p[] = { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 }; //int p[] = { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 ,32,42,52,55,56,58,60,63,66,70,80,100,110,120,130,140,150,160,170,180}; int money = cutRod(p, 4); int m = m_TD(p, 4, r); printSolution(p, 11);//查看前10根需要输入11. system("pause"); return 0; } int cutRod(int *p, intn){//n=钢条长度 if (n == 0){ return 0; } int maxValue = 0; for (int i = 0; i < n; i++) { int n2 = n - (i + 1);//拆分成i+1根，和n-（i+1）根， i = 0表示，拆分成1根和n-1根 maxValue = max(maxValue, p[i] + cutRod(p, n2)); } return maxValue; } //memoized_top-down 备忘-自顶向下 int m_TD(int *p,intn,int *r){//p = price保存价钱的数组，n = num钢条的长度，r保存收益的数组,即保存子问题的求解值，初始化为所有元素都为0。 /* n = 0 n = 1 i = 0, n2 = 0，第一根为1,第二根为0 q = max(0,p[0]+m_TD(p,0,r)) = 1; r[1] = 1; n = 2 i = 0, n2 = 1，第一根为1,第二根为1 q = max(0,p[0]+m_TD(p,1,r)) = max(0,1+1) = 2 ; i = 1, n2 = 0 ,第一根为2,第二根为0 q = max(2,p[1]+m_TD(p,0,r)) = max(5,2+0) = 5; */ int q = 0; if (r[n] >= 0){//判断是否已经有解。 returnr[n]; } if (n == 0) return 0; else { int n2 = 0; for (int i = 0; i < n; i++) { n2 = n - (i + 1); q = max(q, p[i] + m_TD(p, n2,r)); } } r[n] = q; return q; } //button-up 自底向上法 int BD(int *p, intn){ //n =2,依此求得r[1]、r[2]; /*i = 1, * j = 1, q = max(0,p[1-0] + r[0]) = 1; * r[1] = 1; */ /*i = 2, * j = 1, q = max(1,p[0] + r[1]) = 2;切分成2 = 1+1 * j = 2 q = max(5,p[1] + r[0]) = 5; 切分成2 = 2+0； * r[2] = 5; */ int r[100] = { 0 };//求解每个子问题i=1 -> n根钢条的问题解，求得解保存如r数组中。 for (int i = 1; i <= n; i++) { int maxValue = 0; int j = 1; for ( j; j <=i; j++) { maxValue = max(maxValue, p[j - 1] + r[i - j]); } r[i] = maxValue; } return r[n]; //尝试着将i j初始化0，但是没有找到对应的方法.还是按书上的初始化1. } //exetenden button-up 自底向上的扩展算法。保存切割方案，保留第一段钢条的最优切割长度 int ** ext_BD(int * p, intn){ staticint s[50] = { 0 }; staticint r[50] = { 0 };//求解每个子问题i=1 -> n根钢条的问题解，求得解保存如r数组中。 staticint *result[2] = { r, s };//result保存两个数组指针。 for (int i = 1; i <= n; i++) { int maxValue = 0; int j = 1; for (j; j <= i; j++) { int value = p[j - 1] + r[i - j]; if (maxValue < value){ maxValue = value; s[i] = j;//保留第一段钢条的最优切割长度 r[i] = maxValue; } } } return result; } void printSolution(int * p,intn){ int ** sol = ext_BD(p, n); int * r = sol[0]; int * s = sol[1]; for (int i = 0; i < n; i++) { cout << i << " r：" << r[i] << " first_cut: "<<s[i]<<endl; } }
参考文献： 殷建平等译.算法导论（第三版).机械工业出版社