贪心算法
七月在线 林应
2018 年 3 月
灯神说“你可以许 3 个愿望”…
主要内容
简介、思路和特性
实现要点
经典问题分析
作业
7 月在线求职面试 4 期
2/27
julyedu.com
简介、思路和特性
简介
贪心算法（又称贪婪算法）是指，在对问题求解
时，总是做出在当前看来是最好的选择。也就是
说，不从整体最优上加以考虑，他所做出的是在
某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，
关键是贪心策略的选择，选择的贪心策略必须具
备无后效性，即某个状态以前的过程不会影响以
后的状态，只与当前状态有关。
7 月在线求职面试 4 期
3/27
julyedu.com
简介、思路和特性
基本要素（关于最优解）
贪心选择：指所求问题的整体最优解可以通过一
系列局部最优的选择，即贪心选择来达到。这是
贪心算法可行的第一个基本要素，也是贪心算法
与动态规划算法的主要区别。贪心选择是采用从
顶向下、以迭代的方法做出相继选择，每做一次
贪心选择就将所求问题简化为一个规模更小的子
问题。对于一个具体问题，要确定它是否具有贪
心选择的性质，我们必须证明每一步所作的贪心
选择最终能得到问题的最优解。
7 月在线求职面试 4 期
4/27
julyedu.com
简介、思路和特性
基本要素（关于最优解）
最优子结构：当一个问题的最优解包含其子问题
的最优解时，称此问题具有最优子结构性质。运
用贪心策略在每一次转化时都取得了最优解。问
题的最优子结构性质是该问题可用贪心算法或动
态规划算法求解的关键特征。贪心算法的每一次
操作都对结果产生直接影响，而动态规划则不是。
贪心算法对每个子问题的解决方案都做出选择，
不能回退；动态规划则会根据以前的选择结果对
当前进行选择，有回退功能。
七月在线求职面试 4
期
5/27
julyedu.com
