实际生活中，经常需要求一些问题的“可行解”和“最优解”，这就是所谓的“最优化”问题。一般来说，每个最优化问题都包含一组“限制条件”和一个“目标函数”，符合限制条件的问题求解方案称为可行解，使目标函数取得最佳值（最大或最小）的可行解称为最优解。求解最优化问题的算法很多，例如穷举、搜索、动态规划等。贪心法也是求解这类问题的一种常用方法。

- 贪心法的基本思想

贪心法是从问题的某个初始解出发，采用逐步构造最优解的方法，向给定的目标前进。在每一个局部阶段，都做一个“看上去”最优的决策，并期望通过每一次所做的局部最优选择产生出一个全局最优解。做出贪心决策的依据称为“贪心策略”。要注意的是，贪心策略一旦做出，就不可再更改。

与递推不同的是，贪心严格意义上说只是一种策略或方法，而不是算法。推进的每一步不是依据某一个固定的递推式，而是做一个当时“看似最佳”的贪心选择（操作），不断将问题归纳为更小的相似子问题。所以，归纳、分析、选择正确合适的贪心策略，是解决贪心问题的关键。

- 贪心法的正确性证明

对于一个问题，如果想用贪心法求解，首先要想到基于某种“序”或者“规则”的贪心策略。 其次还要能证明其正确性。要严格证明一个贪心算法的正确性是很困难的，目前最有效的一种方法叫“矩阵胚理论”，但是很复杂。信息学竞赛中常用的贪心证明方法，一般有反证法、构造法、调整法。其实，即使一个贪心算法是不完全正确的，也可以努力寻找一些调整方法，或制定多种贪心策略，通过调整优化、比较择优来争取得到最优解，甚至也可以先得到一个“较优”解，然后，在此基础上进行搜索剪枝或分支定界。

证明方法： （1） 反证法 用贪心的策略，依次构造出一个解 S1，假设最优解 S2 不同于 S1，可以证明是矛盾的，从而得出 S1 就是最优解。 （2） 构造法 根据描述的算法，用贪心的策略依次构造出一个解，可证明一定是合法的解。即用贪心法找可行解。 （3） 调整法 用贪心的策略，依次构造出一个解 S1。假设最优解 S2 不同于 S1，找出不同之处，在不破坏最优性的前提下，逐步调整 S2，最终使其变为 S1，从而 S1 也是最优解。

- 贪心算法三个核心问题

第一个问题：为什么不直接求全局最优解?

1、原问题复杂度过高； 2、求全局最优解的数学模型难以建立； 3、求全局最优解的计算量过大； 4、没有太大必要一定要求出全局最优解，“比较优”就可以。

第二个问题：如何把原问题分解成子问题？

1、按串行任务分 时间串行的任务，按子任务来分解，即每一步都是在前一步的基础上再选择当前的最优解。 2、按规模递减分 规模较大的复杂问题，可以借助递归思想（见第2课），分解成一个规模小一点点的问题，循环解决，当最后一步的求解完成后就得到了所谓的“全局最优解”。 3、按并行任务分 这种问题的任务不分先后，可能是并行的，可以分别求解后，再按一定的规则（比如某种配比公式）将其组合后得到最终解。

第三个问题：如何知道贪心算法结果逼近了全局最优值？

这个问题是不能量化判断的，正是因为全局最优值不能够知道，所以才求的局部最优值。追求过程需要考虑以下几个问题: 成本：耗费多少资源，花掉多少编程时间。 速度：计算量是否过大，计算速度能否满足要求。 价值：得到了最优解与次优解是否真的有那么大的差别，还是说差别可以忽略。

总结

这种贪心的策略，实际就是在当前状态下，选择一个最优的，是比较短视的，每次都是在眼前的几种决策里，挑一个当前最小的。这种局部最优解，最终会得到一个全局最优解。

贪心这种只看局部的策略，只适用于函数存在一个波峰的情况，如下，只要一直求解局部最优，最终就会到达全局最优（类似于AI中的梯度下降）

而如果函数存在多个波峰，则用贪心只能求得局部最优，但无法求得全局最优。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com