急：算法高手请进。有一个难题求解？

急：算法高手请进。有一个难题求解？  
  标准原材料长600cm。  
  可能要截成以下几种规格：60cm、80cm、90cm、120cm、150cm、180cm、210cm、2400cm的任意几种的组合。  
  比方说：  
  方案一：需要60cm28根、210cm16根、240cm8根，最少需要多少根原材料（600cm）  
  方案....  
  此解主要解决怎么才能最省料。  
  另：能否解任意规格尺寸的问题。 问题点数：100、回复次数：46Top

1 楼newmeteor（圆缘）回复于 2005-04-22 12:00:53 得分 0

老问题，装箱问题！Top

2 楼zdf_zhang（杀倭少将）回复于 2005-04-22 12:04:32 得分 0

高手请解答Top

3 楼zdf_zhang（杀倭少将）回复于 2005-04-22 16:20:36 得分 0

比装箱问题难多了Top

4 楼zdf_zhang（杀倭少将）回复于 2005-04-22 19:59:44 得分 0

上面有误：可能要截成以下几种规格：60cm、80cm、90cm、120cm、150cm、180cm、210cm、240cm的Top

5 楼sjjf（水晶剑锋）回复于 2005-04-22 21:59:15 得分 0

单纯行法的   截料问题的应用   google   一下就能找到很详细的答案   呵呵  
  Top

6 楼miyimei（）回复于 2005-04-24 11:00:14 得分 5

如果裁成的每种规格只有一根，就是装箱，但是有很多根，要用数学建模  
  （1）我们先找出每根原料有多少切割模式，每根原料长600cm  
                          60cm(根)                   210cm(根)                 240cm(根)             剩余(cm)  
  模式1                 10                                 0                                 0                             0  
  模式2                   6                                 1                                 0                             30  
  模式3                   3                                 2                                 0                             0  
  漠视4                   6                                 0                                 1                             0  
  模式5                   2                                 0                                 2                             0  
  模式6                   2                                 1                                 1                             30  
  设第i种模式切割xi根(xi>=0)的时候需要原料最少，则所求的目标就是  
  Min   Z=x1+x2+x3+x4+x5+x6                       ...1  
  根据客户的需求，需要60cm28根、210cm16根、240cm8根，可以得到约束条件：  
  10x1+6x2+3x3+6x4+2x5+2x6>=28             ...2  
  x2+2x3+x6>=16                                           ...3  
  x4+2x5+x6>=8                                             ...4  
  由1-4式，依线性规划的方法可以求解Z  
   
  (2)不知道你说的任意尺寸是指什么，完全抽象的方法不好理解，还是用上面的题  
   
  标准原材料长600cm。  
  可能要截成以下几种规格：60cm、80cm、90cm、120cm、150cm、180cm、210cm、240cm的任意几种的组合。  
  需要60cm28根、210cm16根、240cm8根，最少需要多少根原材料（600cm）  
   
  增加一种，还要150cm的20根，需求的规格增加到4种，不要再枚举出所有的切割模式了，只要求出有一根原料几种切割模式，很容易用程序求出，设为n种  
  建立一个矩阵：  
                                  60cm               150cm                       210cm                     240cm  
  模式1                         r11                   r21                         r31                           r41  
  模式2                         r12                   r22                         r32                           r42  
  .  
  .  
  模式n                         r1n                   r2n                         r3n                           r4n  
  每种模式切割原料xi根  
  目标   Min   Z=x1+x2+...+xn                   ...5  
  约束条件：  
  a.满足客户需求      
  r11*x1+r12*x2+...+r1n*xn>=28  
  r21*x1+r22*x2+...+r2n*xn>=20  
  r31*x1+r32*x2+...+r3n*xn>=16  
  r41*x1+r42*x2+...+r4n*xn>=8  
  b.因为每种切割模式必须可行，合理，所以每根原料所使用的长度必须<=600cm,>=540cm,得到另外的约束条件：  
  540<=60r11+150r21+210r31+240r41<=600  
  540<=60r12+150r22+210r32+240r42<=600  
  ...  
  540<=60r1n+150r2n+210r3n+240r4n<=600  
  c.总原料的根数不能少于  
  Z>=(60*28+150*20+210*16+240*8)/600=16.6，既是Z>=17  
  d.因为切割模式和排列顺序无关，假设x1>=x2>=...>=xn  
  由5式和约束条件a,b,c,d可求解。  
   
   
  如果你会用线性规划软件Lindo的话，可以把条件输进去试试，但是计算规模不要太大。自己编程也可以，反正按照上面的模型啦。问题(2)计算比较复杂，设n=3的话Lindo也要算好几分钟的。Top

7 楼miyimei（）回复于 2005-04-24 11:03:15 得分 5

对了，用Lindo不仅可以得到总根数Z，还可以得到每种切割模式的切割方法，按这种切割方法切多少根  
   
  你可以自己编程算算上面的规划模型Top

8 楼zdf_zhang（杀倭少将）回复于 2005-04-25 11:37:58 得分 0

用线性规划的话，如果组合的种类达到10种，   数量达到万，您认为不用超级计算机能算出来吗？Top

9 楼ogogohg（blog.csdn.net/ogogohg）回复于 2005-04-25 21:14:08 得分 0

可以这样嘛，在问题2里面，设置条件，根据实际情况，没必要采用过多的切割模式，限定采用3－4种模式切割就可以了，结果很接近理论最优值  
  对于组合的增加，问题规模变大，只有增加假设的约束条件，求取近似值，也是实际有意义的值  
   
  或者你有什么别的好办法？？Top

10 楼ogogohg（blog.csdn.net/ogogohg）回复于 2005-04-25 21:17:50 得分 0

不好意思，我是马甲，说明一下Top

11 楼zdf_zhang（杀倭少将）回复于 2005-04-26 10:22:31 得分 0

只限定3-4种，就达不到实际要求了。Top

12 楼zdf_zhang（杀倭少将）回复于 2005-05-08 09:44:55 得分 0

求解Top

13 楼yelling（Ray（←☆→射手））回复于 2005-05-08 13:09:22 得分 0

用组合数学中的母函数做  
  不过搂主没给出数据的范围。Top

14 楼windywoman（风过忘忧）回复于 2005-05-13 20:06:31 得分 90

用方案评定法。先把所有可能的分法列出来，再根据权值来判断什么分法最好。比如一种分法为6个60的，1个240的，与另外一种方法：3个60的，2个210的，哪种分法更好呢？我的考虑是，如果剩下的都是60的，那么是可以每10个消耗1根600的，就不会剩下废料，但要是剩下的都是240的，那么每两根240的就要消耗1根600的，剩下120的废料。所以每根240的可能产生60的废料。那么每种方案用掉一根240的，就会减少产生60废料的可能，就给加60的权值分。当然，如果此方案已经造成废料，那么造成多少废料，就减多少权值分。所以，6个60，1个240的分法的权值分是60，而3个60，2个210的权值分是180，所以后面的分法比前面的好。  
  所以结果就是用所有的方法按权值大小进行分割，先用权值最大的分，直到不能分（因为会造成某种原料的需求已经达到），换权值第二的，依此类推，直到所有需要的材料都已切割出来。  
   
  以下是我写的程序。输入文件input.txt的格式为：  
  600  
  60   80   90   120   150   180   210   240  
  28   0   0   0   0   0   16   8  
  输出文件为output.txt.  
  我这个程序的问题是分法实在太多了，现在这个已知条件还不能造成分法太多，但是如果原材料的长度再大，或者可分的程度再多，那么方案就太多了。比如如果原材料长度为1000的时候，分法就已达到3000多种。应该还可以优化，因为基本上只有最后1根原材料时才会需要那些权值特别差的分法。不过还是有可能用到权值小于0的分法的，所以分法如何取舍不好决定。  
  此程序能满足任意的规格尺寸。  
   
  import   java.io.BufferedInputStream;  
  import   java.io.OutputStreamWriter;  
  import   java.io.DataInputStream;  
  import   java.io.BufferedWriter;  
  import   java.io.FileInputStream;  
  import   java.io.FileNotFoundException;  
  import   java.io.FileOutputStream;  
  import   java.io.IOException;  
  import   java.util.Vector;  
   
  public   class   Assign   {  
   
          public   static   void   main(String[]   args)   {  
                  DataInputStream   in=null;  
                  BufferedWriter   out=null;  
                  try{  
                          in   =   new   DataInputStream(new   BufferedInputStream(new   FileInputStream("input.txt")));  
  out   =   new   BufferedWriter(new   OutputStreamWriter(new   FileOutputStream("output.txt"),"gb2312"));  
                          int   aimlen   =   Integer.parseInt(in.readLine());  
                          String[]   s   =   in.readLine().split("   ");  
                          String[]   s2   =   in.readLine().split("   ");  
  in.close();  
  in   =   null;  
                          Vector   ways   =   new   Vector();  
                          int[]   spit   =   new   int[s.length];  
                          int[]   nums   =   new   int[s2.length];  
  out.write("原料每根长度："+aimlen+"\n");  
                          for(int   i=0;i<s.length;i++){  
                                  spit[i]   =   Integer.parseInt(s[i]);  
                          }  
                          for(int   i=0;i<s2.length;i++){  
                                  nums[i]   =   Integer.parseInt(s2[i]);  
                                  out.write("需长度"+spit[i]+"的材料"+nums[i]+"根。"+"\n");  
                          }  
  int   g=0;  
  for(int   i=0;i<spit.length;i++){  
  g+=spit[i]*nums[i];  
  }  
  int   x   =   (g-g%aimlen)/aimlen;  
  if(g%aimlen!=0)  
  x++;  
  out.write("\n"+"期望根数为："+x);  
                          ways   =   getWays(spit,aimlen,spit.length,nums);  
                          int[][]   sortWay   =   sortWays(ways,spit,aimlen);  
                          out.write("\n");  
  for(int   j=0;j<spit.length;j++){  
          out.write(spit[j]+"米\t");  
  }  
  out.write("废料\t");  
  out.write("加权值");  
  for(int   i=0;i<sortWay.length;i++){  
          out.write("\n");  
  for(int   j=0;j<spit.length;j++){  
          out.write(sortWay[i][j]+"\t");  
  }  
  out.write(sortWay[i][sortWay[i].length-2]+"\t");  
  out.write(sortWay[i][sortWay[i].length-1]+"");  
  }  
                          int[]   results   =   getResult(sortWay,nums);  
                          out.write("\n"+"实际所需根数为："+getTotal(results));  
                          out.write("\n分配方案为：");  
                          int   count   =   0;  
                          for(int   i=0;i<results.length;i++){  
                                  if(results[i]!=0){  
                                          count++;  
                                          out.write("\n第"+count+"种方案如下，共分配"+results[i]+"次：");  
                                          for(int   j=0;j<spit.length;j++){  
                                                  if(sortWay[i][j]!=0){  
                                                          out.write("长度为"+spit[j]+"的分配"+sortWay[i][j]+"次：");  
                                                  }  
                                          }  
                                  }  
                          }  
  out.close();  
  out   =   null;  
                  }catch(FileNotFoundException   e){  
                          System.out.println("请写好输入文件");  
                          e.printStackTrace();  
                  }catch(IOException   e2){  
                          System.out.println("输入输出流错误");  
                          e2.printStackTrace();  
                  }finally{  
                          try{  
  if(in!=null){  
  in.close();  
  in=null;  
  }  
  if(out!=null){  
  out.close();  
  out=null;  
  }  
                          }catch(IOException   e3){  
                                  e3.printStackTrace();  
                          }  
                  }    
          }  
           
          public   static   int   getTotal(int[]   a){  
                  int   b=0;  
                  for(int   i=0;i<a.length;i++){  
                          b+=a[i];  
                  }  
                  return   b;  
          }  
           
          public   static   int   min(int   a,int   b){  
                  return   (a<b)?a:b;  
          }  
           
          public   static   Vector   getWays(int[]   a,int   b,int   n,int[]   e){  
                  Vector   c   =   new   Vector();  
                  Vector   d   =   null;  
                  int[]   tmp;  
                  if(n==1){  
                          for(int   i=0;i<=min((b-b%a[a.length-1])/a[a.length-1],e[a.length-1]);i++){  
                                  c.add(new   int[]{i,0,0});  
                          }  
                  }else{  
                          for(int   i=0;i<=min((b-b%a[a.length-n])/a[a.length-n],e[a.length-n]);i++){  
                                  d   =   getWays(a,b-a[a.length-n]*i,n-1,e);  
                                  for(int   j=0;j<d.size();j++){  
                                          tmp   =   new   int[((int[])d.get(j)).length+1];  
                                          tmp[0]   =   i;  
                                          for(int   k=1;k<tmp.length;k++){  
                                                  tmp[k]   =   ((int[])d.get(j))[k-1];  
                                          }  
                                          c.add(tmp);  
                                  }  
                                  d   =   null;  
                          }  
                  }  
                  return   c;  
          }  
           
          public   static   int[][]   sortWays(Vector   c,int[]   a   ,int   b){  
                  int[][]   d   =   new   int[c.size()][a.length+2];  
                  int   f,g;  
                  int[]   tmp   =   null;  
                  for(int   i=0;i<c.size();i++){  
                          g=0;  
                          tmp   =   (int[])c.get(i);  
  for(int   j=0;j<a.length;j++){  
  g+=tmp[j]*a[j];  
  }  
                          tmp[tmp.length-2]   =   b-g;  
  g=0;  
                          for(int   j=0;j<tmp.length-2;j++){  
                                  f   =   (b-b%a[j])/a[j];  
                                  g   +=   (b%a[j])*tmp[j]/f;    
                          }  
                          tmp[tmp.length-1]   =   g-tmp[tmp.length-2];  
                          d[i]=tmp;  
                  }  
                  for(int   i=0;i<d.length-1;i++){  
                          for(int   j=i+1;j<d.length;j++){  
                                  if(d[j][d[j].length-1]>d[i][d[i].length-1]){  
                                          tmp   =   d[i];  
                                          d[i]   =   d[j];  
                                          d[j]   =   tmp;  
                                  }  
                          }  
                  }  
                  return   d;  
          }  
           
          public   static   int[]   getResult(int[][]   c,int[]   a){  
                  int[]   b   =   new   int[c.length];  
                  for(int   i=0;i<c.length;i++){  
                          b[i]   =   getMin(c[i],a);  
                          for(int   j=0;j<a.length;j++){  
                                  a[j]   -=   c[i][j]*b[i];  
                          }  
                  }  
                  return   b;  
          }  
           
          public   static   int   getMin(int[]   a,int[]   b){  
                  int   tmp=-1;  
                  for(int   i=0;i<b.length;i++){  
                          if(a[i]!=0){  
                                  if(tmp==-1){  
                                          tmp   =   (b[i]-b[i]%a[i])/a[i];  
                                  }else{  
                                          tmp   =   min((b[i]-b[i]%a[i])/a[i],tmp);  
                                  }  
                          }  
                  }  
                  return   (tmp==-1)?0:tmp;  
          }  
  }  
  Top

15 楼windywoman（风过忘忧）回复于 2005-05-13 22:40:27 得分 0

优化了一下，速度提高5－6倍，不过时间还是随原材料的长度和最小钢管的长度的比值成指数增长。  
   
  import   java.io.BufferedInputStream;  
  import   java.io.OutputStreamWriter;  
  import   java.io.DataInputStream;  
  import   java.io.BufferedWriter;  
  import   java.io.FileInputStream;  
  import   java.io.FileNotFoundException;  
  import   java.io.FileOutputStream;  
  import   java.io.IOException;  
  import   java.util.Vector;  
   
  public   class   Assign   {  
  public   static   long   times;  
          public   static   void   main(String[]   args)   {  
  long   st   =   System.currentTimeMillis();  
  times   =   0;  
                  DataInputStream   in=null;  
                  BufferedWriter   out=null;  
                  try{  
                          in   =   new   DataInputStream(new   BufferedInputStream(new   FileInputStream("input.txt")));  
  out   =   new   BufferedWriter(new   OutputStreamWriter(new   FileOutputStream("output.txt"),"gb2312"));  
                          int   aimlen   =   Integer.parseInt(in.readLine());  
                          String[]   s   =   in.readLine().split("   ");  
                          String[]   s2   =   in.readLine().split("   ");  
  in.close();  
  in   =   null;  
                          Vector   ways   =   new   Vector();  
                          int[]   spit   =   new   int[s.length];  
                          int[]   nums   =   new   int[s2.length];  
  out.write("原料每根长度："+aimlen+"\n");  
                          for(int   i=0;i<s.length;i++){  
                                  spit[i]   =   Integer.parseInt(s[i]);  
                          }  
                          for(int   i=0;i<s2.length;i++){  
                                  nums[i]   =   Integer.parseInt(s2[i]);  
                                  out.write("需长度"+spit[i]+"的材料"+nums[i]+"根。"+"\n");  
                          }  
  int   g=0;  
  for(int   i=0;i<spit.length;i++){  
  g+=spit[i]*nums[i];  
  }  
  int   x   =   (g-g%aimlen)/aimlen;  
  if(g%aimlen!=0)  
  x++;  
  out.write("\n"+"期望根数为："+x);  
                          ways   =   getWays(spit,aimlen,spit.length,nums);  
                          int[][]   sortWay   =   sortWays(ways,spit,aimlen);  
  long   et   =   System.currentTimeMillis();  
  System.out.println("共得到方案"+sortWay.length+"种，耗时："+(et-st)+"毫秒，计算次数："+times);  
                          int[]   results   =   getResult(sortWay,nums);  
  int   flag=0;  
  for(int   i=0;i<nums.length;i++){  
  if(nums[i]>0){  
  flag=1;  
  break;  
  }  
  }  
                          out.write("\n"+"实际所需根数为："+(getTotal(results)+((flag==1)?1:0)));  
                          out.write("\n分配方案为：");  
                          int   count   =   0;  
                          for(int   i=0;i<results.length;i++){  
                                  if(results[i]!=0){  
                                          count++;  
                                          out.write("\n第"+count+"种方案如下，共分配"+results[i]+"次;");  
                                          for(int   j=0;j<spit.length;j++){  
                                                  if(sortWay[i][j]!=0){  
                                                          out.write("长度为"+spit[j]+"的分配"+sortWay[i][j]+"次：");  
                                                  }  
                                          }  
                                  }  
                          }  
  if(flag==1){  
  count++;  
                                  out.write("\n第"+count+"种方案如下，共分配1次：");  
                                  for(int   j=0;j<spit.length;j++){  
                                          if(nums[j]!=0){  
                                                  out.write("长度为"+spit[j]+"的分配"+nums[j]+"次：");  
                                          }  
                                  }  
  }  
  out.write("\n验算：");  
  int   sum;  
  for(int   j=0;j<spit.length;j++){  
  out.write("\n共得到长度为"+spit[j]+"的根数：");  
  sum=0;  
  for(int   i=0;i<results.length;i++){  
  sum+=results[i]*sortWay[i][j];  
  }  
  sum+=nums[j];  
  out.write(sum+"。");  
  }  
  long   e   =   System.currentTimeMillis();  
  System.out.println("完成，用时："+(e-st)+"毫秒，计算次数："+times);  
  out.close();  
  out   =   null;  
                  }catch(FileNotFoundException   e){  
                          System.out.println("请写好输入文件");  
                          e.printStackTrace();  
                  }catch(IOException   e2){  
                          System.out.println("输入输出流错误");  
                          e2.printStackTrace();  
                  }finally{  
                          try{  
  if(in!=null){  
  in.close();  
  in=null;  
  }  
  if(out!=null){  
  out.close();  
  out=null;  
  }  
                          }catch(IOException   e3){  
                                  e3.printStackTrace();  
                          }  
                  }    
          }  
           
          public   static   int   getTotal(int[]   a){  
                  int   b=0;  
                  for(int   i=0;i<a.length;i++){  
                          b+=a[i];  
  times++;  
                  }  
                  return   b;  
          }  
           
          public   static   int   min(int   a,int   b){  
                  return   (a<b)?a:b;  
          }  
           
          public   static   Vector   getWays(int[]   a,int   b,int   n,int[]   e){  
                  Vector   c   =   new   Vector();  
                  Vector   d   =   null;  
                  int[]   tmp;  
                  if(n==1){  
                          //for(int   i=0;i<=min((b-b%a[a.length-1])/a[a.length-1],e[a.length-1]);i++){  
                          //         c.add(new   int[]{i,0,0});  
  c.add(new   int[]{min((b-b%a[a.length-1])/a[a.length-1],e[a.length-1]),0,0});  
  times++;  
                          //}  
                  }else{  
                          for(int   i=0;i<=min((b-b%a[a.length-n])/a[a.length-n],e[a.length-n]);i++){  
                                  d   =   getWays(a,b-a[a.length-n]*i,n-1,e);  
                                  for(int   j=0;j<d.size();j++){  
                                          tmp   =   new   int[((int[])d.get(j)).length+1];  
                                          tmp[0]   =   i;  
                                          for(int   k=1;k<tmp.length;k++){  
                                                  tmp[k]   =   ((int[])d.get(j))[k-1];  
  times++;  
                                          }  
                                          c.add(tmp);  
                                  }  
                                  d   =   null;  
                          }  
                  }  
                  return   c;  
          }  
           
          public   static   int[][]   sortWays(Vector   c,int[]   a   ,int   b){  
                  int[][]   d   =   new   int[c.size()][a.length+2];  
                  int   f,g;  
                  int[]   tmp   =   null;  
                  for(int   i=0;i<c.size();i++){  
                          g=0;  
                          tmp   =   (int[])c.get(i);  
  for(int   j=0;j<a.length;j++){  
  g+=tmp[j]*a[j];  
  times++;  
  }  
                          tmp[tmp.length-2]   =   b-g;  
  g=0;  
                          for(int   j=0;j<tmp.length-2;j++){  
                                  f   =   (b-b%a[j])/a[j];  
                                  g   +=   (b%a[j])*tmp[j]/f;    
  times++;  
                          }  
                          tmp[tmp.length-1]   =   g-tmp[tmp.length-2];  
                          d[i]=tmp;  
                  }  
                  for(int   i=0;i<d.length-1;i++){  
                          for(int   j=i+1;j<d.length;j++){  
                                  if(d[j][d[j].length-1]>d[i][d[i].length-1]){  
                                          tmp   =   d[i];  
                                          d[i]   =   d[j];  
                                          d[j]   =   tmp;  
  times++;  
                                  }  
                          }  
                  }  
                  return   d;  
          }  
           
          public   static   int[]   getResult(int[][]   c,int[]   a){  
                  int[]   b   =   new   int[c.length];  
                  for(int   i=0;i<c.length;i++){  
                          b[i]   =   getMin(c[i],a);  
                          for(int   j=0;j<a.length;j++){  
                                  a[j]   -=   c[i][j]*b[i];  
  times++;  
                          }  
                  }  
                  return   b;  
          }  
           
          public   static   int   getMin(int[]   a,int[]   b){  
                  int   tmp=-1;  
                  for(int   i=0;i<b.length;i++){  
                          if(a[i]!=0){  
  times++;  
                                  if(tmp==-1){  
                                          tmp   =   (b[i]-b[i]%a[i])/a[i];  
                                  }else{  
                                          tmp   =   min((b[i]-b[i]%a[i])/a[i],tmp);  
                                  }  
                          }  
                  }  
                  return   (tmp==-1)?0:tmp;  
          }  
  }  
  Top

16 楼zdf_zhang（杀倭少将）回复于 2005-05-16 09:33:53 得分 0

非常感谢！我先试试！想要分我可再开贴（因为级别限制，一次最多100）！！！Top

17 楼zdf_zhang（杀倭少将）回复于 2005-05-16 12:56:16 得分 0

谢谢，我测试通过了。算法写的非常好。  
  我的QQ：15650898  
  我想和windywoman(风过忘忧)通过QQ联系Top

18 楼windywoman（风过忘忧）回复于 2005-05-16 13:34:30 得分 0

无法跟你QQ联系啊，QQ被禁了：（  
  这两天又优化了一下……现在用java   Assign   1000   300   0来计算原材料长度1000，300种分割规格，规格长度和各长度所需数量随机的最优分割方案，可以在10秒以内得到答案……  
  而且最后一个参数0是精度控制参数，设成0得到的是最优解，但是根据分割规格的种类成指数上升。如果设大一点，时间可以控制到O(n*n)--n为分割规格种类，应该比贪婪法要快，因为贪婪法的时间大概是O(m*n)--m为最后所需的原材料数量，n为最后所需的分割数量总和，不过跟贪婪法一样不是最优解，具体是不是比贪婪法得到的解要好，没验算过。  
   
  import   java.io.OutputStreamWriter;  
  import   java.io.BufferedWriter;  
  import   java.io.FileOutputStream;  
  import   java.io.IOException;  
  import   java.util.Vector;  
   
  public   class   Assign   {  
  public   static   long   times;  
  public   static   int   m;  
  public   static   int   c;  
  public   static   int   aimlen;  
   
          public   static   void   main(String[]   args)   {  
  long   st   =   System.currentTimeMillis();  
  double[]   power;  
  Vector   results   =   new   Vector();  
  int[]   way;  
  Vector   ways   =   new   Vector();  
  times   =   0;  
  int   min;  
  Integer   tmpr;  
  int[]   tmp;  
                  BufferedWriter   out=null;  
                  try{  
  out   =   new   BufferedWriter(new   OutputStreamWriter(new   FileOutputStream("output.txt"),"gb2312"));  
                          aimlen   =   Integer.parseInt(args[0]);  
  m   =   Integer.parseInt(args[1]);  
  c   =   Integer.parseInt(args[2]);  
                          int[]   spit   =   new   int[m];  
                          int[]   nums   =   new   int[m];  
  for(int   i=0;i<m;i++){  
  spit[i]=50+(int)(Math.round(Math.random()*500));  
  nums[i]=(int)(Math.round(Math.random()*200));  
  }  
  out.write("原料每根长度："+aimlen+"\n");  
                          for(int   i=0;i<m;i++){  
                                  out.write("需长度"+spit[i]+"的材料"+nums[i]+"根。"+"\n");  
                          }  
  int   g=0;  
  for(int   i=0;i<m;i++){  
  g+=spit[i]*nums[i];  
  }  
  int   x   =   (g-g%aimlen)/aimlen;  
  if(g%aimlen!=0)  
  x++;  
  out.write("\n"+"期望根数为："+x);  
  power   =   getPower(spit,aimlen);  
                          sortByPower(spit,power,nums);  
  int   count=0;  
  while(getSum(nums,spit)>aimlen){  
  way   =   getMaxPowerWay(power,spit,aimlen,nums);  
  count++;  
  System.out.println("count="+count);  
  min   =   getMin(nums,way);  
  for(int   j=0;j<m;j++){  
  nums[j]   -=   way[j]*min;  
  times++;  
  }  
  results.add(new   Integer(min));  
  ways.add(way);  
  }  
  if(getSum(nums,spit)!=0){  
  ways.add(nums);  
  results.add(new   Integer(1));  
  }  
                          out.write("\n"+"实际所需根数为："+getVectorSum(results));  
                          out.write("\n分配方案为：");  
                          for(int   i=0;i<results.size();i++){  
                                  if(((Integer)results.get(i)).intValue()!=0){  
                                          out.write("\n第"+(i+1)+"种方案如下，共分配"+((Integer)results.get(i)).intValue()+"次:");  
  tmp   =   (int[])ways.get(i);  
                                          for(int   j=0;j<m;j++){  
                                                  if(tmp[j]!=0){  
                                                          out.write("长度为"+spit[j]+"的分配"+tmp[j]+"次;");  
                                                  }  
                                          }  
  out.write("废料为"+getTrash(spit,tmp,aimlen)+";权值为"+getWayPower(power,spit,tmp,aimlen)+"。");  
                                  }  
                          }  
  out.write("\n验算：");  
  int   sum;  
  for(int   j=0;j<m;j++){  
  out.write("\n共得到长度为"+spit[j]+"的根数：");  
  sum=0;  
  for(int   i=0;i<results.size();i++){  
  tmp   =   (int[])ways.get(i);  
  tmpr   =   (Integer)results.get(i);  
  sum+=tmpr.intValue()*tmp[j];  
  }  
  out.write(sum+"。");  
  }  
  long   e   =   System.currentTimeMillis();  
  System.out.println("完成，用时："+(e-st)+"毫秒，计算次数："+times);  
  out.close();  
  out   =   null;  
                  }catch(IOException   e2){  
                          System.out.println("输入输出流错误");  
                          e2.printStackTrace();  
                  }finally{  
                          try{  
  if(out!=null){  
  out.close();  
  out=null;  
  }  
                          }catch(IOException   e3){  
                                  e3.printStackTrace();  
                          }  
                  }    
          }  
  }  
  Top

19 楼windywoman（风过忘忧）回复于 2005-05-16 13:35:31 得分 0

其中一部分函数如下……帖子太长了，摘出来了……  
   
          public   static   int   getVectorSum(Vector   results){  
                  int   tmp   =   0;  
                  for(int   i=0;i<results.size();i++){  
  times++;  
                          tmp+=((Integer)results.get(i)).intValue();  
                  }  
                  return   tmp;  
          }  
   
  public   static   double   getSum(double[]   a,int[]   b){  
  double   tmp=0;  
  for(int   i=0;i<m;i++){  
  tmp+=a[i]*b[i];  
  times++;  
  }  
  return   tmp;  
  }  
   
  public   static   int   getSum(int[]   a,int[]   b){  
  int   tmp=0;  
  for(int   i=0;i<m;i++){  
  tmp+=a[i]*b[i];  
  times++;  
  }  
  return   tmp;  
  }  
           
          public   static   int   getTotal(int[]   a){  
                  int   b=0;  
                  for(int   i=0;i<m;i++){  
                          b+=a[i];  
  times++;  
                  }  
                  return   b;  
          }  
           
          public   static   int   min(int   a,int   b){  
  times++;  
                  return   (a<b)?a:b;  
          }          
           
          public   static   int   getMin(int[]   nums,int[]   way){  
                  int   tmp=-1;  
                  for(int   i=0;i<m;i++){  
  times++;  
                          if(way[i]!=0){  
                                  if(tmp==-1){  
                                          tmp   =   (nums[i]-nums[i]%way[i])/way[i];  
                                  }else{  
                                          tmp   =   min((nums[i]-nums[i]%way[i])/way[i],tmp);  
                                  }  
                          }  
                  }  
                  return   (tmp==-1)?0:tmp;  
          }  
   
  public   static   double[]   getPower(int[]   spit,int   aimlen){  
  double[]   c=new   double[spit.length];  
  double   tmp;  
  for(int   i=0;i<m;i++){  
  c[i]=aimlen%spit[i];  
  tmp   =   (aimlen-c[i])/spit[i];  
  c[i]=c[i]/tmp;  
  c[i]=c[i]/spit[i];  
  times++;  
  }  
  return   c;  
  }  
   
  public   static   void   sortByPower(int[]   spit,double[]   power,int[]   nums){  
  double   tmp;  
  int   tmp1;  
  for(int   i=0;i<m-1;i++){  
                          for(int   j=i+1;j<m;j++){  
                                  if(power[j]>power[i]){  
                                          tmp   =   power[i];  
                                          power[i]   =   power[j];  
                                          power[j]   =   tmp;  
  tmp1   =   spit[i];  
  spit[i]   =   spit[j];  
  spit[j]   =   tmp1;  
  tmp1   =   nums[i];  
  nums[i]   =   nums[j];  
  nums[j]   =   tmp1;  
  times++;  
                                  }  
                          }  
                  }  
  }  
   
  public   static   int   getTrash(int[]   spit,int[]   tmpres,int   aimlen){  
  return   aimlen-getSum(spit,tmpres);  
  }  
   
  public   static   void   getWay(double[]   power,int[]   spit,int[]   nums,int   aimlen,int[]   tmpres,int   n){  
  int   tmp=aimlen;  
  for(int   i=0;i<n;i++){  
  tmp-=tmpres[i]*spit[i];  
  times++;  
  }  
  for(int   i=n;i<m;i++){  
  tmpres[i]   =   min((tmp-tmp%spit[i])/spit[i],nums[i]);  
  tmp-=tmpres[i]*spit[i];  
  times++;  
  }  
  }  
   
  public   static   double   getWayPower(double[]   power,int[]   spit,int[]   tmpres,int   aimlen){  
  double[]   tmp=new   double[m];  
  for(int   i=0;i<m;i++){  
  tmp[i]=power[i]*spit[i];  
  times++;  
  }  
  return   getSum(tmp,tmpres)-getTrash(spit,tmpres,aimlen);  
  }  
   
  public   static   int   getPrev(int[]   nums,int   n){  
  for(int   i=n-1;i>=0;i--){  
  times++;  
  if(nums[i]>0)return   i;  
  }  
  return   -1;  
  }  
   
  public   static   int   getNext(int[]   tmpres,int   n,int   endn){  
  if(n==endn)   return   -1;  
  for(int   i=n+1;i<=endn;i++){  
  times++;  
  if(tmpres[i]>0){  
          return   i;  
  }  
  }  
  return   -1;  
  }  
   
  public   static   int[]   getMaxPowerWay(double[]   power,int[]   spit,int   aimlen,int[]   nums){  
  int   tmp=aimlen;  
  int   trash=-1;  
  double   max=0-aimlen;  
  int   n=0;  
  int   tmpn;  
  int   endn=getPrev(nums,nums.length);  
  int[]   tmpres=new   int[power.length];  
  double   tmpmax;  
  int[]   res=new   int[power.length];  
  while(trash==-1||trash>c){  
  getWay(power,spit,nums,aimlen,tmpres,n);  
  trash   =   getTrash(spit,tmpres,aimlen);  
  tmpmax   =   getWayPower(power,spit,tmpres,aimlen);  
  if(tmpmax>max){  
  max=tmpmax;  
  for(int   i=0;i<res.length;i++){  
  res[i]=tmpres[i];  
  times++;  
  }  
  }  
  if(getNext(tmpres,n,endn)==-1){  
  n=getPrev(tmpres,endn);  
  if(n==-1)  
  break;  
  tmpres[n]--;  
  n   =   getNext(nums,n,endn);  
  }else{  
  n   =   getNext(tmpres,n,endn);  
  tmpres[n]--;  
  n   =   getNext(nums,n,endn);  
  }  
  while(n==-1){  
  times++;  
  n=getPrev(tmpres,endn);  
  if(n==-1)  
  break;  
  tmpres[n]--;  
  n   =   getNext(nums,n,endn);  
  }  
  if(n==-1)  
  break;  
  }  
  tmpmax   =   getWayPower(power,spit,tmpres,aimlen);  
  if(tmpmax>max){  
  max=tmpmax;  
  for(int   i=0;i<res.length;i++){  
  res[i]=tmpres[i];  
  times++;  
  }  
  }  
  return   res;  
  }  
  Top

20 楼windywoman（风过忘忧）回复于 2005-05-16 15:46:40 得分 0

不知道为什么，算到最后的几个数的时候速度特别慢……按我之前的想法应该越到后边越快的……不知道是不是什么地方写错了，我怎么看也看不出来哪儿的毛病……请高手帮我看看这个程序，到底哪儿的问题……Top

21 楼do_same_thing（我……我是马甲）回复于 2005-05-16 17:11:52 得分 0

markTop

22 楼windywoman（风过忘忧）回复于 2005-05-16 17:16:37 得分 0

&Otilde;&Ograve;&sup3;&ouml;&Agrave;&acute;&Aacute;&Euml;&pound;&not;&Ocirc;&shy;&Agrave;&acute;&Icirc;&Ograve;&cedil;&atilde;&acute;í&Aacute;&Euml;&pound;&not;×&icirc;&ordm;ó&Otilde;&acirc;&cedil;&ouml;&sup3;&Igrave;&ETH;ò&Atilde;&raquo;&Auml;&Uuml;&Iuml;ó&Icirc;&Ograve;&Iuml;&euml;&Iuml;ó&micro;&Auml;&Auml;&Ccedil;&Atilde;&acute;&iquest;ì&micro;&Auml;&Egrave;&yen;&Ccedil;ó×&icirc;&Oacute;&Aring;&frac12;&acirc;&pound;&not;java   Assign   1000   50   0&frac34;&Iacute;&Oacute;&Atilde;&Aacute;&Euml;&frac12;&laquo;&frac12;ü&Ograve;&raquo;·&Ouml;&Ouml;&Oacute;&iexcl;&pound;&sup2;&raquo;&sup1;&yacute;&sup1;&Agrave;&frac14;&AElig;±&Egrave;&Ouml;&reg;&Ccedil;°&micro;&Auml;&sup3;&Igrave;&ETH;ò&raquo;&sup1;&Ecirc;&Ccedil;&Ograve;&ordf;&iquest;ì&Ograve;&raquo;&micro;&atilde;&iexcl;&shy;&iexcl;&shy;&Aacute;í&Iacute;&acirc;&pound;&not;&Ouml;&raquo;&Ccedil;ó&frac12;ü&Euml;&AElig;&frac12;&acirc;&micro;&Auml;&raquo;°&pound;&not;&raquo;&sup1;&Ecirc;&Ccedil;&iquest;&Eacute;&Ograve;&Ocirc;&acute;&iuml;&micro;&frac12;O(n*n)&micro;&Auml;&iexcl;&pound;  
  &Otilde;&yacute;&Egrave;·&micro;&Auml;getMaxPowerWay&ordm;&macr;&Ecirc;&yacute;&Egrave;&ccedil;&Iuml;&Acirc;&pound;&ordm;  
  public   static   int[]   getMaxPowerWay(double[]   power,int[]   spit,int   aimlen,int[]   nums){  
  int   tmp=aimlen;  
  int   trash=-1;  
  int   n=0;  
  int   tmpn;  
  int   endn=getPrev(nums,nums.length);  
  int[]   tmpres=new   int[power.length];  
  getWay(power,spit,nums,aimlen,tmpres,-1);  
  double   max=getWayPower(power,spit,tmpres,aimlen);  
  double   tmpmax;  
  int[]   res=new   int[power.length];  
  for(int   i=0;i<res.length;i++){  
  res[i]=tmpres[i];  
  times++;  
  }  
  trash   =   getTrash(spit,tmpres,aimlen);  
  while(trash>c){  
  n=getNext(tmpres,n,endn);  
  if(n==endn||n==-1){  
  n=getPrev(tmpres,endn);  
  if(n==-1)  
  break;  
  }  
  tmpres[n]--;  
  getWay(power,spit,nums,aimlen,tmpres,n);  
  tmpmax   =   getWayPower(power,spit,tmpres,aimlen);  
  if(tmpmax>max){  
  max=tmpmax;  
  trash   =   getTrash(spit,tmpres,aimlen);  
  for(int   i=0;i<res.length;i++){  
  res[i]=tmpres[i];  
  times++;  
  }  
  }  
  }  
  if(trash!=0){  
  tmpmax   =   getWayPower(power,spit,tmpres,aimlen);  
  if(tmpmax>max){  
  max=tmpmax;  
  for(int   i=0;i<res.length;i++){  
  res[i]=tmpres[i];  
  times++;  
  }  
  }  
  }  
  return   res;  
  }Top

23 楼windywoman（风过忘忧）回复于 2005-05-16 17:19:37 得分 0

找出来了，原来我搞错了，最后这个程序没能象我想象的那么快的去求最优解，java   Assign   1000   50   0就用了将近一分钟。不过估计比之前的程序还是要快一点……另外，只求近似解的话，还是可以达到O(n*n)的。  
  正确的getMaxPowerWay函数如下：  
  public   static   int[]   getMaxPowerWay(double[]   power,int[]   spit,int   aimlen,int[]   nums){  
  int   tmp=aimlen;  
  int   trash=-1;  
  int   n=0;  
  int   tmpn;  
  int   endn=getPrev(nums,nums.length);  
  int[]   tmpres=new   int[power.length];  
  getWay(power,spit,nums,aimlen,tmpres,-1);  
  double   max=getWayPower(power,spit,tmpres,aimlen);  
  double   tmpmax;  
  int[]   res=new   int[power.length];  
  for(int   i=0;i<res.length;i++){  
  res[i]=tmpres[i];  
  times++;  
  }  
  trash   =   getTrash(spit,tmpres,aimlen);  
  while(trash>c){  
  n=getNext(tmpres,n,endn);  
  if(n==endn||n==-1){  
  n=getPrev(tmpres,endn);  
  if(n==-1)  
  break;  
  }  
  tmpres[n]--;  
  getWay(power,spit,nums,aimlen,tmpres,n);  
  tmpmax   =   getWayPower(power,spit,tmpres,aimlen);  
  if(tmpmax>max){  
  max=tmpmax;  
  trash   =   getTrash(spit,tmpres,aimlen);  
  for(int   i=0;i<res.length;i++){  
  res[i]=tmpres[i];  
  times++;  
  }  
  }  
  }  
  if(trash!=0){  
  tmpmax   =   getWayPower(power,spit,tmpres,aimlen);  
  if(tmpmax>max){  
  max=tmpmax;  
  for(int   i=0;i<res.length;i++){  
  res[i]=tmpres[i];  
  times++;  
  }  
  }  
  }  
  return   res;  
  }Top

24 楼windywoman（风过忘忧）回复于 2005-05-16 18:56:49 得分 0

还是有个地方有问题…getMaxPowerWay函数第三版：  
  public   static   int[]   getMaxPowerWay(double[]   power,int[]   spit,int   aimlen,int[]   nums){  
  int   tmp=aimlen;  
  int   trash=-1;  
  int   tmpn;  
  int   endn=getPrev(nums,nums.length);  
  int[]   tmpres=new   int[power.length];  
  getWay(power,spit,nums,aimlen,tmpres,-1);  
  int   n=getNext(tmpres,-1,endn);  
  double   max=getWayPower(power,spit,tmpres,aimlen);  
  double   tmpmax;  
  int[]   res=new   int[power.length];  
  for(int   i=0;i<res.length;i++){  
  res[i]=tmpres[i];  
  times++;  
  }  
  trash   =   getTrash(spit,tmpres,aimlen);  
  while(trash>c){  
  n=getNext(tmpres,n,endn);  
  if(n==endn||n==-1){  
  n=getPrev(tmpres,endn);  
  if(n==-1)  
  break;  
  }  
  tmpres[n]--;  
  getWay(power,spit,nums,aimlen,tmpres,n);  
  tmpmax   =   getWayPower(power,spit,tmpres,aimlen);  
  if(tmpmax>max){  
  max=tmpmax;  
  trash   =   getTrash(spit,tmpres,aimlen);  
  for(int   i=0;i<res.length;i++){  
  res[i]=tmpres[i];  
  times++;  
  }  
  }  
  }  
  if(trash!=0){  
  tmpmax   =   getWayPower(power,spit,tmpres,aimlen);  
  if(tmpmax>max){  
  max=tmpmax;  
  for(int   i=0;i<res.length;i++){  
  res[i]=tmpres[i];  
  times++;  
  }  
  }  
  }  
  return   res;  
  }  
   
  算了一下，java   Assign   1000   50   0好的情况下10几秒，坏的话10几分钟……不过要是前两天那个程序，根本就无法算到50种，因为方案的数目已经超过Vector的存储范围。现在的程序至少在空间要求上要少很多了：）Top

25 楼do_same_thing（我……我是马甲）回复于 2005-05-16 20:47:50 得分 0

mark   again.Top

26 楼windywoman（风过忘忧）回复于 2005-05-16 20:49:30 得分 0

事实证明，最佳方案法远优于贪婪法。  
  以下为java   Assign   1000   5   20计算所得贪婪法和最佳方案法的输出：  
  原料每根长度：1000  
  需长度179的材料128根。  
  需长度123的材料64根。  
  需长度185的材料55根。  
  需长度428的材料16根。  
  需长度69的材料186根。  
   
  期望根数为：61  
   
   
  以下为贪婪法所得结果：  
  贪婪法完成，用时：20毫秒，计算次数：43279  
  实际所需根数为：66  
  分配方案为：  
  第1根原材料如下方案分割：428;428;123;废料为21。  
  第2根原材料如下方案分割：428;428;123;废料为21。  
  第3根原材料如下方案分割：428;428;123;废料为21。  
  第4根原材料如下方案分割：428;428;123;废料为21。  
  第5根原材料如下方案分割：428;428;123;废料为21。  
  第6根原材料如下方案分割：428;428;123;废料为21。  
  第7根原材料如下方案分割：428;428;123;废料为21。  
  第8根原材料如下方案分割：428;428;123;废料为21。  
  第9根原材料如下方案分割：123;123;123;123;123;123;123;123;废料为16。  
  第10根原材料如下方案分割：123;123;123;123;123;123;123;123;废料为16。  
  第11根原材料如下方案分割：123;123;123;123;123;123;123;123;废料为16。  
  第12根原材料如下方案分割：123;123;123;123;123;123;123;123;废料为16。  
  第13根原材料如下方案分割：123;123;123;123;123;123;123;123;废料为16。  
  第14根原材料如下方案分割：123;123;123;123;123;123;123;123;废料为16。  
  第15根原材料如下方案分割：123;123;123;123;123;123;123;123;废料为16。  
  第16根原材料如下方案分割：185;185;185;185;185;69;废料为6。  
  第17根原材料如下方案分割：185;185;185;185;185;69;废料为6。  
  第18根原材料如下方案分割：185;185;185;185;185;69;废料为6。  
  第19根原材料如下方案分割：185;185;185;185;185;69;废料为6。  
  第20根原材料如下方案分割：185;185;185;185;185;69;废料为6。  
  第21根原材料如下方案分割：185;185;185;185;185;69;废料为6。  
  第22根原材料如下方案分割：185;185;185;185;185;69;废料为6。  
  第23根原材料如下方案分割：185;185;185;185;185;69;废料为6。  
  第24根原材料如下方案分割：185;185;185;185;185;69;废料为6。  
  第25根原材料如下方案分割：185;185;185;185;185;69;废料为6。  
  第26根原材料如下方案分割：185;185;185;185;185;69;废料为6。  
  第27根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第28根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第29根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第30根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第31根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第32根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第33根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第34根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第35根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第36根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第37根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第38根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第39根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第40根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第41根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第42根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第43根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第44根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第45根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第46根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第47根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第48根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第49根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第50根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第51根原材料如下方案分割：179;179;179;179;179;69;废料为36。  
  第52根原材料如下方案分割：179;179;179;123;123;123;69;废料为25。  
  第53根原材料如下方案分割：123;123;123;123;123;69;69;69;69;69;废料为40。  
  第54根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;69;废料为34。  
  第55根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;69;废料为34。  
  第56根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;69;废料为34。  
  第57根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;69;废料为34。  
  第58根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;69;废料为34。  
  第59根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;69;废料为34。  
  第60根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;69;废料为34。  
  第61根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;69;废料为34。  
  第62根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;69;废料为34。  
  第63根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;69;废料为34。  
  第64根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;69;废料为34。  
  第65根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;69;废料为34。  
  第66根原材料如下方案分割：69;69;69;69;69;69;69;69;69;69;69;69;69;废料为103。  
   
   
  以下为最佳方案法所得结果：  
  贪婪法完成，用时：0毫秒，计算次数：711  
  实际所需根数为：62  
  分配方案为：  
  第1种方案如下，共分配8次:长度为428的分配2次;长度为69的分配2次;废料为6;权值为142.85714285714286。  
  第2种方案如下，共分配32次:长度为179的分配4次;长度为69的分配4次;废料为8;权值为85.71428571428571。  
  第3种方案如下，共分配11次:长度为185的分配5次;长度为69的分配1次;废料为6;权值为71.42857142857143。  
  第4种方案如下，共分配3次:长度为69的分配9次;长度为123的分配3次;废料为10;权值为17.857142857142854。  
  第5种方案如下，共分配2次:长度为69的分配2次;长度为123的分配7次;废料为1;权值为17.857142857142858。  
  第6种方案如下，共分配5次:长度为123的分配8次;废料为16;权值为0.0。  
  第7种方案如下，共分配1次:长度为123的分配1次;废料为877;权值为-875.0。  
  验算：  
  共得到长度为428的根数：16。  
  共得到长度为179的根数：128。  
  共得到长度为185的根数：55。  
  共得到长度为69的根数：186。  
  共得到长度为123的根数：64。  
   
   
   
   
  －－－－另外，java   Assign   1000   1000   100可以在2秒内完成，而且结果远优于贪婪法……而贪婪法估计真得用超级计算机才可以搞定了……Top

27 楼zdf_zhang（杀倭少将）回复于 2005-05-17 09:54:53 得分 0

我的一个好朋友用贪婪法给我写了一个程序。我和   windywoman(风过忘忧)   的程序比较了一下，的确比贪婪法要好的多。  
  通过我测试，我目前没有发现比《型材切割助手3.02》算得更好的了。不知道他是怎么算的？  
  您可以把Java源程序的邮箱发到我邮箱里吗？  
  jwjkr@163.com  
  非常感谢！  
  这段代码能改写成Dephi的代码吗？我不知道Vector类型在Dephi中如何表达？Top

28 楼zdf_zhang（杀倭少将）回复于 2005-05-17 10:06:30 得分 0

用《。。。助手》算上面的例子是六种方案，需要61根，原材料利用率达99.41%  
  切割方案如下：  
  1、69*4+179*3+185   共42次  
  2、123+185*2+69+428   共6次  
  3、69*2+123*7   共6次  
  4、428*2+123   共5次  
  5、123*5+185+179   共1次  
  6、123*6+179   共1次Top

29 楼zdf_zhang（杀倭少将）回复于 2005-05-17 10:09:51 得分 0

用《。。。助手》算上面的例子是六种方案，需要61根，原材料利用率达99.41%  
  切割方案如下：  
  1、69*4+179*3+185   共42次   余料2  
  2、123+185*2+69+428   共6次   余料10  
  3、69*2+123*7   共6次   余料1  
  4、428*2+123   共5次   余料21  
  5、123*5+185+179   共1次   余料21  
  6、123*6+179   共1次   余料83  
  请问能将上述的Java源代码改写成BCB的吗？Top

30 楼nlstone（天外流星）回复于 2005-05-17 13:31:53 得分 0

markTop

31 楼windywoman（风过忘忧）回复于 2005-05-17 14:31:26 得分 0

居然还不是最优解……郁闷！不过我不会delphi,没法帮你了：（Top

32 楼zdf_zhang（杀倭少将）回复于 2005-05-17 16:03:34 得分 0

您可以把Java源程序发到我邮箱里吗？  
  jwjkr@163.com  
  非常感谢！Top

33 楼windywoman（风过忘忧）回复于 2005-05-17 17:54:14 得分 0

修改过了，原来是因为我只判断了权值，没去判断相同权值情况下废料最少为优。  
  修改过后运行结果跟那个助手给出的结果一样。  
  程序我会发给你邮箱里面。请接收。Top

34 楼zdf_zhang（杀倭少将）回复于 2005-05-17 18:27:54 得分 0

谢谢，可怎么算成63根了，还是上个例子Top

35 楼zdf_zhang（杀倭少将）回复于 2005-05-17 18:36:46 得分 0

你算一下这个：  
  aimlen=6000;  
  spit   =   new   int[]{1500,1350,600,700,800,500,3000,1800,1000,900,3300,5700,2100,3400,1200,1700,4000,4400,3100};  
  nums   =   new   int[]{804,1240,176,76,88,72,152,88,92,178,80,88,162,88,22,98,8,28,12};  
  助手算出来是972根  
  你算出来是1000根呀。Top

36 楼windywoman（风过忘忧）回复于 2005-05-17 22:06:45 得分 0

不对啊，怎么在你机器上跟我得数据不一样？？  
  我那个例子算出来就是61根啊。  
  不过后来这个例子，我这边算出来是993根……真的可以达到972根么……那我这个就不是最优了。Top

37 楼zdf_zhang（杀倭少将）回复于 2005-05-18 09:55:28 得分 0

我把助手给你发过去，不信你试试！Top

38 楼zdf_zhang（杀倭少将）回复于 2005-05-18 10:03:00 得分 0

是不是你给我发源代码时发错了Top

39 楼windywoman（风过忘忧）回复于 2005-05-18 14:23:20 得分 0

不可能啊……我现在还在修改中，现在大概可以搞出977根左右……比人家用迭代法就是要差一点……Top

40 楼zdf_zhang（杀倭少将）回复于 2005-05-18 16:25:05 得分 0

能搞出977根也很不错了！佩服……Top

41 楼handwolf（青松崖）回复于 2005-05-18 17:17:11 得分 0

markTop

42 楼ZDL627（天）回复于 2005-05-19 21:47:10 得分 0

markTop

43 楼anggogo（angGoGo）回复于 2005-05-27 22:47:53 得分 0

唉,这个是最简单的   DP   1-d   resource   allocation   的问题Top

44 楼zdf_zhang（杀倭少将）回复于 2005-06-03 10:31:44 得分 0

anggogo(angGoGo):你会吗？为什么不解答？Top

45 楼yangfasheng（悟法:前面是绝路,希望在拐角）回复于 2005-06-03 19:15:07 得分 0

NBTop

46 楼Kvci（看了不笑就没小JJ同时又比较长的昵称__——————————————————————————————）回复于 2005-06-13 14:59:13 得分 0

&#1&#2&#3&#4&#5&#6&#7<>&#8&#9&#10&#1$&#11+2  
  Top

相关问题

• 模式
• 原材料
• tmpres
• aimlen
• tmpmax
• spit
• cm
• endn
• 权值
• 切割

• 帖主：zdf_zhang
• miyimei
• miyimei
• windywoman

• CSDN Blog
• 技术文档
• 代码下载
• 第二书店
• 读书频道