使用贪心选择策略，把一个复杂的问题，分解为一系列较为简单的局部最优选择，每一步选择都是对当前解的一个扩展，直到获得问题的完整解
3. 贪心法求解的问题特征最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质贪心选择性质：问题的全局最优解可以通过局部最优解得到，即存在要给最优解是以贪心选择开始的
（1）假设问题的一个整体最优解
（2）证明可以将这个整体最优解修改成从贪心选择开始，此时，原问题就简化成为一个相似的、规模较小的子问题
（3）用数学归纳法证明，通过每一步的贪心选择，最终可得到问题的整体最优解
4. 贪心法 vs 动态规划法
| 贪心法 | 动态规划 | |
|---|---|---|
| 相同点 | 最优子结构性质 | |
| 不同点 | 自顶向下求解，求解过程不依赖于子问题的解，仅在当前状态下做出最好选择，即局部最优选择 | 自底向上求解，求解过程依赖于子问题的解，在求出相关子问题的解后，再做出选择 |
| 最优子结构+贪心选择 | 最优子结构+重叠子问题 | |
（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合
（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合
（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款
（4）选择函数select：即贪心选择策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心选择策略就是在候选集合中选择面值最大的货币
（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款
