0、概念

0.1.定义

贪心算法（greedy algorithm ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 。
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯

0.2.特征

利用贪心法求解的问题应具备如下2个特征：
1、贪心选择性质
一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
2、最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析。

0.3.步骤

贪心算法一般按如下步骤进行：
①建立数学模型来描述问题。
②把求解的问题分成若干个子问题。
③对每个子问题求解，得到子问题的局部最优解。
④把子问题的解局部最优解合成原来解问题的一个解。

0.4.适用

由贪心算法的定义来说，贪心算法一般适用的场所：
1、贪心算法一般用来解决求最大或最小解；
2、贪心算法只能确定某些问题的可行性范围。

1、与动态规划的联系

1.1.区别

1.贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解则不作保留；
动态规划：全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有的局部最优解；
2、动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常自顶向下的方式进行。
3、根据以上两条可以知道，贪心不能保证求得的最后解是最佳的，一般复杂度低；而动态规划本质是穷举法，可以保证结果是最佳的，复杂度高。

1.2.联系

1、都是分解成子问题来求解，都需要具有最优子结构
2、所有的贪心问题都可以用动态规划来求解，可以这么说，贪心算法是动态规划的特例。

举个列子：平时购物找零钱时，为使找回的零钱的硬币数最少，不要求找零钱的所有方案，而是从最大面值的币种开始，按递减的顺序考虑各面额，先尽量用大面值的面额，当不足大面值时才去考虑下一个较小面值，这就是贪心算法。

有很多经典的应用，比如霍夫曼编码，普利姆和克鲁斯卡尔最小生成树算法，还有迪杰斯特拉单源最短路径算法，都是使用了这种思维。

2、例子

1、题目：n个作业组成的作业集，可由m台相同机器加工处理。要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
2、思路：作业不能拆分成更小的子作业；每个作业均可在任何一台机器上加工处理。这个问题是NP完全问题，还没有有效的解法(求最优解)，但是可以用贪心选择策略设计出较好的近似算法(求次优解)。当n<=m时，只要将作业时间区间分配给作业即可；当n>m时，首先将n个作业从大到小排序，然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中，选择需要处理时间最长的，把它分配给当前总累计需要工作时长最短的机器。这样一来，这个调度问题可以理解为一个分配问题，我们通过这种方案，使得几台机器获得接近的工作总时长，达到整体的最短的工作时长的效果。
3、算法实现：

	/**多机调度问题*/
	public void greedy()
	{
	  int time[] = {9,7,8,4,2,1,3};
      int number = 3;
	  int Sumtime = getNumber4(time,number);
	  println("花费的最小总时间："+Sumtime);		
	}
	int getNumber(int time[] , int number)
	{
		int usedTime=0;               //最长时间为总时间
		int[] fin = new int[number];  //单机处理时间		
		for(int k=0;k<number;k++)     //初始时间清零
		{
			fin[k]=0;
		}		
		if(number>time.length)
			return time[0];
		else 
		{			
			for( int i=0 ; i<time.length-1 ;i++)
			{  
				   for( int j=0;j<time.length-i-1;j++) //冒泡选出任务时间最大的
				   {
					   if(time[j]>time[j+1])
					   {
						   int temp = time[j+1];
						   time[j+1]=time[j];
						   time[j]=temp;
					   }
				   }
					   int min=0;; 
					   int value=100;
					   for(int k=0;k<fin.length;k++)  //选出当前累计工时最小的机子
					   {
						   if(fin[k]<value)
						   {
							   min=k;
							   value=fin[k];
						   }						  
					   }					   						
					   fin[min]+=time[time.length-1-i];							   
			} 
			   int min=0;; 
			   int value=100;
			   for(int k=0;k<fin.length;k++)  //选出当前累计工时最小的机子
			   {
				   if(fin[k]<value)
				   {
					   min=k;
					   value=fin[k];
				   }				  
			   }
			   fin[min]+=time[0];
			for( int n=0;n<fin.length;n++)
			{
				if(fin[n]>usedTime)
				{
					usedTime=fin[n];
				}
			}
			return usedTime;
		}		
	}