主要参考：
【百度文库PPT】贪心策略
【****】贪心策略的特点与应用

基本问题

使用贪心算法应注意 局部最优与全局最优的关系。这是贪心算法能够应用的一个十分重要的基础。

2个基本问题

应用贪心算法解决问题时，需注意两个问题：

1. 该题是否适用于使用贪心算法求解？
2. 如何选择贪心标准，以得到最优解/较优解？

举例:部分背包问题

• 【形式化】通过形式化定义，明确变量，目标，约束。但是并未给出从约束空间到达目标的方法，这就是我们需要做的，寻找到达目标的算法。

• 【形式化与程序 】形式化中的变量 对应 程序中的变量。约束对应程序中的 if语句。

  图1：引题
  

贪心算法 vs 动态规划

因为贪心算法与动态规划在很多场景下可以共同使用，两者有一些相同点及不同点，此处通过比较两者的区别联系，加深对于这两种算法的理解。（图2）

图2：对比贪心算法与动态规划

问题1：贪心算法适用场景

没有统一的判断标准，往往需要根据经验进行判断。

• 【局部最优与全局最优】由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，在广度优先搜索（BFS）中的解题过程亦可以满足局部最优解

图3：贪心求解问题的特点

局部最优 & 全局最优

贪心算法应该是可以通过局部最优达到全局最优目的的。但是，如何证明局部最优就能达到全局最优呢？(如何能够得到最优子结构呢？)

问题2：贪心策略

定义

图4：贪心策略的定义

贪心策略合理性证明

两种方法： 反证法，替换法
举例1：小生成树的prim算法贪心正确性的证明

寻找贪心策略的技巧

更新中 …