greedyjob.java

《算法设计与分析》王晓东编著

public class Greedyjob {
	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 d[]=new int[]{0,4,2,4,3,1,4,6};
		int w[]=new int[]{0,70,60,50,40,30,20,10};
		int job[]=new int[d.length];
		
		System.out.println(greedyJob(d,w,job));
	}
}