fac5_3.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 160 页，例
//批作业调度问题的回溯解法
//本程序输入时注意m 数组需增加一个{0,0}元素，最优值初值选bestf=32767
 
   class FlowShop 
   { 
     static int n,       //作业数
                f1,      //  机器1完成处理时间
                f,       //  完成时间和
                bestf;   //  当前最优值
     static int [][]m;   //  各作业所需的处理时间
     static int []x;     //  当前作业调度
     static int []bestx; //  当前最优作业调度
     static int []f2;    //  机器2完成处理时间

    public static void backtrack(int i)
     {
   //   System.out.println("**i***  "+i);
      if(i>n){
      for(int j=1;j<=n;j++)
       bestx[j]=x[j];
      bestf=f;
             }
      else
        for(int j=i;j<=n;j++){    
        f1+=m[x[j]][0];
        f2[i]=((f2[i-1]>f1)? f2[i-1]:f1)+m[x[j]][1];
        f+=f2[i];
   //   System.out.println("**f  "+f+"  f1="+f1+"  f2[i]="+f2[i]);
        if(f<bestf){
        swap(i,j);
        backtrack(i+1);
        swap(i,j);
                   }
        f1-=m[x[j]][0];
        f-=f2[i];

        }
     }
 
  static void swap(int i,int j)
  {
   int temp;   
   temp=x[i];
   x[i]=x[j];
   x[j]=temp;
  }
 }
      public class Fac5_3{
      public static void main(String args[])
  {
   
     int [][]m1={{0,0},{2,1},{3,1},{2,3}};
     int n1=m1.length;
     int x1[]=new int[n1+1];
     int ff2[]=new int[n1+1];
     int bestx1[]=new int[n1+1];
     FlowShop pzd=new FlowShop();
     pzd.m=m1;
     for(int i=0;i<=n1;i++){
     x1[i]=i;
     ff2[i]=0;
     }
     pzd.x=x1;
     pzd.n=n1-1;
     pzd.bestf=32767;
     pzd.f=0;
     pzd.f1=0;
     pzd.f2=ff2;
     pzd.bestx=bestx1;
     pzd.backtrack(1);
    for(int i=1;i<n1;i++)
    System.out.print(pzd.bestx[i]+"  ");
    System.out.println();
    System.out.println(" 最优值  "+pzd.bestf);
  }
}