贪心的两个特性
- 贪心选择
- 原问题的整体最优解可以通过一系列的局部最优的选择得到
- 应用同一规则，将原问题变为一个相似但规模更小的子问题，而后的每一步都是当前最佳的选择
- 这种选择依赖已作出的选择，不依赖于未作出的选择
- 运用贪心策略的程序运行时没有回溯的过程
- 最优子结构
- 当一个问题的最优解包含其子问题的最优解时，称此问题有最有子结构性质
- 这个性质决定了当前问题能否使用贪心策略
贪心算法秘籍
贪心策略 -》 局部最优解 -》 全局最优解
例题
- 2.2 27页
- 2.3 32页
- 2.4 37页
- 2.5 45页 最短路径
