算法书上都没写，背包问题为什么不能用贪心法解？

作者 | 梁唐

大家好，我是梁唐。

上周我们一起聊了贪心法的原理，并且一起解析了两道例题。可能因为标题起的不好，很多小伙伴当成广告了。错过的小伙伴可以点一下下方的传送门，回顾一下上期的内容。

五分钟搞定贪心算法，从此不惧大厂面试

今天呢我们来聊一个在学习贪心法的时候一个非常经典的问题：如何判断贪心法有没有反例呢？很多时候我们想出了一个基于贪心法的思路，但是却无法判断这个方法究竟是不是可行，这个时候我们应该怎么办呢？这些内容算法书本上往往也都没有，需要读者自己通过一次又一次地刷题去领悟。

好在我已经把这其中的原理总结出来了，多少可以省去大家一些自己摸索的时间。

反例问题

首先，我们来看一个经典的问题，即背包问题。

当前有n个物品，每个物品有它自己的体积v_i 和价值p_i ，现在我们有一个最多能装V体积的背包。请问我们最多能够拿多少价值的物品？

一看问题，求最大价值，很多人第一反应就是贪心法。但很遗憾，这道问题不能使用贪心法求解。对于不能使用贪心法的原因，书本上往往是给出一个反例，你看这有一个明摆着的例子放在这里，贪心法不能解决，所以不能用。

这个反例很好找，比如说我们有三个物品，体积分别是1，2，3，价值分别是2.5，5，6，背包的体积是4。不论我们是体积最小优先还是单位价值比最大优先，最终选出来的物品都是1和2，这样策略的收益是7.5。但如果我们拿1和3，收益是8，要更高。

反例我们当然很容易就找出来了，但问题是，我们怎么知道是贪心法就不成立呢，还是说我们贪心的角度没对呢？在这个问题当中反例很明显，但有些问题则不是那么容易判断的。这个时候我们该怎么快速地给出结论呢？

关于这个问题，我当年acm队长的教练交给了我们一个原创的方法——均等假设法。实际上我也仅仅从学长的口中学到了这个方法，任何算法书上都没有提到过，绝对的核心知识。

均等假设

所谓均等假设法，很简单，就是我们根据贪心法的策略，假设两个不一样，但是在策略面前优先级相同的选择。然后根据选择之后的结果来判断，如果这两个选择不论选哪一种最后的结果都一样，那么贪心法可行。如果不同的选择会带来不同的结果，那么贪心法不可行，需要寻找其他的方法。

我们拿刚才讨论的背包问题为例，假设我们的贪心策略是最小体积优先。那很好办，我们假设两个物品体积都是1，但价格不同，显然拿A或者拿B是会影响最终结果的。所以这个策略是行不通的。

单位体积价值最大的策略可以用同样的方法迅速否定，比如一个物品体积是2，价值4，一个物品体积3，价值6。两个物品体积都不一样，选择明显会影响最终结果。

如果我们把题目当中的条件换一换，拿的不再是物品，而是香水，或者是黄沙。我们再套入均等假设法，就会发现当A和B性价比同为最高的时候，先选A还是先选B结果都一样。因为香水和黄沙都是可以拆分的，无论我们先拿了A还是先拿了B，只要还有容量，一定会拿另外一样，并且拿下来的价值不变。

比如我们先拿了A，背包还有空余，那么我们一定拿B。由于B是可以拆分的，所以不会存在拿不了的情况。且A和B性价比相同，所以两者谁被拆分都不会影响结果。既然不会影响最终结果，那么这道题就可以用贪心法来做了。

我们再回顾一下之前讲的例题——会议问题。

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

我们之前通过分析给出的策略是会议结束时间早的优先，我们同样采取均等假设法来判断一下。假设现在有两个会议都是10点结束，但是它们开始时间不同，一个是8点开始，一个是9点开始。

这个时候我们的选择会影响最终安排的会议数量吗？

答案是不会，因为不论选哪一个，下一个会议的开始时间都一定在10点之后，这个限制条件是不变的，那么最终的答案自然也不会变。有人会说不对啊，它们开始的时间不同，万一存在一个会是从8点开到9点的呢？

答案是不会出现这种情况，原因很简单，如果存在一个从8点开到9点的会议，由于我们贪心的策略是结束时间早的优先。那么这个9点结束的会议优先级一定高于10点结束的这两个会议，那么这个会一定优先安排了。一旦它被安排了，那么8点开到10点的会议就不能排了，也就没有和9点到10点的会议竞争的资格。

然而均等假设法的假设前提就是这两个选项是一样的，都是可选的，拥有竞争资格的。所以我们假设的前提就是包含了不会存在8点到9点这样的会议。

所以绕了这么一圈，我们还是可以下结论，采用均等假设法没有发现矛盾，说明这个贪心策略是可行的。

总结

贪心法和二分法一样，属于很直观一下就能学会的算法。但是算法简单不代表题目也简单，在竞赛和面试当中经常会遇到很多很难的贪心法的问题。

这些问题的难点有两个，一个是贪心策略不好找，另外一个就是有很多干扰项，有一些策略不可行，但是很难发现。

我这次写的两篇文章就分别针对这两个问题，上篇的文章讲的是如何寻找策略，这篇讲的是如何判断策略是否可行。不论大家是为了竞赛、保研还是为了面试，都希望能够给大家起到一点帮助。

最后，再多说一点注意事项。均等假设法并不是严格的数学证明，而是一种直观的判断方法。所以只能作为思考时的依据，而不能作为书面的证明，千万不要写在算法课的作业和考试里哦，不然一定是会扣分的。

祝大家端午快乐~