动态规划（二）--钢条切割
问题描述：一家公司购买长钢条，将其切割成短钢条出售，切割本身没有成本，长度为i的短钢条的价格为Pi。那给定一段长度为n的钢条和一个价格表Pi,求钢条的切割方案使得收益Rn最大。如一个Pi如下：
长度i12345678910价格Pi1589101717202430
在距离钢条左端i长度处，我们总是可以选择切割或者不切割，所以长度为n的钢条共有2的n-1次方中不同的切割方案.
朴素的递归求解法：
我们可以将钢条从左边切下长为i的一段，只对右边剩下的n-i继续进行切割（递归求解）；即原问题的分解方式为：将长度为n的钢条分解成左边开始一段以及剩余部分继续分解的结果。可描述为：
Rn=max(Pi+Rn-i),其中1<=i<=n.
在这个公式中，原问题的最优解只包含一个相关子问题（右端剩余部分）的解，而不是两个。
PseudoCode：
CUT-ROD（P,n）
if n == 0
return 0
q = -∞
for i = 1 to n
q = max(q,p[i]+cut-ROD(p,n-i))
return q
Java实现代码如下：
/** * @author Bangwen Chen * * 2013-8-21 */public class Bottom_Up_Cut_Rod {public static void main(String args[]){long start = System.currentTimeMillis();int p[]={1,5,8,9,10,17,17,20,24,30,35,42,50,53,54,59,61,64,68,70,72,73,75,80,85,90,92,95,97,100,102};System.out.println(bottom_up_cut_rod(p,30));long end = System.currentTimeMillis();System.out.println("cost: " +(end-start));}static int bottom_up_cut_rod(int p[],int n){int r[]=new int [n+1];r[0]=0;for(int j=1;j<n+1;j++){int q = -1000;for(int i=1;i<j+1;i++){q=max(q,p[i-1]+r[j-i]);}r[j]=q;}return r[n];}static int max(int a,int b){return a>=b?a:b;}}Reference：Introduction to Algorithm(Thrid Edition) 机械工业出版社 2013