1. 贪心算法简介
1.1 基本定义
在贪婪算法(greedy method) 中，我们要逐步构造一个全局最优解。每一步，我们都在一定的标准下，做出一个最优决策。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。做出决策所依据的标准称为贪心准则(greedy criterion)。
贪心算法每一步必须满足以下条件：
- 可行的：即必须满足问题的约束。
- 局部最优：即当前步骤中所有可行选择中最佳的局部选择。
- 不可更改：即局部最优选择一旦做出，在算法的后面步骤就不可改变了。
注意：贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
1.2 贪心算法基本思路
- 建立数学模型来描述问题。
- 把求解的问题分成若干个子问题。
- 对每一子问题求解，得到子问题的局部最优解。
- 把子问题的解局部最优解合成原来解问题的一个解。
2. 贪心算法最优性证明
2.1 贪心算法的前提
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
2.2 最优子结构
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。
2.3 贪心算法与动态规划的区别
- 贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。
- 贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。
- 能用贪心解决的问题，也可以用动态规划解决。
本文参考五大常用算法之一——贪心算法