greedyaselectormain.java

贪心算法 使某些问题时间复杂度降为一维线性

/**
*An iterative greedy algorithm
*/

class GreedyASelector
{
	int n;
	int A[];

	public int[] greedyASelector(int[] s,int[] f)	//迭代贪心算法
	{				
		n=s.length;
		A[1]=1;
		int i=1;
		for(int m=2;m<s.length;m++)		//线性寻找am
		{
			if(s[m]>=f[i])
			{
				A[i+1]=m;
				i=m;
			}
		}
		return A;
	}
}

public class GreedyASelectorMain
{
	public static void main(String args[])
	{

		int s[]={0,1,3,0,5,3,5,6,8,8,2,12};		//活动开始时间的集合
		int f[]={0,4,5,6,7,8,9,10,11,12,13,14};		//活动结束时间的集合（已排序）
		int A[]=new int[s.length];			//A是用来存放最早结束活动的集合

		for(int i=0;i<s.length;i++)			//A初始化各项为0
		{
			A[i]=0;
		}

		GreedyASelector gas=new GreedyASelector();
		gas.A=A;					
		gas.greedyASelector(s,f);

		for(int j=1;j<s.length;j++)			//输出
		{
			if(gas.A[j]==0)
				System.out.print("");
			else
				System.out.print("a"+gas.A[j]+" ");
		}
	}
}