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

D=(2,3,1,3,4,5,2);P(15,12,11,10,8,5,4);

首先将作业按p1≥p2 ≥ … ≥ pn排序, 将作业1存入解数组J中, 然后按照如下步骤逐一处理作业2到作业n；假设已处理完了i-1个作业, 其中有k个作业可构成可行解，已存入J(1),J(2)…J(k)中, 且D(J(1))<=D(J(2)) <=…<=D(J(k))

§现在处理作业i, 判断Jυ{i}是否可行, 就是看是否能为其中作业都找到适当插入位置r, 使作业i插入后有D(J(r))≥r; 1≤r≤k+1.  过程如下：

将D(J(k)), D(J(k-1)),…依次与D(i)比较，若D(J(l))>D(i)且D(J(l))≠l,l≤k，则作业J(l)可以向后延迟一个单位时间来处理,作业i可以在J(l)之前处理。

package greedy;

public class JS {
    int n=7;
    int [] D={0,2,3,1,3,4,5,2};//下标从1开始
    float[] P={0,15,12,11,10,8,5,4};//先对P进行非增排序
    int[] J=new int[n+1]; 
    int k;
    JS(){
        k=js(D,J,n,k);
        System.out.println("可调度作业数目:"+k);
        double sum=0;
        System.out.print("作业调度次序："); 
        for(int i=1;i<=k;i++){
            System.out.print("->"+J[i]);
            sum+=P[J[i]];
        }
        System.out.println();
        System.out.println("总收益Sum="+sum);
    }
    public int js(int[] D,int[] J,int n,int k){
        int i,r;
        k=1;
        J[1]=1;//把第一个作业加入
        for(i=2;i<n;i++){
            r=k;
            while(D[J[r]]>D[i]&&D[J[r]]!=r){
                r--;
            }
            if(D[J[r]]<=D[i]&&D[i]>r){
                for(int l=k;l>r;l--){
                    J[l+1]=J[l];
                }
                J[r+1]=i;
                k++;
            }
        }
        return k;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        new JS();
    }

}

测试结果：