基本思想

贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心算法的基本要素

2个重要的性质：贪心选择性质和最优子结构性质。

1、贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2、最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

3、贪心算法与动态规划算法的差异

贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。（01背包问题和背包问题）
分析：
对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。
实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。

拓展

贪心策略一旦经过证明成立后，它就是一种高效的算法。贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的
贪心算法可以与随机化算法一起使用。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）

经典问题

活动安排问题
最优装载
单源最短路径
最小生成树

考点：

1、能采用贪心算法求最优解的问题，一般具有的重要性质为：最优子结构性质与贪心选择性质
2、贪心选择性质是指：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
3、最优子结构性质是指：问题的最优解包含了其子问题的最优解.
4、贪心算法
基本思想：一种依据最优化量度依次选择输入的分级处理方法。
基本思路：
1、根据题意，选取最优化量度标准；
2、根据量度标准对这 n 个输入排序，依次选择输入量加入部分解中。
3、判断加入量是否满足约束条件，不满足则不把此输入加到这部分解中。
5、背包问题的目标函数和贪心算法最优化量度相同吗？
答：不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。
6、贪心算法总是做出当前看来最好的选择。就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。
7、最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
8、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
9、Prim算法利用贪心策略求解最小生成树问题,其时间复杂度是O(n2)。
10、请叙述动态规划算法与贪心算法的异同。

共同点：都需要最优子结构性质，都用来求有优化问题。
不同点：
- 动态规划：每一步作一个选择—依赖于子问题的解。
- 贪心方法：每一步作一个选择—不依赖于子问题的解。
- 动态规划方法的条件：子问题的重叠性质。
- 可用贪心方法的条件：最优子结构性质；贪心选择性质。
- 动态规划：自底向上求解；
- 贪心方法：自顶向下求解。
- 可用贪心法时，动态规划方法可能不适用；
- 可用动态规划方法时，贪心法可能不适用。

11、背包问题的贪心算法所需的计算时间为O(nlogn）
12、解决活动安排问题，最好用（B ）算法
A.分治 B.贪心 C.动态规划 D.穷举

13、哈弗曼编码的贪心算法所需的计算时间为（ B ）。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）

14、采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为 ( B ) 。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）

void Knapsack(int n,float M,float v[],float w[],float x[])
{
    Sort(n,v,w);         计算时间为O(nlogn）
    int i;
    for (i=1;i<=n;i++) 
        x[i]=0;
    float c=M;
    for (i=1;i<=n;i++) 
    {
        if (w[i]>c) break;
        x[i]=1;
        c - =w[i];
    }
    if (i<=n) 
        x[i]=c/w[i];
}

克鲁斯卡尔(Kruskal)算法：
贪心策略：每次都在连接两个不同连通分量的边中选权值最小的边。
基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。