2.1.3 为贪心加上限制

没有带上脖套的狗可能会咬人，带上脖套的狗可以看家，适当的贪心可以得到问题的最优解，过度的贪心会适得其反，这就需要我们为贪心加个“度”。对于一个具体的最优解问题，是否使用贪心算法求解，按照贪心策略得到的全局解是否一定最优，没有一个通用的判定方法。但是，可以通过贪心算法求解的最优问题一般有两个特点：

（1）最优子结构——问题的最优解包含了子问题的最优解，比如，你要考到班级第一名，那你一定是考进了班级前两名，考进了班级前两名，那一定是考进了前五名。

（2）贪心选择性质——可通过局部最优选择来达到全局最优解，贪心选择性质是贪心算法的核心，贪心的每一步都只依赖当前已有的信息，而不依赖“未来”的信息。如果把贪心的过程当作人生的旅程，那么当我们回首往事时，会发现每个阶段的自己做的选择都是最正确的，由此我们可以意识到贪心选择条件是多么的严苛，所以我们要慎用贪心。

注意：我们要慎用贪心，贪心往往不能保证是全局最优解，一般产生的是整体最优解的近似解。