贪心算法
在对问题求解的时候，总是做出在当前看来最好的选择。也就是说，找出局部最优解。通过求局部最优解得到最终问题的答案。贪心策略的选择必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
贪心问题的解决步骤
- 当我们看到这些问题，首先联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选择几个数据，在满足限制值的情况下，期望值最大。
- 尝试看这个问题能否用贪心问题解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
贪心的正确性
数学上如何证明两个值相等， 等价于： $A \ge B$ && $A \le B$
经典问题
Huffman树问题
合并果子
用堆来维护所有的叶节点，一次pop两个，添加和
排序不等式
排队打水问题，按照时间从小到大排序
证明：调整法，假设最优解不是按照从小到大排好序的，通过调整可以减少等待时间，从而矛盾。
比较严谨的证明：
数学归纳法
反证法
绝对值不等式
货仓选择问题：放中位数
$f(x) = |x_1 - x| + |x_2 - x| + |x_3 - x| + … + |x_n - x|$
$f(x) = (|x_1 - x| + |x_n - x|) + (|x_2 - x| + |x_{n-1}) + …$
思想：分组（将前面的项与后面的项放在一起考虑） + 放缩
推公式
刷杂耍的牛：
分糖果问题
钱币找零
区间覆盖问题
相关题目
| 题目分类 | 题目名称 | 考察点 | 其他说明 |
|---|---|---|---|
| 股票买卖系列 | 仅买卖一次 | 贪心算法、股票买卖、定序、新的变量与最值 |
