贪心算法
贪心算法，又称贪婪算法：在对问题求解时，总是做出在当前看来时最好的选择，本质是选择每一阶段的局部最优，从而达到全局最优。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
贪心算法和动态规划的对比：
- 贪心算法与动态规划的不同在于贪心算法对每个子问题的解决方案都做出选择，不能回退；
- 动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
算法特性
这个算法能解决的大多数问题都有以下两个特性：
- 贪心属性：它的意思是每次迭代时都采用局部最优解，而无需考虑对全局的影响。我们相信通过不断求解局部最优解终会得到全局最优解，但是正如我之前所说，这个结论不一定成立。为了证明在每次迭代终都求得了最优解，我们需要使用归纳法（显然不是简单的证明）
- 最优子结构：求解的问题必须能划分为子问题，每个子问题都有最优解
设计思路
- 首先需要先联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大
- 尝试使用贪心算法解决问题：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据
- 举例子试验贪心算法的结果是否最优：简单列举验证即可
实现框架：
从问题的某一初始解出发
while(能朝给定总目标前进一步) {
利用可行的决策，求出可行解的一个解元素
}
由所有解元素组合成问题的一个可行解
经典问题
经典应用：
- 霍夫曼编码（Huffman Coding）
- Prim
- Kruskal 最小生成树算法
- Dijkstra 单源最短路径算法
霍夫曼编码
利用贪心算法来实现对数据压缩编码，有效节省数据存储空间。
| 字符 | 出现频率 | 编码 | 总二进制位数 |
|---|
| a | 450 | 1 | 450 |
| b | 350 | 01 | 700 |
| c | 90 | 001 | 270 |
| d | 60 | 0001 | 240 |
| e | 30 | 00001 | 150 |
| f | 20 | 00000 | 100 |
相关问题
- 简单题目
- 455 分发饼干
- 1005 K 次取反后最大化的数组和
- 860 柠檬水找零
- 中等题目
- 序列问题
- 贪心解决股票问题
- 122 买卖股票的最佳时机 II
- 714 买卖股票的最佳时机含手续费
- 两个维度权衡问题
- 有点难度
- 区间问题
- 55 跳跃游戏
- 45 跳跃游戏 II
- 452 用最少数量的箭引爆气球
- 435 无重叠区间
- 763 划分字母去区间
- 56 合并区间
- 53 最大子序和
- 134 加油站
- 968 监控二叉树
参考资料