何为贪心
假设有四种硬币：二角五分、一角、五分和一分。现要找给顾客六角三分。 显然，会拿出2个二角五分、1个一角和3个一分的硬币交给顾客。 贪心方法思路：首先选出一个面值不超过六角三分的最大硬币，即二角五分，然后在剩余数中再选最大面值的硬币，依此类推，得到其解。 若硬币面值改为：一角一分、五分和一分，而要找给顾客一角五分钱。 用贪心算法将找给1个一角一分和4个一分的硬币。然而，3个五分硬币是最好的找法。 此时，贪心算法没有得到整体最优解。但通常可得到最优解的很好近似。
顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 当然，希望贪心算法得到的最终结果也是整体最优的。 虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。 在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
贪心算法的基本要素
考察用贪心算法求解的问题的一般特征对于一个具体问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢? 这个问题很难给予肯定的回答。从许多用贪心算法求解的问题中看到，这类问题一般具有2个重要性质：贪心选择性质和最优子结构性质。
贪心选择性质
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。也是贪心算法与动态规划算法的主要区别。贪心算法通过一系列的选择来得到问题的解，它所做的每步选择都是当前状态下局部最好选择，即局部最优选择（贪心选择）。贪心算法所做的贪心选择可以依赖于以往所做过的选择，但不依赖于子问题的解。每作一次贪心选择就将所求问题简化为规模更小的子问题。在动态规划算法中，每步所做的选择往往依赖于相关子问题的解，因而只有在解出相关子问题后，才做出选择。正是由于上述差别，动态规划方法以自底向上的方式解决各个子问题，而贪心方法以自顶向下的方式进行。
证明贪心选择性质的方法: 对具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
首先考察一个问题的整体最优解（x1,x2,…,xn），并证明可修改这个最优解，使其以贪心选择开始。然后，用数学归纳法证明，通过进一步做贪心选择，最终可得到问题的整体最优解（y1,y2,…,yn） （y1,y2,…,yn）是用贪心选择做出的最优解。
最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
贪心选择与最优子结构
满足贪心选择性质必满足最优子结构性质。满足最优子结构性质却未必满足贪心选择性质。虽然能够应用贪心算法一定能够应用动态规划法，但是一般来说，贪心算法的效率高于动态规划法，因而还是应用贪心算法。
贪心算法与动态规划算法的差异
共同点：贪心算法和动态规划算法都要求问题具有最优子结构性质。具有最优子结构的问题应该选用贪心算法，还是动态规划算法求解? 是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题(0-1背包问题和装载问题)，并以此说明贪心算法与动态规划算法的主要差别。
👉结合0-1背包问题和装载问题进行分析
贪心算法的一般框架
GreedyAlgorithm(parameters
)
{
初始化；
重复执行以下的操作：
选择当前可以选择的最优解；
将所选择的当前解加入到问题的解中去；
直至满足问题求解的结束条件。
}
活动安排问题
👉 活动安排问题-贪心
0-1背包问题(不适合用贪心)
👉 0-1背包问题-贪心(不适合用贪心)
最优装载
👉 最优装载-贪心
哈夫曼编码
👉哈夫曼编码-贪心
单源最短路径
👉 单源最短路径-贪心(Dijkstra (迪杰斯特拉),有向图，无向图)
最小生成树（Prim）
👉 最小生成树-贪心(Prim算法(普里姆算法))
最小生成树（Kruskal）
👉 最小生成树-贪心(Kruskal算法(克鲁斯卡尔算法))
汽车加油问题
👉 汽车加油问题-贪心
