贪心算法是就问题而言，选择当下最好的选择，而不从整体最优考虑，通过局部最优希望导致全局最优。
贪心算法的要素
1）贪心选择性质：可以通过局部最优选择来构造全局最优解。换言之，直接做出在当前问题中看来最优的选择，而不必考虑子问题的解。
2）最优子结构：一个问题的最优解包含其子问题的最优解。
贪心算法的设计步骤：
1）将最优化问题转换为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解
2）证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的
3）证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
示例：背包问题，均分纸牌，最大整数
作者：半路和尚怎么出家
链接：https://www.jianshu.com/p/48a6bdfccff1
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
五大常用算法之一：分治算法 五大常用算法之二：动态规划算法 五大常用算法之三：贪心算法 五大常用算法之四：回溯法 ...
而它属于五大常用算法之一，而五大常用算法为：分治、动态规划、贪心、回溯、分支界定。下面来看一下具体相关的算法。 查...
基本常识 kmp算法百度百科 动态规划几个经典例子总结 五大常用算法之四：回溯法 五大常用算法之五：分支限界法 P...
引言 据说有人归纳了计算机的五大常用算法，它们是贪婪算法，动态规划算法，分治算法，回溯算法以及分支限界算法。虽然不...
分治算法 一、基本概念 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题...
五大常用算法之一：分治算法 基本概念： 把一个复杂的问题分成两个或更多的相同的或相似的子问题。再把子问题分成更小的...
摘自：五大常用算法的简单介绍 1、递归与分治 递归算法：直接或者间接不断反复调用自身来达到解决问题的方法。这就要求...
1.贪心算法 贪心算法的要素 1）贪心选择性质：可以通过局部最优选择来构造全局最优解。换言之，直接做出在当前问题中...
五大常用算法之一：分治算法 一、基本概念 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就...
前言 数据结构与算法的重要性已不言而喻，最近，我整理出十大经典排序算法、五大常用算法总结，今天特意整理出微软面试的...
本文标题：五大常用算法
本文链接：https://www.haomeiwen.com/subject/nnnuwltx.html
网友评论