贪心算法

贪心的两个特性

1. 贪心选择
   • 原问题的整体最优解可以通过一系列的局部最优的选择得到
   • 应用同一规则，将原问题变为一个相似但规模更小的子问题，而后的每一步都是当前最佳的选择
   • 这种选择依赖已作出的选择，不依赖于未作出的选择
   • 运用贪心策略的程序运行时没有回溯的过程
2. 最优子结构
   • 当一个问题的最优解包含其子问题的最优解时，称此问题有最有子结构性质
   • 这个性质决定了当前问题能否使用贪心策略

贪心算法秘籍

贪心策略 -》 局部最优解 -》 全局最优解

例题

1. 2.2 27页
2. 2.3 32页
3. 2.4 37页
4. 2.5 45页 最短路径