fac4_7.java

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

//本程序取自王晓东编著“算法分析与设计”第 130 页，例
//多机调度问题的贪心解法
 
   class MinHeap 
   {                        //Min-heap impmentation
    static MachineNode[] Heap;    //Pointer to the heap array
    static int size;             //Maximum size of the heap
    static int n;                //Number of elements now in heap
    public MinHeap(MachineNode[] h,int num,int max)//constructor
     { Heap=h;n=num;size=max;buildheap();}
    public int heapsize()//return current size of the heap
     {  return n;}
    public boolean isLeaf(int pos)//true if pos is a leaf position
     { return(pos>=n/2)&&(pos<n);} 

    public static void Assert_notFalse(boolean p,String q)
     {if(!p)System.out.println((String)q);}
   
  //return position for left child of pos
    public int leftchild(int pos)
     { Assert_notFalse(pos<n/2,"position has no left child");
       return 2*pos+1;
     }
  //return position for right child of pos
    public int rightchild(int pos)
     {Assert_notFalse(pos<(n-1)/2,"position has no right child");
     return 2*pos+2;
     }
    public int parent(int pos)//return position for parent
     {Assert_notFalse(pos>0,"position has no parent");
     return (pos-1)/2;
     }
    public void buildheap() //Heapify contents of Heap
     {  for(int i=n/2-1;i>=0;i--)siftdown(i);}

    public static void swap(MachineNode[] q,int i,int j)
     {
       MachineNode temp;
       temp=q[i];q[i]=q[j];q[j]=temp;}
//
    private void siftdown(int pos) //put element in its corrent place
     {Assert_notFalse((pos>=0)&&(pos<n),"illegal heap position ");
     while(! isLeaf(pos))
      {
       int j=leftchild(pos);
       if(j<(n-1) && (Heap[j].key()>Heap[j+1].key()))
         j++;// j is now index of child with smaller value
       if(Heap[pos].key()<=Heap[j].key()) return;// Done
       swap(Heap,pos,j);
       pos=j;//Move down 
      }
     }
    public void insert(MachineNode val) //Insert value into heap
     {
     System.out.println( "Heap[0].id="+Heap[0].id+" Heap[1].id="+Heap[1].id+" Heap[2].id="+Heap[2].id);    
     Assert_notFalse(n<=size,"Heap is full ");
     int curr=n++;
     Heap[curr]=val;      //start at end of heap
     
   //System.out.println( "Heap["+curr+"].id="+Heap[curr].id+" Heap["+curr+"].avail="+Heap[curr].key());    
   // System.out.println("heap ["+parent(curr)+"].id="+Heap[parent(curr)].id+" heap["+parent(curr)+"].avail="+Heap[parent(curr)].key());
         //Now sift up until curr's parent's key<curr's key
   //  System.out.println("curr="+curr+"  parent(curr)="+parent(curr)); 
     while((curr!=0) && (Heap[curr].key()<Heap[parent(curr)].key()))
       {            
         swap(Heap,curr,parent(curr));
         curr=parent(curr);
        
       }
      }
//
    public MachineNode removeMin()  //remove minimum value
      {
       Assert_notFalse(n>0,"Removing from empty heap ");
       swap(Heap,0,--n);//swap minimum with last value
       if(n!=0)     //Not on last intent
       siftdown(0); //Put new heap root val in corrent place 
       return Heap[n];
     } 
      public static void outminheap()
       {       
        for(int i=0;i<n;i++)
          System.out.println(" Heap["+i+"]"+".id="+Heap[i].id+" avail "+Heap[i].avail);
       }
     
 } // class MinHeap
 
  class jobNode implements Comparable
  {
    int id;
    int time;
     jobNode(int i,int tt)
       {
         id=i;
         time=tt;
       }
     public int compareTo(Object x)
       {
        int xt=((jobNode)x).time;
        if(time<xt)return -1;
        if(time==xt)return 0;
        return 1;
       }
  }
 class MachineNode implements Comparable
   { 
     static int id,avail;
     MachineNode(int i,int a)
     {
      id=i;
      avail=a;
     }
     public int compareTo(Object x)
     {
      int xa=((MachineNode)x).avail;
      if(avail<xa)return -1;
      if(avail==xa)return 0;
      return 1;
     }
      public static int key()
     {  return avail;}
   }
  public class Fac4_7{
     public static void mergeSort(jobNode[] e)
   {
     int k=e.length-1;  
     jobNode a;
     for(int i=0;i<k;i++)
      for(int j=i+1;j<=k;j++)
       if(e[i].time<e[j].time){
        a=e[i];
        e[i]=e[j];
        e[j]=a;
       }
    }     

   public static int greedy( int []a,int m)
   {
     int n1=a.length-1;
     int sum=0;
//如果作业数小于等于机器数为每台机器分配一个作业，其中最长的作业时间即为最小作业时间
     if(n1<=m){
     for(int i=0;i<n1;i++){if(sum<a[i])sum=a[i];}
      System.out.print("为每个作业分配一台机器。");
      return sum;
             }  
//如果作业数大于机器数先将作业按加工时间降序排序
      jobNode []d=new jobNode[n1+1];
     for(int i=0;i<=n1;i++)
      d[i]=new jobNode(i,a[i]);
      mergeSort(d); 
    //  System.out.println(" 排序后 ");
    // for(int i=0;i<=n1;i++)
    //  System.out.println("d["+i+"]  "+d[i].id+"  "+d[i].time);
      
//按机器数建立最小堆
      MachineNode c[]=new MachineNode[n1+1]; 
      for(int j=0;j<=n1;j++)
      {
       MachineNode x=new MachineNode(j,d[j].time); 
       c[j]=x;
      }
      MinHeap H=new MinHeap(c,0,m);
      for(int i=0;i<m;i++)
      {
        MachineNode x=new MachineNode(i,d[i].time);           
         H.insert(x); 
     }          
      H.outminheap();
     for(int i=m;i<=n1;i++){
       MachineNode x=(MachineNode)H.removeMin();
        System.out.println("将机器"+x.id+" 从 "+x.avail+" 到"
          +(x.avail+d[i].time)+" 的时间段分配给作业"+d[i].id);
        x.avail+=d[i].time; 
       if(sum<x.avail)sum=x.avail; 
         System.out.println("x.id="+x.id+" x.avail="+x.avail);  
        H.insert(x);     
        }       
        H.outminheap();
        return sum;      
   }           
 
      public static void main(String args[])
  {
    int v1[]={2,14,4,16,6,5,3};
    int c1=3;   
    System.out.println(" 最短完成时间 "+greedy(v1,c1));
  }
}