[TOC]

一、定义

贪心算法是从问题初始状态出发，通过若干次贪心的选择（每次取最多的果子，每次选最小的数字等），从而得到最优值（较优值）的一种算法。

简言之，贪心算法试图用不断寻找局部最优解来寻找整体最优解，并不是所有问题都可以通过贪心来取得，不过一部分特定的类型可以用贪心来求解。

【引例】在$N$行$M$列的正整数矩阵中，从每行选择一个数，使得选出的$N$个数的和最大。
解法：因要求所求的和最大，不难证明只要每行选择最大值可保证最终解为最优解。

二、特点

贪心算法的每一步必须满足以下条件：

可行性：该步必须满足问题的约束
最优性：该步是目前可选解中，相对最优的一步
无后效：该步不会影响之前的选择，也不会被之后的选择影响

三、简单实例

1.最优装载问题

给定 $n$ 个物体，第 $i$ 个物体重量为 $w_i$ ，选择尽量多的物体，使得总重量不超过 $C$ 。

分析：因为要求的是最多的物品数量，对于同一限载，易证选取较轻的物品可以装的更多，因而考虑优先选择重量较小的物品。【证明】

2.部分背包问题 *

有 $n$ 个物体，第 $i$ 个物体的重量为 $w_i$ ，价值为 $v_i$，在总重量不超过 $c$ 的情况下让总价值尽量高。每一个物体可以只取走一部分，价值和重量按比例计算。

分析：和普通背包问题不同的地方在于价值和重量按比例计算，这意味着不会存在空间浪费的问题，因而只要选出性价比最大的即可。【证明】

3.乘船问题

有 $n$ 个人，第 $i$ 个人的重量为 $w_i$ 。每艘船的载重量都为 $c$ ，最多可乘两个人。求用最少的船只装送所有人的方案。

分析：考虑对于最轻的人，为了尽量节省空间，应选择能载的最重的人配对，由于每个人都必须要过河，那对于最轻的人也无法匹配的的最重的人，只能单独乘坐一艘船。因而只需计算最轻的人与较重的人尽量能配对的对数，再加上不能配对的（太重的）人的个数即为答案。【证明】

4.非环形均分问题

一群人坐成一排，每个人手里有 $a_i$ 个糖果，每个人可以将手里一定数量的糖过传给身边的人，欲使每个人最终手里的糖的数量相等，问最少的传递次数。

分析：考虑最边上的人，他手里的糖有一个已经定下来的预期目标，因而对于他的操作，至少有一次，得到一定数量的糖或是给出一定数量的糖使得手里的糖数量成为平均数。

四、经典运用

1.选择不相交区间问题

给定 $n$ 个开区间 $（a_i, b_i）$ ，选择尽量多个区间，使得这些区间没有交点。

分析：若此时左端已选到 $s$ （开始为0），对于右端最靠左（且能选）的两个区间 $（a_i, b_i）$ 、$（a_j, b_j）$ , 有 $b_i < b_j$ ，则区间 $（a_i, b_i）$ 能比 $（a_j, b_j）$ ，给右侧最大的空间，因而应优先考虑区间 $（a_i, b_i）$。
所以，按照结束时间 $b_1 \leq b_2 \leq … \leq b_n$ 的顺序进行排序，依次考虑每个活动，如果没有和已经选择的活动冲突，就选。否则就不选。【证明】

2.区间选点问题

给定 $n$ 个闭区间 $[a_i, b_i]$ ,在数轴上选择尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。

分析：按照每个区间结束位置从小到大进行排序。然后按编号从小到大选择区间，优先选择当前区间的最后一个。【证明】

3.区间覆盖问题

给定 $n$ 个闭区间 $[a_i, b_i]$ ,选择尽量少的区间覆盖一条指定的线段区间 $[s, t]$。

分析：将所有的区间按左端点排序，依次处理每个区间。每次选择左端点在上一步已选范围内（接着上次继续覆盖），右端点尽量靠右的一个区间。【证明】

4.流水作业调度问题 *

有 $n$ 个作业要在两台机器 $M_1$ 和 $M_2$ 组成的流水线上完成加工。每个作业 $i$ 都必须先花时间 $a_i$ 在 $M_1$ 上加工，然后花时间 $b_i$ 在 $M_2$ 上加工。确定 $n$ 个作业的加工顺序，使得所有作业完成时间最短。

分析：.考虑最直观的情况，让 $M_1$ 没有空闲， $M_2$ 空闲的时间尽量的短。

$Johnson$ 算法：
设：
$N_1$ 为 $a < b$ 的作业的集合，按 $a$ 非减序排列
$N_2$ 为 $a \geq b $ 的作业的集合，按 $b$ 非増序排列
【证明】Ⅰ Ⅱ

五.小结

至此，贪心算法的总结完毕。然而，贪心并不仅仅是一道题，一个套路，一种算法。它是对于问题处理的一种思想，是对题目的一种思路。贪心的问题有无穷个，但只要我们掌握了真正的诀窍，又有何畏惧？

参考资料： [1]黄新军,董永健,赵国治,曹文,李健,董欣然.信息学奥赛一本通·提高篇[M].福建:福建教育出版社,2018.
[2]yanerhao.五大经典算法之四贪心算法 [CP/OL].https://blog.csdn.net/yanerhao/article/details/70162902 ,2017-04-13/2018-07-23.
[3]Will_Don .五大常用算法之三贪心算法[CP/OL].https://www.cnblogs.com/xsyfl/p/6938642.html ,2017-06-05 /2018-07-23 .
[4]周小博.浅谈信息学竞赛中的区间问题[DB/OL].https://wenku.baidu.com/view/7fcc174bc850ad02de80416b.html, 2010-12-25/2018-07-28.
[5]风仲达.0018算法笔记——【动态规划】流水作业调度问题与Johnson法则[DB/OL].https://blog.csdn.net/liufeng_king/article/details/8678316, 2013-03-15/2018-08-22.

算法Ⅰ 贪心