fac3_8.java

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

//本程序取自王晓东编著“算法分析与设计”第 90 页，例
//流水作业调度问题动态规划解法
public class Fac3_8{
 static class Elememt 
   {
    int key;
    int index;
    boolean job;
    private Elememt(int kk,int ii,boolean jj)
      {
       key=kk;
       index=ii;
       job=jj;
      }
   }
 
   public static int flowShop(int []a,int []b,int []c)
   {
     int n=a.length;
     Elememt []d=new Elememt[n];
     for(int i=0;i<n;i++){
       int key=a[i]>b[i]? b[i]:a[i];
       boolean job=a[i]<=b[i];
       d[i]=new Elememt(key,i,job);
     // System.out.println("d["+i+"] "+key+"  "+i+"  "+job);
       }
     mergeSort(d);
     int j=0,k=n-1;
     for(int i=0;i<n;i++){
       if(d[i].job)c[j++]=d[i].index;
       else c[k--]=d[i].index;
       }
     j=a[c[0]];
     k=j+b[c[0]];
     for(int i=1;i<n;i++){
       j+=a[c[i]];
       k=j<k? k+b[c[i]]:j+b[c[i]];
       }
   return k; 
  }
     public static void mergeSort(Elememt[] e)
   {
     int k=e.length-1;  
     Elememt a;
     for(int i=0;i<k;i++)
      for(int j=i+1;j<=k;j++)
       if(e[i].key<e[j].key){
        a=e[i];
        e[i]=e[j];
        e[j]=a;
       }
    }    

  public static void main(String args[])
  {
    int []x={2,3,2};
    int []y={1,1,3};
    int n=x.length;
    int []z=new int[n];
    System.out.println("完成作业所需最短时间 "+flowShop(x,y,z));
    System.out.println("作业编号自0开始，作业执行顺序为 ");
    for(int j=0;j<n;j++)   
    System.out.print(" "+z[j]);
    System.out.println();
  }
}