举个例子，形象介绍下什么是贪心算法
问题：假设有四种硬币，面值分别为二角五分、一角、五分和一分。现在要找给某顾客六角三分钱。
答案：六角三分钱 = 2 个二角五分+ 1 个一角+ 3 个一分
算法：首先选出一个面值不超过六角三分的最大硬币，即二角五分，从六角三分中减去二角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又一个二角五分，如此一直做下去。
转换：硬币的面值改为一分、五分和一角一分 3 种，要找给顾客的是一角五分钱。
答案：一角五分钱 = 1 个一角一分的硬币 + 4 个一分的硬币

活动安排问题

问题简介

1.活动安排问题要求高效地安排一系列争用某一公共资源的活动。设有n个活动的集合E={1, 2, …, n}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi ,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi )内占用资源。
2.若区间[si, fi )与区间[sj, fj )不相交，则称活动i与活动j是相容的，即当：
图片说明
3.活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

让我们思考下为什么选择这个最优策略？
1.如果选择最早开始时间为最优策略，那么有一个问题：如果它的结束时间最晚，晚到整个舞台使用时间，显然这个策略是有问题的。
2.如果选择最短活动时间为最优策略，那么如果它是最晚开始的，晚到整个舞台的最后使用时间，显然这个策略也不行。
3.那么就剩下以最早结束时间为最优策略。稍后的详解可以证明这个选择是对的。

贪心算法解决活动安排问题

1.首先将各活动的起始时间和结束时间存储于数组 s 和 f 中，然后将活动按活动结束时间的非减序进行排列：f1 ≤ f2≤…≤ fn。如果所给出的活动未按此序排列，可以用 O(nlogn)的时间将它重排。
图片说明
2.贪心选择策略：每次总是选择具有最早完成时间的相容活动加入集合中。
3.贪心算法一开始选择活动1，并将 j 初始化为1。然后依次检查活动 i 是否与当前已选择的所有活动相容。活动 i 与当前集合 A 中所有活动相容的充分且必要的条件是其开始时间 s 不早于最近加入集合 a 中的活动 j 的结束时间 fj， si ≥ fj。若活动 i 与之相容，则 i 成为最近加入集合 a 中的活动，因而取代活动 j 的位置。
图片说明
4.代码实现

package dynamic;

/*
 * 代码描述：
 * 贪心算法一开始选择活动1，并将 j 初始化为1。然后依次检查活动 i 是否与当前已选择的所有活动相容。
 * 活动 i 与当前集合 A 中所有活动相容的充分且必要的条件是其开始时间 s 不早于最近加入集合 a 中的活
 * 动 j 的结束时间 fj， si ≥ fj。若活 动 i 与之相容，则 i 成为最近加入集合 a 中的活动，因而取代活
 * 动 j 的位置。
 */

public class GreedySelector {

    private static int[] s= {0,1,3,0,5,3,5,6,8,8,2,12};
    private static int[] f= {0,4,5,6,7,8,9,10,11,12,13,14};
    private static boolean a[]=new boolean[f.length];
    private static int n=f.length-1;

    public static int greedySelector(int[] s,int[] f,boolean a[]) {
        /*
         * s[]记录活动开始时间
         * f[]记录活动结束时间，而且按降序排列
         * a[i]=true记录加入到安排表内的活动
         */
        a[1]=true; //贪心算法一开始选择活动1
        int j=1; //将j初始化为1
        int count=1; //记录加入到安排表内的活动数
        for(int i=2;i<=n;i++){ //开始选择活动1以后的活动
            if(s[i]>=f[j]) { //如果剩余活动的开始时间晚于或等于前一活动的结束时间，那么加入到安排表内
                a[i]=true; //表示这个活动i可以加入到安排表内
                j=i; //用于下一次剩余活动开始时间与上一个加入到安排表内的活动的结束时间的比较
                count++; //活动数增加
            }
            else a[i]=false; //否则这个活动不加入到安排表内

        }
        System.out.print("加入到安排表内的活动为：活动");
        for(int k=1;k<=n;k++) {
            if(a[k]==true)
                System.out.print(k+"、");
        }
        return count;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        greedySelector(s,f,a);

    }

}

程序截图：
图片说明
时间复杂性分析：
算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。

算法合理性分析

1.由于输入的活动以其完成时间的非减序排列，所以算法每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
2.贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。
3.证明：设E=｛1,2,…,n｝为所给的活动集合。首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动1。
（1）设A属于E是所给的活动安排问题的一个最优解，且A中活动也按结束时间非减序排列，A中的第一个活动是活动k。若k=1，则A就是一个以贪心选择开始的最优解。若k>1,则设B=A-{k} ∪{1}。由于f1＜fk，且A中活动是相容的，故B中的活动也是相容的。又由于B中活动个数与A中活动个数相同，且A是最优的，故B也是最优的。也就是说，B是以贪心选择活动1开始的最优活动安排。由此可见，总存在以贪心选择开始的最优活动安排方案。
（2）进一步，在做了贪心选择，即选择了活动1后，原问题就简化为对E中所有与活动1相容的活动进行活动安排的子问题。即若A是原问题的最优解，则A’=A-{1}是活动安排问题E’={i∈E:si>=f1}的最优解。事实上，如果能找到E’的一个解B’，它包含比A’更多的活动，则将活动1加入到B’中将产生E的一个解B，它包含比A更多的活动。这与A的最优性矛盾。因此，每一步所做的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题。对贪心选择次数用数学归纳法即知，贪心算法GreedySelector最终产生原问题的最优解。

贪心算法的基本要素

1.贪心算法通过一系列的选择来得到问题的解。它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。这种启发式的策略在许多情况下确能达到预期目的，解活动安排问题的贪心算法就是一个例子。
2.对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢? 从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质

1.贪心选择性质
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优选择来达到。通常可以用类似于证明活动安排问题的贪心选择性质时所采用的方法来证明。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。
2.最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。在活动安排问题中，其最优子结构性质表现为：若A是对于E的活动安排问题包含活动1的一个最优解。则相容活动A’=A-{1}是活动安排问题E’={i∈E: si>=f1}的一个最优解。

贪心算法与动态规划算法的主要区别