基本思想

贪心算法是一种稳扎稳打的算法，它从问题的某一个角度出发，在每一个阶段都根据相应的贪心策略做出当前最优决策，逐步逼近最终目标，尽可能快地求出最优解。贪心算法可以理解为局部最优，最后达到全局最优。贪心算法的核心思想就是“今朝有酒今朝醉”，只考虑当前面临的问题，不考虑接下来会发生什么。

特点

• 1.贪心算法每个决策一旦做出，不可撤回，即贪心不允许回溯。
• 2.贪心是根据贪心策略来逐步构造问题的，所选贪心策略不同，其具体算法实现也会不同，算法质量也不同。因此，算法的好坏在于贪心策略的选择。
• 3.贪心算法就有高效性和不稳定性，因为它可以迅速地得到一个解，但不一定是最优解，但无论是不是最优解，它一定是最优解的一个近似值。

基本要素

1.最优子结构

当一个问题的最优解一定包含其子问题的最优解时，此问题具有最优解性质。即一个问题能分成若干个子问题，通过对子问题的最优解的推导（数学归纳），可以得到原问题的最优解。只有问题的子问题具有最优解时，才能保证贪心可以求得原问题的最优解。

2.贪心选择性质

贪心选择性质是指通过一系列的逐步局部最优选择，使得最终的选择是最优的，其次，每次做的选择依赖于前一次的选择，但不依赖于下一次的选择。贪心所做的是一个非线性的子问题处理（一个子问题不依赖于另一个子问题，但又有严格的处理顺序要求）。

贪心法的解题步骤

• 1.将问题分为若干个互相独立的子问题。
• 2.制定贪心策略并选择最合适的策略
• 3.对于每个阶段，依据贪心策略进行贪心选择，并求出最优解。
• 4.将各个子问题的解，合并为原问题的一个解。