贪心算法

missonce 发布于2019-07-30 16:39 / 690人阅读

摘要：贪心算法与动态规划算法的差异贪心算法和动态规划算法都要求问题具有最优子结构性质，这是类算法的一个共同点。

贪心算法的基本要素
对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。
但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。

1、贪心选择性质
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2、最优子结构性质
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。

3、贪心算法与动态规划算法的差异
贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。

贪婪算法可解决的问题通常大部分都有如下的特性：
随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
最后，目标函数给出解的值。
为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。

GPU云服务器云服务器贪心算法的题目贪心算法java找零最简单的贪心算法最小集合覆盖贪心算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/41779.html

【LeetCode】贪心算法--买卖股票的最佳时机 II（122）

摘要：贪心算法每一步必须满足一下条件可行的即它必须满足问题的约束。四题目分析贪心算法，总是做出在当前看来是最好的选择，不从整体最优上加以考虑，也就是说，只关心当前最优解，按照贪心策略，不关心以后，我们只关心当前利益。一、写在前面为什么要在LeetCode刷题？大家都知道不管是校招还是社招算法题是必考题，而这一部分恰巧是大多数人的短板，所以刷题首先是为了提高自身的编程能力，能够在算法面试中...

xbynet 2019-07-31 11:21 评论0 收藏0
基本算法思想：递归+分治+动态规划+贪心+回溯+分支限界

摘要：代码实现见下面评论对应代码动态规划基本思想和分治法基本思想有共同的地方，不同的是子问题往往不是独立的，有事母问题要借助子问题的解来判断，因此把已经计算好的问题记录在表格中，后续如果需要查询一下，可以避免重复计算，这是动态规划的基本思想。作者：心叶时间：2018-05-01 19:28 本文对应github地址：https://github.com/yelloxing/... 以上实现...

EscapedDog 2019-08-26 11:52 评论0 收藏0
【LeetCode】贪心算法--划分字母区间（763）

摘要：写在前面今天这篇文章是贪心算法系列的第三篇划分字母区间。前文回顾贪心算法分发糖果刷题汇总汇总贴今日题目字符串由小写字母组成。返回一个表示每个字符串片段的长度的列表。示例输入输出解释划分结果为。每个字母最多出现在一个片段中。写在前面今天这篇文章是贪心算法系列的第三篇--划分字母区间。前文回顾：【LeetCode】贪心算法--分发糖果（135）刷题汇总：【LeetCode】汇总...

honhon 2019-07-31 11:21 评论0 收藏0
【LeetCode】贪心算法--分发糖果（135）

摘要：今日题目老师想给孩子们分发糖果，有个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。相邻的孩子中，评分高的孩子必须获得更多的糖果。示例输入输出解释你可以分别给这三个孩子分发颗糖果。第三个孩子只得到颗糖果，这已满足上述两个条件。今日题目老师想给孩子们分发糖果，有N个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖...

刘永祥 2019-07-30 18:46 评论0 收藏0