动态规划(二)--钢条切割

发布时间:2016-12-9 19:43:03 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"动态规划(二)--钢条切割",主要涉及到动态规划(二)--钢条切割方面的内容,对于动态规划(二)--钢条切割感兴趣的同学可以参考一下。

问题描述:一家公司购买长钢条,将其切割成短钢条出售,切割本身没有成本,长度为i的短钢条的价格为Pi。那给定一段长度为n的钢条和一个价格表Pi,求钢条的切割方案使得收益Rn最大。如一个Pi如下: 长度i 1 2 3 4 5 6 7 8 9 10 价格Pi 1 5 8 9 10 17 17 20 24 30 在距离钢条左端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 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(cut_rod(p,30)); long end = System.currentTimeMillis(); System.out.println("cost: " +(end-start)); } static int cut_rod(int p[],int n){ if(n==0){ return 0; } int q=-1000; for(int i=1;i<n+1;i++){ // System.out.println(i); // System.out.println("i=" + i+" "+(p[i-1]+cut_rod(p,n-i))); q=max(q,p[i-1]+cut_rod(p,n-i)); // System.out.println(q); } return q; } static int max(int a,int b){ return a>=b?a:b; } } 运行时间67656ms左右(笔记本烂也是一大要素。。),但是关键还是在于算法效率低下,其原因在于CUT-ROD反复调用相同的参数值对自身进行递归调用,以n=4为例,当i=1时,n-i=3,那么子问题n=3要对子子问题n=2进行求解;但是当i=2,n-i就也等于2,相当于子问题是n=2,在这个过程中就重复求解了n=2的最优值,即在反复求解相同的子问题,T(n) =2^n;即运行时间为n的指数函数。 动态规划方法 对应与上一篇的动态规划原理,钢条切割问题显然是个最优化问题 对于Rn,我们可以用更短的钢条的最优切割收益来描述它:Rn=MAX(Pn,R1+Rn-1,R2+Rn-2,...,Rn-1+r1);其中第一个参数对应不切割直接出售整根钢条的方案。可以注意到的是当首次切割完成后,我们可以将两段钢条看成两个独立的钢条切割实例,对于这两个子问题我们有可以选取组合收益最大者,构成原问题的最优解。所以我们称钢条切割问题满足最优子结构的性质:问题的最优解由相关子问题的最优解组合而成,而这些子问题可以独立求解。下面将分别给出上一篇(http://blog.csdn.net/bianghoo/article/details/10737089)介绍的两个实现方法的伪代码和java代码 带备忘的自顶向下法: PseudoCode MEMOIZED-CUT_ROD(p,n) let r[0...n] be a new array for i = 0 to n r[i] = -∞ return MEMOIZED-CUT-ROD-AUX(p,n,r) MEMOIZED-CUT-ROD-AUX(p,n,.r) if r[n] >= 0   return r[n] if n == 0 q = 0 else q =-∞ for i = 1 to n q =max(q,p[i]+MEMOIZED-CUT-ROD-AUX(p,n,.r)) r[n]=q return q java代码 /** * @author Bangwen Chen * * 2013-8-21 */ public class Top_Down_with_Memoization { 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(memoized_cut_rod(p,30)); long end = System.currentTimeMillis(); System.out.println("cost: " +(end-start)); } static int memoized_cut_rod(int p[],int n){ int r[]=new int[n+1]; for(int i=0;i<n+1;i++){ r[i]=-100; } return memorized_cut_rod_aux(p,n,r); } static int memorized_cut_rod_aux(int p[],int n,int r[]){ if (r[n]>=0){ return r[n]; } int q; if(n==0){ q=0; }else{ q=-1000; for(int i=1;i<n+1;i++){ q=max(q,p[i-1]+memorized_cut_rod_aux(p,n-i,r)); } } r[n]=q; return q; } static int max(int a,int b){ return a>=b?a:b; } } 自底向上法 BOTTOM-UP-CUT-ROD(p,n) let r[0...n] be a new array for j = 0 to n q = -∞ for i = 1 to j q =max(q,p[i]+r[j-i]) r[j] = q return r[n] 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; } } 两个程序的运行时间均为0ms,两个算法既有相同的渐进运行时间。  Reference:Introduction to Algorithm(Thrid Edition) 机械工业出版社 2013

上一篇:Qt Creator 配置Msvc 2012的调试器
下一篇:CFileDialog的详解(转)

相关文章

相关评论