fac4_8.java

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

//本程序取自王晓东编著“算法分析与设计”第 139 页，例
//任务时间表问题的贪心解法
  public class Fac4_8{
     public static int greedyjob(int[] d,int[] w,int[] job)
   {
     int n=d.length-1;  
     d[0]=0;job[0]=0;
     int k=1;
     job[1]=1;
     for(int i=2;i<=n;i++){
       int r=k;
       while((d[job[r]]>d[i]) && (d[job[r]]!=r)) r--;
       if((d[job[r]]<=d[i]) && (d[i]>r)){
      for(int m=k;m>r;m--)
       job[m+1]=job[m];
      job[r+1]=i;
      k++;
         }
       } 
 
     for(int i=1;i<=k;i++)
       w[job[i]]=0;
     int sum=0;
     for(int i=1;i<=n;i++)
       if(w[i]>0){
         job[++k]=i;
         sum+=w[i];
        }
     return sum;
   }

      public static void main(String args[])
  {
    int v1[]={0,4,2,4,3,1,4,6};
    int w1[]={0,70,60,50,40,30,20,10}; 
    int n=v1.length-1; 
    int[] u1=new int[n+1]; 
    System.out.println("最小误时罚款 "+greedyjob(v1,w1,u1));
    System.out.println("最优时间表  ");
    for(int i=1;i<=n;i++)
    System.out.print(u1[i]+"  ");
    System.out.println();
  }
}