【2】贪心算法-综述

前言
从前，有一个很穷的人救了一条蛇的命，蛇为了报答他的救命之
恩，于是就让这个人提出要求，满足他的愿望。这个人一开始只要求简
单的衣食，蛇都满足了他的愿望，后来慢慢地贪欲升起，要求做官，蛇
也满足了他。这个人直到做了宰相还不满足，还要求做皇帝。蛇此时终
于明白了，人的贪心是永无止境的，于是一口就把这个人吞掉了。
所以，蛇吞掉的是宰相，而不是大象。故此，留下了“人心不足
蛇吞相”的典故。

人之初，性本贪

我们小时候背诵《三字经》，
“人之初，性本善，性相近，习相远。
”其实我觉得很
多时候“人之初，性本贪”
。小孩子吃糖果，总是想要多多的；吃水果，想要最大的；
买玩具，总是想要最好的，这些东西并不是大人教的，而是与生俱来的。对美好事物
的趋优性，就像植物的趋光性，
“良禽择木而栖，贤臣择主而事”“窈窕淑女，君子好逑”
，我们似乎永远在追求美而优的东西。现实中的很多事情，正是因为趋优性使
我们的生活一步一步走向美好。例如，我们竭尽所能买了一套房子，
然后就想要添置一些新的家具，再就想着可能还需要一辆车子…… 凡事都有两面性，一把刀可以做出美味佳肴，也可以变成杀人凶器。
在这里，我们只谈好的“贪心”。
贪心算法
贪心算法的本质
算法导论中如是说：


在贪心算法中，注意以下几个问题：
（1）没有后悔药。一旦做出选择，不可以反悔。
（2）有可能得到的不是最优解，而是最优解的近似解。
（3）选择什么样的贪心策略，直接决定算法的好坏。
贪心算法需要遵循的原则

在解决问题时，通常把原问题分解成规模较小的子问题。
如果原问题的解没有办法通过子问题的解而得到，那么这个分解是没有意义的。
贪心算法的秘籍
（1）贪心策略的确定

（2）局部最优解
根据贪心策略，一步一步地得到局部最优解。例如，第一次选一个
最大的苹果放起来，记为a1，第二次再从剩下的苹果堆中选择一个最大
的苹果放起来，记为a2，以此类推。
（3）全局最优解
把所有的局部最优解合成原来问题的一个最优解。
类似于冒泡排序就是采用的贪心的算法


贪心算法的缺点主要有以下几点：

• 可能无法得到全局最优解：贪心算法通常只考虑当前情况下的最优解，而不考虑后续步骤对解的影响。因此，可能会得到局部最优解，但不是全局最优解。
• 需要满足贪心选择性质：贪心算法只能用于满足贪心选择性质的问题。如果问题没有这种性质，那么贪心算法将无法提供正确的解决方案。
• 可能受限于问题的约束条件：问题的约束条件可能对贪心算法的有效性产生限制。如果问题的约束条件不满足某些条件，贪心算法可能就无法提供正确的解决方案。
• 可能存在多个最优解：对于某些问题而言，可能存在多个最优解。在这种情况下，贪心算法可能会得到任意一个最优解，但无法保证得到的是哪一个。
  算法的求解步骤
• 问题分析（策略选择）
• 算法设计
• 完美图解
• 伪代码
• 实战演练
• 算法解析（时间复杂度、空间复杂度）