贪心算法
贪心算法通过一系列的选择来得到问题的解。它所做的每一个选择都是当前状态下局部的最好选择，即贪心选择。
贪心选择的一般特征：贪心选择性质和最优子结构性质。
贪心选择性质：
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。然后再去解出做出这个选择后产生的相应的子问题。贪心算法所做的贪心选择可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各个问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，没做一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。
最优子结构性质：
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
弹性算法与动态规划算法的差异：
贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。大多数时候，能用贪心算法求解的问题，都可以用动态规划算法求解。但是能用动态规划求解的，不一定能用贪心算法进行求解。
活动安排问题：
问题：
设有n个活动的集合E={1,2,...,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间Si和一个结束时间Fi，且Si<Fi。如果选择了活动i，则它在半开时间区间[Si,Fi)内占用资源。若区间[Si,Fi)与区间[Sj，Fj）不相交，则称活动i与活动j是相容的。也就是说Si>=Fj或Sj>=Fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选择出最大的相容活动子集合。
关于证明：
这个问题可以使用贪心算法进行求解。其实这个问题的关键并不是如何用贪心算法求解，而是如何证明这个问题可以用贪心算法求解。鉴于证明的复杂性，还是不在此讨论证明问题。其实贪心算法问题的证明无非都是用数学归纳法证明，不错就是那个传说中万能证明法，数学归纳法。还是直接讨论实现过程吧。
实现：
首先将活动按照活动的结束时间非递减：F1<=F2<=...<=Fn排序。如果所给的活动未排序，则先将活动按此序排列，时间复杂度一般为O(nlogn)可解决。以下是解决问题的算法。
//贪心算法-活动安排的实现
#include "stdafx.h"
#include "stdio.h"
template<class Type>
void GreedySelector(int n,Type s[],Type f[],bool A[])
{
A[0]=1; //第一个直接选取
int j=0;
for(int i=1;i<n;i++)
{
if(s[i]>=f[j]){A[i]=true;j=i;} //如果第i+1的活动的开始时间大于或等于第i个活动的结束时间，则标记该活动
else A[i]=false;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
//初始化数据
int n=3;
int s[3]={1,2,4}; //开始时间
int f[3]={3,3,5}; //结束时间
bool A[3]={0,0,0}; //数组A用于标记是否选择活动，1表示选择，0表示不选择
GreedySelector<int>(n,s,f,A);
for(int i=0;i<n;i++)
{
printf("%d\n",A[i]);
}
}
该算法的贪心选择的意义是使剩余的可安排的时间段极大化，以便安排尽可能多的相容活动。也就是说，每次选择完了之后，保证这次的选择之后留下的时间是最多的。
测试结果
时间复杂度：
GreedySelector算法效率极高。当输入的数据是已经按照结束时间非递减排序好的时候，算法只需要O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。
适用范围：
贪心算法并不能总求得问题的整体最优解。但对于某些问题，却总能求得整体最优解，这要看问题时什么了。只要能满足贪心算法的两个性质：贪心选择性质和最优子结构性质，贪心算法就可以出色地求出问题的整体最优解。即使某些问题，贪心算法不能求得整体的最优解，贪心算法也能求出大概的整体最优解。如果你的要求不是太高，贪心算法是一个很好的选择。最优子结构性质是比较容易看出来的，但是贪心选择性质就没那么容易了，这个时候需要证明。证明往往使用数学归纳法。
适用范围个人总结的一句话，能证明用就可以用。（因为个人觉得证明比算法实现还难）
