疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

动态规划之钢条切割


 

  一段已知的钢条求解如何切割受益最大。只是算法导论书中动态规划中的问题。

  价格如下:int price[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};//price[0]=0 表示长度0的钢条价格为0这里采用了动态规划中的带备忘的自底向上的方法。具体看代码,有很详细的注释

  package blut.Algorithms.dongtaiguihua;

  /**

  * 动态规划之 钢条切割最优问题

  * 采用了备忘录模式的 自底向上的递推模式

  * @author blut

  *

  *

  */

  public class Demo1 {

  public void func(int[] price,int n){

  int res[][]=sub(price,n);

  System.out.println("受益为"+res[0][n]);

  //输出最优方案

  System.out.print("方案是");

  while(n>0){

  System.out.print(res[1][n]+" ");

  n=n-res[1][n];

  }

  System.out.println();

  }

  public int[][] sub(int[] price,int n){

  int temp[][]=new int[2][n+1];//temp[0][2]表示2的钢条的最佳受益,temp[1][2]表示2的钢条的最佳切割点

  temp[0][0]=0;

  temp[1][0]=0;

  for(int i=1;i<=n;i++){

  int q=-9999;

  for(int j=1;j<=i;j++){

  if(q

  q=price[j]+temp[0][i-j];

  temp[1][i]=j;//更新最佳的切割点。表示长度为i的钢条切割点在j上最优

  }

  }

  temp[0][i]=q;//g更新最佳的受益,

  }

  return temp;

  }

  public static void main(String []arg){

  int price[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

  int n=8;

  new Demo1().func(price,n);

  }

  }

  输出结果为

  受益为22

  方案是2 6

  各位应该看得懂吧,不理解的部分希望能说明,我会详细写下来的。