贪心算法

• 翻硬币：翻硬币 - 蓝桥云课 (lanqiao.cn)
• 快乐司机（lanqiao-1513）：【课后练习】快乐司机 - 蓝桥云课 (lanqiao.cn)
• 防御力：防御力 - 蓝桥云课 (lanqiao.cn)

【算法优点】

• 容易理解：生活常见

• 操作简单：在每一步都选局部最优

• 效率高：复杂度常常是O(1)的

【算法缺点】

• 缺点：局部最优不一定是全局最优

贪心算法的基本概念

贪心算法与枚举法的不同之处在于每个子问题都选择最优的情况，然后向下继续进行，且不能回溯，枚举法是将所有情况都考虑然后选出最优的情况。

贪心算法，在对问题求解时，不从整体考虑，而是采用一叶障目的选择方式，只选择某种意义上的局部最优解。并且，贪心算法是没有固定的模板可以遵循的，每个题日都有不同的贪心策略，所以算法设计的关键就是贪心策略的选择。

贪心算法有一个必须要注意的事情。贪心算法对于问题的要求是，所有的选择必须是无后效性的，即当前的选择，不能影响后续选择对于结果的影响。

贪心算法主要适用于最优化问题，如：MST问题。有时候贪心算法并不能得到最优答案，但是能得到精确答案的近似答案。有时可以铺助其他算法得到不是那么精确的结果。

符合贪心策略（贪心选择性质）：

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规算法的主要区别。所谓的贪心选择性质就是，该问题的每一步选择都在选择最优的情况下能够导致最终问题的答案也是最优。或者说是无后效性，如果该问题的每一步选择都对后续的选择没有影响，就可以是应用贪心算法。

贪心法求解的问题满足以下特征：

• 最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。从局部最优能扩展到全局最优。

• 贪心选择性质。问题的整体最优解可以通过一系列局部最优的选择来得到。

动态规划问题的特征：

• 重叠子问题：子问题是原大问题的小版本；计算大问题的时候，需要多次重复计算小问题。

• 最优子结构：大问题的最优解包含小问题的最优解；可以通过小问题的最优解推导出大问题的最优解。

例子：最少硬币问题

正解：使用动态规划解决

贪心算法的设计步骤

按照定义设计：

1. 证明原问题的最优解之一可以由贪心选择得到；

2. 将最优化问题转化为这样一个问题，即先做出选择，再解决剩下的一个子问题；

3. 对每一子问题一一求解，得到子问题的局部最优解；

4. 把子问题的解局部最优解合成原来解问题的一个解。

例子：活动安排问题（区间调度问题）

题目：有很多电视节目，给出它们的起止时间。有些节目时间冲突。问能完整看完的电视节目最多有多少？

例子：区间覆盖问题

例子：最优装载问题

例子：多机调度问题

贪心策略：最长处理时间的作业优先，即把处理时间最长的作业分配给最先空闲的机器。让处理时间长的作业得到优先处理，从而在整体上获得尽可能短的处理时间。

贪心习题

练习题目：贪心- 蓝桥云课 (lanqiao.cn)