贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。
适用范围：局部最优策略能导致产生全局最优解实际上贪心算法使用的情况比较少，可以先选择该问题下的几个实际数据进行分析可以做出判断
贪心选择：所求问题的整体最优解可以通过一系列局部最优的选择达到
采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题最优子结构：原问题的最优解包含的子问题的最优解，而这些子问题可以独立求解
证明：显然，贪心算法需要证明整体最优可以从局部最优得到
反证法：交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了
归纳法：先算得出边界情况（例如 $n=1$）的最优解 $F_1$ ，然后再证明：对于每个 $n$，$F_{n+1}$ 都可以由 $F_n$ 推导出结果。
基本步骤：
- 求解问题分解为若干子问题
- 从某个初始解出发
- 采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模
- 将所有解综合起来
实现框架
从问题的某一初始解出发；
while(能朝给定总目标前进一步){
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；贪心算法与动态规划的区别：
- 贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。
- 贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是
要点
常见题型
在提高组难度以下的题目中，最常见的贪心有两种。
- 「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。」。
- 「我们每次都取 XXX 中最大/小的东西，并更新 XXX。」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）
二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。
排序解法
用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。
后悔解法
思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。
