开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
2023.02.25湖南
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的是在某种意义上的局部最优解。
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。实际上，贪心算法适用的情况很少。一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可以做出判断。
大多数可以使用贪心算法的问题都有以下特点：（1）原问题复杂度过高；（2）求全局最优解的数学模型难以建立；（3）求全局最优解的计算量过大；（4）没有太大必要一定要求出全局最优解，“比较优”就可以。
严格来说，贪婪算法可解决的问题通常大部分都有如下的特性：（1）随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。（2）有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。（3）还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。（4）选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。（5）最后，目标函数给出解的值。（6）为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。
贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策略的选择，根据不同的问题选择不同的策略。
必须注意的是策略的选择必须具备无后效性，即某个状态的选择不会影响到之前的状态，只与当前状态有关，所以对采用的贪婪的策略一定要仔细分析其是否满足无后效性。
整数转罗马数字问题：
解题思路：这道题要将4，9，40，90，400，900的符号单列出来。然后我们使用贪心算法，每次运算都将总数减去最大的可能数值，直到减到0。（就像假如你要付67块钱，肯定先找出一张50块，再找出一张10块，再找出一张5块，最后找出两张1块）。
下面附上Python3的题解代码
以下是LeetCode题库中一些用到贪心算法的经典例题的题目及解析，有题干，有题解代码、有解题思路（持续更新）：