贪心算法：
1.概念
贪心，贪婪
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法
2.应用场景
局部最优等同与全局最优解的时候
3.难点
理解概念和算法实现一般不困难，难的是贪心算法正确性的证明
例子1：找零钱问题
硬币系统：[25, 10, 1] - 贪心正确
硬币系统：[25, 10, 4] - 贪心错误（找8分：贪心4+4，最优4+4？等等，8分用两个4分就是最优）
更好的反例：[25, 10, 1] 找30分：贪心25+1+1+1+1+1，最优10+10+10
例子2：活动选择问题
按结束时间排序，每次选结束最早且不冲突的活动
证明需要：1) 存在最优解包含第一个活动 2) 子问题具有最优子结构
为什么证明这么难？
- 反直觉的陷阱
很多问题看起来可以用贪心，但实际上有反例：
部分背包问题：贪心正确
0-1背包问题：贪心错误
- 需要创造性思维
证明贪心正确性往往需要：
交换论证法
数学归纳法
反证法
- 问题依赖性强
每个问题的贪心策略和证明方法都不同，没有通用模板。
学习建议
- 从经典问题入手
先掌握这些经典的贪心问题及其证明：
哈夫曼编码
最小生成树（Prim/Kruskal）
最短路径（Dijkstra）
活动选择
- 培养证明思维
证明框架： - 证明贪心选择性质：存在最优解包含第一次贪心选择
- 证明最优子结构：剩余子问题的最优解 + 贪心选择 = 原问题最优解
- 多做练习，积累经验
尝试自己构造反例
学习标准问题的证明思路
理解不同证明技巧的适用场景
实际影响
这在面试和竞赛中很常见：
容易：想到贪心思路
困难：证明这个思路的正确性
关键：即使不能严格证明，也要能说明为什么这个策略合理
总结
贪心算法体现了计算机科学中一个普遍现象——提出启发式方法容易，但证明其最优性困难。这正说明了算法设计不仅是技巧，更是严谨的数学思维训练。
往往竞赛的时候，至少可以尝试使用贪心算法得到一部分的分数。
附录：
数学归纳法：高中数学阶段的一个证明技巧，观察，归纳，假设，递推关系推广
反证法：逆否命题的真值等价