vlambda博客
学习文章列表

大家好，我是梁唐。

今天和大家聊聊贪心法，贪心法算是非常简单的算法，原理非常简单，和二分法一样，一两句话就可以说明白。

但是原理能说明白，不代表题目就做得出来，贪心法当中也有很多的门道。如果摸不着门道，可能即使明摆着告诉你这是贪心法，也未必能想出解法来。

今天我们先不搞这么硬核，先从最基础的开始讲起。

贪心法定义

讲算法自然离不开定义，我特地去维基百科搜了一下，贪心法的定义还挺复杂，一共总结出来了好几点。我贴一下给大家看看：

1. 创建数学模型来描述问题
2. 把求解的问题分成若干个子问题
3. 对每一个子问题求解，得到的子问题的局部最优解
4. 把子问题的局部最优解合成原来问题的一个解

你看，这个定义清晰完整，有头有尾，看起来颇有道理。但实际上，如果你真的按照这些点去分析会发现这背后有一系列问题，比如子问题是什么，如何把原问题分割成子问题。子问题的局部最优解怎么合成原问题的解，这样合成的解一定是最优的吗……

如果你愿意还可以继续这样套娃地问下去，保证越想越头大，越想离结果越远。

在我看来，贪心法其实很简单，某种程度上来说叫做直观算法比较合适。就好像数学里的很多公理一样，没有多余的解释，就直来直往。

举个例子，比如有一道著名的贪心例题叫做找零问题。也就是某个顾客去买东西，但是他没有零钱，已知商品的价格是x，请问找零的时候最少需要几张纸币（假设没有硬币）？

这个问题哪怕是去问小孩子，他们也能非常准确地告诉你，这题很简单，只要尽量找大面值的钞票就好了。但如果要去深究这里面什么是子问题，什么是子问题的最优解，可能大学生都不一定能答得上来。

所以过于钻研定义没啥意义，我们还是回到本心，按照直觉来，把它当成一种直觉驱动的算法。

找到核心值

既然贪心法可以理解成直觉法，并且大多数人也都是靠着直觉来做贪心的问题的，那么出题人在设计题目的时候，就一定会利用大家的这种心理，反其道而行之，让大家因为自己的直觉作茧自缚。

比如我们来看一道同样经典的会议问题：

你是某公司的秘书，需要给公司的一个会议室安排会议。现在已知当天有n个会议，以及这些会议的起始时间。请问在不做任何调整的情况下，最多能安排多少会议？

题目很简单，只有两三句话，一看就明白了。我们从直觉上来的话就是要安排尽可能多的会议，也就是说要把会议尽可能安排得紧密。但是道理都懂，怎样安排才可以保证紧密呢？

有人会想说可以优先考虑开会时间短的会议，但是深入一想很容易找到反例。比如A会议是9点到10点，B会议是10点到11点，而C会议是9点50到10点10分。如果优先安排C会议的话，会导致A和B两个会议都安排不了。

还有人会想说可以优先安排开始时间比较早的，这个反例就更明显了，假如有一个会议是从早6点到晚6点，那么当天就不要安排其他会议了，就这一个就占完了。

可能大家还会有一些其他的想法，但其中可能大部分都是错的。于是就会陷入一种想出方案然后推翻，再想出方案再推翻，想来想去也不知道正解在何方的感觉。就好像在大海上迷了方向，知道有出路，但是就是不知道出路在哪里。

那么出路究竟在哪里呢？

答案是在核心值上，贪心问题几乎都有一个核心值，所有的策略都是围绕这个值展开的。把握住了这个值，也就把握住了答案。

说来有些抽象，其实非常简单。还是看上面的例题，大家看到了会议要尽可能多，于是发散想到了安排紧凑、性价比等思路。但是从逻辑上来看，这样的发散其实是没有根据的，性价比高的方案不一定安排得就多，同样紧凑也一样，而且紧凑还有无法量化的问题。

但是如果冷静下来不做这些发散，其实很容易找到答案。这题的本质是安排会议，当前能安排会议的前提是之前的会议已经结束了。也就是说之前的会议没结束就不能安排新的，那么应该怎么做？很简单，优先安排结束得早的会议。会议结束得越早，越有可能安排尽可能多的会议。

所以我们按照会议结束的时间排序，然后在不冲突的前提下尽可能安排即可。

说穿了是不是非常简单？答案本身一文不值，之前的是推倒思考得到答案的过程。

最后，我们把难度提升，来看看在一些更加复杂的题意当中如何寻找核心量，从而解出问题。

练习题

我们接下来要看的就是经典的过河问题：

有n个人要过河，只有一条船，船上最多只能坐两人。

已知每人划船过河的速度不同，有的快有的慢。

当两个人在一艘船上时，过河所需要的时间为两人所需时间的最大值。在已知所有人划船过河所需时间的前提下，求最少需要多少时间能让所有人都过河？

我想大家可能都或多或少听说过这个问题，我们很容易可以想到由于只有一艘船，所以每次只能运一个人，必须还要一个人把船划回来。也就是说返程的时间是完全浪费的，那么我们肯定会想要尽量让划船速度快的人划回来。比如可以让划船速度最快的人当船夫，每次都由他把船划回来“载客”。

但是这样做也有问题，由于两个人同乘一船时按照两人所需时间的最大值来计算，那么速度快的船夫就不能发挥优势，从而浪费了很多时间。

接着可以想到，可以让划船速度最慢的两人同乘，因为每个人都是要至少过河一次的。让速度最慢的两人同行性价比最高，可以节省浪费……

同样，这样发散地想下去也没有止境，我们会想出各种各样的方案或者是点子，但就是串不起来构成完整的解法。这个时候就需要我们冷静下来，不要再发散去想了，而是要找一找核心量。在这个问题当中核心的量是什么呢？很明显，就是时间。

我们与其在这里空想，不如好好表示一下时间这个量，看看能不能有所发现。

我们先简化问题，从人数少的时候开始。n=1或2时非常显然，我们从n >= 3开始讨论。当n=3时，我们假设这三人分别是A、B、C，他们过河所需要的时间是a、b、c，其中a <= b <= c。

那么我们一开始的选择就有3种，分别是A + B、B + C、A + C（+表示两人同乘一船，A+B即A和B同乘一船）。

我们分开讨论，第一种A + B，然后A返回，接上C完成过河。所需要的时间是b + a + c。

第二种B + C，B返回，接上A完成过河，需要的时间为c + b + b=c + 2b。

第三种A + C，A返回，接上B完成过河，需要的时间为c + a + b。

对比了一下就发现第二种最慢，第一种和第三种是一样的。看起来这一通分析好像没有卵用，但实际上这背后藏着两条铁律。大家一时看不出来没有关系，我们先放一放，回头再说。

我们再来看看4个人时候的情况。假设这四个人分别是A、B、C、D，过河需要的时间是a、b、c、d，其中a <= b <= c <= d。

一开始的选择就多了，一共有6种。A + B, A + C, A + D, B + C, B + D, C + D。看起来很多，但实际上后三种可以直接排除。为什么？因为过去了还得回来，同样是运送一个人过去，为什么不选回来速度更快的A而要选B呢？

看不明白可以看下下面的示意：

如果选择了B+C

第一轮

此岸：A, D 对岸：B, C

B返回

此岸：A, B, D 对岸：C

如果选择了A+C

第一轮

此岸：B, D 对岸：A, C

A返回（肯定不能C返回，完全没有意义）

此岸：A, B, D 对岸：C

可以看到一轮过后选择A + C出发和选择B+C出发的结果一样，而A的返回速度更快，既然如此，为什么不选A + C呢？同理我们可以排除掉B + D以及C + D的情况。

所以我们只需要讨论的依然只有三种，不论怎么选，第一轮一定都是A回来。所以一轮过后此岸一定只剩下三个人，只有三种可能，分别是A + B + C， A + C + D和A + B + D。

眼尖的同学已经看出来了，此时此岸只剩下了三个人，按照我们刚才的分析只要不让两个慢的人同乘就是最优解。大家列一下就会发现，如果按照这样的策略，其实所有的选择得出的结果都是一样的，也就是A当司机，每次运送一个人。这样的结果是b + a + c + a + d = 2a + b + c + d。

这是一个定值啊，难道说我们分析了一圈下来发现最优解是固定的，就是选择最快的仔当司机吗？

当结论和直觉出现矛盾的时候，一定要冷静。冷静下来再好好分析，看看有没有什么遗漏的地方。

是的，这里有一个trick藏在了思维的盲点里。

之前我们讨论的3个人运输方案的时候有一个潜在的前提，那就是对面是没有人的。

但现在不同了，我们前面运输了一个回合，对岸有一个人已经在了，这个人也是可以开船的。所以回来的时候的选择增加了。

到这里好像仍然没什么用，依然有很多种可能的样子。但实际上仔细一想，会发现根本没有那么多可能，可能性是非常少的。在之前的分析当中，我们已经确定，第一轮一定是由速度最快的A运了一个人到了对岸。所以留在对岸的一定不是A，只可能是B、C、D中的一个。

我们假设是C，此岸剩下了A、B、D，那么第二轮到对岸的组合也就只有3种，分别是A+B、A+D以及B+D。这三种方案当中每一种都有一个速度比C快的人，完全没有任何必要让C开空船回来。

基于同样的道理，我们可以排除掉D留在对岸的情况，最有价值的情况只有一种，就是第一轮A+B将B送到对岸，然后第二轮C+D运送两个速度最慢的人过去，最后B开船回来带上A一起过河。

这样得到的结果是b + a + d + b + b = 3b + a + d，刚才A一直做司机的结果是2a + b + c + d。这两种方案哪个快？看不出来，消除一下共同项，最后的结果是要比较一下2b和a + c的大小，哪个小采取哪种方案。

n = 4解决了，n > 4的情况也是一样的，我们递推推导是不是就可以了？

我们再回过头来看看前面分析n=3的情况时提到的两个发现：

1. 第一轮一定是A + X的组合
2. 每一轮划空船回来的一定是对岸速度最快的人

我们刚才所有的推导，其实都是源于上面这两点。说隐蔽吧也不隐蔽，但想找出来也不是那么容易。如果一开始就能把这两点找到，那么这道题其实就很简单了。

好了，关于贪心法的解题思路，就分享到这里，下一篇我们来聊聊贪心法的证明。