带有限期和效益的单位时间的作业排序贪心算法

 1 package greedy;
 2 
 3 public class JS {
 4     int n=7;
 5     int [] D={0,2,3,1,3,4,5,2};//下标从1开始
 6     float[] P={0,15,12,11,10,8,5,4};//先对P进行非增排序
 7     int[] J=new int[n+1]; 
 8     int k;
 9     JS(){
10         k=js(D,J,n,k);
11         System.out.println("可调度作业数目:"+k);
12         double sum=0;
13         System.out.print("作业调度次序："); 
14         for(int i=1;i<=k;i++){
15             System.out.print("->"+J[i]);
16             sum+=P[J[i]];
17         }
18         System.out.println();
19         System.out.println("总收益Sum="+sum);
20     }
21     public int js(int[] D,int[] J,int n,int k){
22         int i,r;
23         k=1;
24         J[1]=1;//把第一个作业加入
25         for(i=2;i<n;i++){
26             r=k;
27             while(D[J[r]]>D[i]&&D[J[r]]!=r){
28                 r--;
29             }
30             if(D[J[r]]<=D[i]&&D[i]>r){
31                 for(int l=k;l>r;l--){
32                     J[l+1]=J[l];
33                 }
34                 J[r+1]=i;
35                 k++;
36             }
37         }
38         return k;
39     }
40     public static void main(String[] args) {
41         // TODO Auto-generated method stub
42         new JS();
43     }
44 
45 }