「贪心算法 greedy algorithm」是一种常见的解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期望获得全局最优解。
贪心算法和动态规划都常用于解决优化问题。它们之间存在一些相似之处，比如都依赖最优子结构性质，但工作原理是不同的。
- 动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解。
- 贪心算法不会重新考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决。
零钱兑换问题
Q:给定 𝑛 种硬币，第 𝑖 种硬币的面值为 𝑐𝑜𝑖𝑛𝑠[𝑖 − 1] ，目标金额为 𝑎𝑚𝑡 ，每种硬币可以重复选取，问能够凑出目标金额的最少硬币个数。如果无法凑出目标金额则返回 −1 。
[1, 5, 10, 20, 50, 100]：在该硬币组合下，给定任意 target
def greedy(coins, target): coins.sort() i = len(coins)-1 count = 0 while target > 0: while i > 0 and coins[i] > target: i -= 1 target -= coins[i] count += 1 return count if target == 0 else -1
贪心优点与局限性
贪心算法不仅操作直接、实现简单，而且通常效率也很高。对于某些硬币面值组合，贪心算法并不能找到最优解。
一般情况下，贪心算法适用于以下两类问题。
- 可以保证找到最优解：贪心算法在这种情况下往往是最优选择，因为它往往比回溯、动态规划更高效。
- 可以找到近似最优解：贪心算法在这种情况下也是可用的。对于很多复杂问题来说，寻找全局最优解是非常困难的，能以较高效率找到次优解也是非常不错的。
贪心算法特性和解题步骤
相较于动态规划，贪心算法的使用条件更加苛刻，其主要关注问题的两个性质。
- 贪心选择性质：只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证得到最优解。
- 最优子结构：原问题的最优解包含子问题的最优解。
贪心问题的解决流程大体可分为以下三步。
- 问题分析：梳理与理解问题特性，包括状态定义、优化目标和约束条件等。这一步在回溯和动态规划中都有涉及。
- 确定贪心策略：确定如何在每一步中做出贪心选择。这个策略能够在每一步减小问题的规模，并最终能解决整个问题。
- 正确性证明：通常需要证明问题具有贪心选择性质和最优子结构。这个步骤可能需要使用到数学证明，例如归纳法或反证法等。
确定贪心策略是求解问题的核心步骤，但实施起来可能并不容易，主要包含以下原因。
- 不同问题的贪心策略的差异较大。对于许多问题来说，贪心策略都比较浅显，我们通过一些大概的思考与尝试就能得出。而对于一些复杂问题，贪心策略可能非常隐蔽，这种情况就非常考验个人的解题经验与算法能力了。
- 某些贪心策略具有较强的迷惑性。当我们满怀信心设计好贪心策略，写出解题代码并提交运行，很可能发现部分测试样例无法通过。这是因为设计的贪心策略只是“部分正确”的，上文介绍的零钱兑换就是个典型案例。
为了保证正确性，我们应该对贪心策略进行严谨的数学证明，通常需要用到反证法或数学归纳法。然而，正确性证明也很可能不是一件易事。如若没有头绪，我们通常会选择面向测试用例进行 Debug ，一步步修改与验证贪心策略。
贪心典型例题
贪心算法常常应用在满足贪心选择性质和最优子结构的优化问题中，以下列举了一些典型的贪心算法问题。
- 硬币找零问题：在某些硬币组合下，贪心算法总是可以得到最优解。
- 区间调度问题：假设你有一些任务，每个任务在一段时间内进行，你的目标是完成尽可能多的任务。如果每次都选择结束时间最早的任务，那么贪心算法就可以得到最优解。
- 分数背包问题：给定一组物品和一个载重量，你的目标是选择一组物品，使得总重量不超过载重量，且总价值最大。如果每次都选择性价比最高（价值 / 重量）的物品，那么贪心算法在一些情况下可以得到最优解。
- 股票买卖问题：给定一组股票的历史价格，你可以进行多次买卖，但如果你已经持有股票，那么在卖出之前不能再买，目标是获取最大利润。
- 霍夫曼编码：霍夫曼编码是一种用于无损数据压缩的贪心算法。通过构建霍夫曼树，每次选择出现频率最小的两个节点合并，最后得到的霍夫曼树的带权路径长度（即编码长度）最小。
- Dijkstra 算法：它是一种解决给定源顶点到其余各顶点的最短路径问题的贪心算法。
分数背包
给定 𝑛 个物品，第 𝑖 个物品的重量为𝑤𝑔𝑡[𝑖 − 1]、价值为 𝑣𝑎𝑙[𝑖 − 1] ，和一个容量为 𝑐𝑎𝑝的背包。每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算，问在不超过背包容量下背包中物品的最大价值。
代码
def greedy(weights, values, cap): items = [Item(key, val) for key, val in zip(weights, values)] items.sort(key=lambda item: item.value/item.weight, reverse=True) n = len(items) i = 0 val = 0 while cap > 0 and i < n: if items[i].weight < cap: val += items[i].value cap = cap - items[i].weight else: val += items[i].value/items[i].weight * cap cap = 0 i += 1 return val
最大容量问题
输入一个数组 ℎ𝑡 ，数组中的每个元素代表一个垂直隔板的高度。数组中的任意两个隔板，以及它们之间的空间可以组成一个容器。容器的容量等于高度和宽度的乘积（即面积），其中高度由较短的隔板决定，宽度是两个隔板的数组索引之差。请在数组中选择两个隔板，使得组成的容器的容量最大，返回最大容量。
def greedy(ht): i, j = 0, len(ht)-1 res = 0 while i < j: cap = min(ht[i], ht[j]) * (j - i) if cap > res: res = cap if ht[i] > ht[j]: j -= 1 elif ht[i] == ht[j]: ix, jx = ht[i+1] - ht[i], ht[j-1] - ht[j] if ix >= jx: i += 1 else: j -= 1 else: i += 1 return res
最大切分乘积问题
给定一个正整数 𝑛 ，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少。
总结以上，可推出以下贪心策略。
- 输入整数 𝑛，从其不断地切分出因子3，直至余数为 0、1、2 。
- 当余数为0时，代表𝑛是 3 的倍数，因此不做任何处理。
- 当余数为2时，不继续划分，保留之。
- 当余数为1时，由于2 × 2 > 1 × 3，因此应将最后一个3替换为2 。
代码
def greedy(num): import math if num <= 3: return num-1 else: a = num//3 b = num%3 if b == 1: return int(math.pow(3, a-1) * 2 * 2) if b == 2: return int(math.pow(3, a) * 2)
重点回顾
- 贪心算法通常用于解决最优化问题，其原理是在每个决策阶段都做出局部最优的决策，以期望获得全局最优解。
- 贪心算法会迭代地做出一个又一个的贪心选择，每轮都将问题转化成一个规模更小的子问题，直到问题被解决。
- 贪心算法不仅实现简单，还具有很高的解题效率。相比于动态规划，贪心算法的时间复杂度通常更低。
- 在零钱兑换问题中，对于某些硬币组合，贪心算法可以保证找到最优解；对于另外一些硬币组合则不然，贪心算法可能找到很差的解。
- 适合用贪心算法求解的问题具有两大性质：贪心选择性质和最优子结构。贪心选择性质代表贪心策略的有效性。
- 对于某些复杂问题，贪心选择性质的证明并不简单。相对来说，证伪更加容易，例如零钱兑换问题。
- 求解贪心问题主要分为三步：问题分析、贪心策略确定、正确性证明。其中，贪心策略确定是核心步骤，正确性证明往往是难点。
- 分数背包问题在 0‑1 背包的基础上，允许选择物品的一部分，因此可使用贪心算法求解。贪心策略的正确性可以使用反证法来证明。
- 最大容量问题可使用穷举法求解，时间复杂度为𝑂(𝑛2 ) 。通过设计贪心策略，每轮向内移动短板，可将时间复杂度优化至𝑂(𝑛) 。
- 在最大切分乘积问题中，我们先后推理出两个贪心策略：≥ 4 的整数都应该继续切分、最优切分因子为 3 。代码中包含幂运算，时间复杂度取决于幂运算实现方法，通常为𝑂(1) 或 𝑂(log 𝑛) 。
