贪心算法

贪心算法总是做出当前最好的选择，期望通过局部最优选择得到全局最优的解决方案。从问题的初始解开始，一步歩地做出当前最好的选择，逐步逼近问题的目标，尽可能得到最优解；即使得不到最优解，也可以得到最优解的近似解¹。

贪心算法要点

如果问题具有两个特性：贪心选择性质和最优子结构性质，则可以用贪心算法¹。

• 贪心选择性质：贪心选择性质指原问题的整体最优解可以通过一系列局部最优的选择得到。应用同一规则，将原问题变为一个相似的、但规模更小的子问题，而后的每一步都是当前最优的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。运用贪心算法解决的问题在程序的运行过程中无回溯过程。
• 最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题是否可以用贪心算法求解的关键。例如原问题$S= \{a_1 ,a_2 ,\dots,a_i ,\dots,a_n \}$，通过贪心选择选出一个当前最优解$\{a_i\}$之后，转化为求解子问题$S -\{a_i\}$，如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质。

最优惠促销方案选择

假设存在 $10$ 个商品，我们分别将其列为 $\{ A_1,A_2,\dots\,A_{10}\}$，存在以下优惠策略。

• $\{A_1,A_2\}$ 优惠 10 元
• $\{A_2,A_3\}$ 优惠 5 元
• $\{A_7,A_5\}$ 优惠 3 元

那么解题步骤如下：

• 先从3中优惠中选出优惠力度最大的策略，即：$\{A_1,A_2\}$ 优惠 10 元。这时还剩下 $\{ A_3,A_4,\dots\,A_{10}\}$ 8 个商品；
• 然后再从这8个商品及两种优惠策略中选择出优惠力度最大的策略，即：$\{A_7,A_5\}$ 优惠 3 元；
• 最终得出结论，采用优惠组合 $\{A_1,A_2\}$ 和 $\{A_7,A_5\}$ 共优惠13元，而这个答案就是本问题的最优解。

上面也提到了，我们得出的结论可能不是最优解，而是一个近似解。现在变换一下优惠策略，如下：

• $\{A_1,A_2\}$ 优惠 10 元
• $\{A_1,A_3\}$ 优惠 8 元
• $\{A_2,A_5\}$ 优惠 7 元
• $\{A_3,A_5\}$ 优惠 3 元

运用贪心法，我们会选出 $\{A_1,A_2\}$ 和 $\{A_3,A_5\}$ 两个组合，共优惠 13 元，但是这个解显然不是问题的最优解。而选择 $\{A_1,A_3\}$ 和 $\{A_2,A_5\}$ 的组合可以有 15 元的优惠，这个才是最优解。

面对同类问题，贪心算法有时能得出最优解，有时只能得出近似解。

参考资料

1. 陈小玉. 算法训练营：海量图解+竞赛刷题（入门篇）. 电子工业出版社. 2021. ISBN：9787121414428 ↩ ↩²