算法浅谈——怪盗基德的珠宝选择问题与贪心算法

本文始发于个人公众号：TechFlow

1

在开始今天的文章之前，我们先来讲一个故事：

在一个月黑风高的夜晚，怪盗基德潜入了一个著名的珠宝会馆。他面前有三个装着珠宝的柜子，这三个规则分别是A、B和C。每个柜子里装了一个珠宝，这三个珠宝的体积分别是6，5，5，价值分别是10，5， 6。基德每次只能打开一个柜子，他需要将偷出来的珠宝放进随身携带的包里。他的包的体积是10，那么请问，基德应该采取什么策略呢？

图片说明

学过算法的同学会一眼就看出来，这是一个背包问题。

我们假装没学过，就按照常理来分析。显然ABC三个珠宝当中A珠宝是最值钱的，由于基德每次只能打开一个柜子，理论上来说应该先拿A。

但是如果拿了A，由于A的体积太大，那么就不能装下B或者C了。所以正确的答案是应该先拿C再拿B，这样能够拿到的价值是11，否则只能装下A一个，价值是10。

我们每次做决定的时候都选择当下回报最多的选项，这种算法叫做贪心法。就好像我们面临三个珠宝去选择最值钱的那个一样，但是当下回报最多并不代表最终的回报最多，所以我们不能只靠眼前的收益来决策。也就是说贪心法是会有反例的。

贪心法有反例这个结论并不难，很容易想明白，难的是我们如何判断当前的问题下，能不能使用贪心算法呢？尤其是我们可能一时半会想不出反例的情况下。

有一个比较取巧的方法叫做均等假设法，这个名字是我取的，没听说过很正常，不用纠结。事实上课本当中谈及贪心算法，也根本不会阐述这个问题，然而这个问题在实际当中又是非常重要的。均等假设法其实很简单，就是假设我们在某次决策的时候，面临两个势均力敌的选项，我们通过判断这两个选项最终的结果是否一致来判断贪心算法是否成立。如果两个均等的选项最终结果一致，那么贪心算法可行，否则不可行。

2

我们还用刚才基德的问题举例：

假设这次基德偷的不再是珠宝，而是非常昂贵的香水，并且假设香水混合之后不会影响它的价值。现在有ABC三瓶香水，每瓶的体积分别是6，5，5价值分别是10，5，5。而基德的瓶子体积是10，显然基德应该先装价值是10的A香水。当基德装完了A香水之后，瓶子体积还有剩余，这个时候他应该***香水呢还是C香水？

因为B和C香水的价值是一样的，我们试一下就知道，不论我们选B还是C都对最终的结果没有影响。也就是说这两个选项既是均等的，并且它的最终结果也是均等的。那么这个时候，我们就认为贪心算法是可行的。

上述的原理我想大家应该都能看明白，不过可能还会有人有这样一个疑问。我要判断两个选项最终的结果是否一样，既然都能做这样的判断了，那么显然应该早就知道贪心法可不可行了，这怎么还能称为是验证贪心法是否可行的方法呢？

答案也很简单，说起来我们是判断最终的结果是否一致，但实际上，我们只需要判断接下来的若干个中间结果，就可以判断最终结果了。最终结果的说法只是为了表述更加准确，毕竟这不是一个数学上严格的证明方法，而只是我们自己用来推测的方法。

3

我们再来看另一个例子：

柯南的学校最近有很多领导来视察，学校需要安排许多会议，但是学校只有一个会议室，老师们想要知道最多能安排多少会议。老师们为了这件事焦头烂额，只好请来了柯南帮忙。请问柯南应该用什么办法来计算呢？

图片说明

我们假设会议一共有n个，开始的时间是si，结束的时间是ei。我们用贪心算法来解，比较容易想到将所有的会议按照起始时间排序，假设我们按照开始时间排序，依次来安排。我们接下来用刚才的均等假设法来判断这个算法是否可行。

假设存在两个会议的开始时间一样，结束时间不同。那么在当前算法下，这两个会议是均等的。假设这两个会议一个是[1,3]，另一个是[1,4]。显然这两个选择的最终结果很有可能不同，因为如果出现一个会议是[3,4]。那么如果选择了第一个会议，就可以安排上，而选择第二个则不能。所以会影响最终结果，因此这种贪心策略不可行。

正解应该是按照结束时间排序，依次安排。我们同样用均等假设法来判断，假设存在两个会议的结束时间一样，并且都能够被安排，它们的时间分别是[2,3]和[1,3]。无论选择它们当中的哪一个，都会在3点结束，对于后面的安排不会产生影响。

你可能会问，如果存在一个[1,2]的会议会怎么样？其实可以证明，不存在这样的会议，因为如果存在，那么根据顺序，应该先安排[1,2]的会议。这样，2点之前开始的会议会被排除在外。那么这两个选项一开始就有一个不成立，自然也就不是均等的了。如果是均等的，那这样的会议就不会存在。

以上就是均等假设法。