fac4_1.java

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

//
//本程序取自王晓东编著“算法分析与设计”第 108 页，例
//活动安排问题贪心解法
  class task{
     int n;
     int[] s;
     int f[];
     public task(int n1,int[] s1,int f1[])
     { n=n1;
       s=s1;
       f=f1;
     }
  }
 public  class Fac4_1{
    public static void sort(int[]x,int[] y)
  {
    int m=x.length-1;
    for(int i=0;i<m;i++)
     for(int j=i;j<=m;j++)
       if(y[i]>y[j]){
        swap(y,i,j);
        swap(x,i,j);
       }
  }
   public static void swap(int[] a,int m,int n)
      {
       int temp;
       temp=a[m];
       a[m]=a[n];
       a[n]=temp;
      }
   public static int greedySelector(int[] s,int[] f,boolean a[])
   {
      int n=s.length-1;
      a[0]=true;
      int j=1;
      int count=1;
      for (int i = 1; i <= n; i++){
        if(s[i]>=f[j]){
           a[i]=true;
             j=i;
           count++;
        }
        else a[i]=false;
      }
      return count;
   }
 public static void main(String argc[])
   {
    int tws=11;
    int ts[]={1,3,0,8,6,5,3,8,5,2,12};
    int tf[]={4,5,6,12,10,9,8,11,7,13,14};
       // System.out.println(" 输出原始数据 ");
       //for(int i=0;i<tws;i++)
       // System.out.print("  "+ts[i]);
       //System.out.println();
       // for(int i=0;i<tws;i++)
       //  System.out.print("  "+tf[i]);
       //  System.out.println();
    sort(ts,tf);
       //System.out.println(" 输出排序后数据 ");
       //for(int i=0;i<tws;i++)
       // System.out.print("  "+ts[i]);
       // System.out.println();
       //for(int i=0;i<tws;i++)
       // System.out.print("  "+tf[i]);
       // System.out.println();
    task aa=new task(tws,ts,tf);
    boolean w[]=new boolean[tws];
    greedySelector(aa.s,aa.f,w);
    System.out.println(" 输出最大活动依任务好安排顺序 ");
    for(int i=0;i<tws;i++){
     if(w[i])
      System.out.print("  "+(i+1));
       }
     System.out.println();
    }
 }