2011年4月25日星期一

一道有趣的面试题 - 煤老板运煤

你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000 公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?

1 条评论:

  1. 上学的时候也解过一个类似的问题,貌似是说派加油机给另一架运输机进行空中加油,既要保证加油机能顺利返航,又要保证给运输机加尽可能多的油……反正是一个规划类的智力题,具体不记得了。

    就运煤来说,先来一个简单的构想,以便我们打开思路:

    1.先拉上1000吨煤,跑250公里,还剩750吨煤。扔下500吨煤,用剩下的250吨煤往回跑,回到矿区时刚好煤用光。
    我们以500吨煤的代价将500吨煤运了250公里。
    2.第二次同理,再将500吨煤运了250公里。
    3.第三次有点特殊,我们不需要再回矿区了,所以到250公里处时,我们还有750吨煤。

    累计三次后,我们把1750吨煤运了250公里。照这个思路接着干:

    4.同第1步,我们又拉1000吨煤跑250公里,扔500吨,再返回来。
    5.回头拉剩下的750吨煤,跑到250里处还有500吨。

    这一轮结束后,我们还剩1000吨,距目标还有500公里。

    6,拉上这1000吨煤到目的地,还剩500吨。

    目的达成,我们花了2500吨煤的代价,将500吨煤运送了1000公里……

    煤老板忽然不经意的问,你这是最优解吗?
    心中一惊,一身冷汗。
    如果这不是最优解,会怎么样?
    煤老板上边有人,下面也有人啊,我会不会有麻烦?
    要不要去柬埔寨避一避?

    话说回来,死也要死得明白。
    到底上面是不是最优解呢……来分析一下。
    首先,有1000吨的煤损耗是铁定的,不然火车不可能从矿区跑到市场。
    另外1500吨煤就有变数了,取决于我们的策略。

    首先来找一下煤损耗的规律。

    第一轮中,我们损耗了1250吨煤。原因是我们在250公里的路上跑了五次,可以认为,每公里代价是5吨煤。
    以此类推,我们第二轮每公里代价是3吨煤,最后一轮,每公里代价是1吨煤。
    即5*250+3*250+1*500=2500。显然,往返运输次数越少,损耗越少。
    所以,省煤的关键就在于,能两次运的,就不要分三次运;能一次运的,就不要两次运。
    第一轮,3000吨煤只能分三次运。没话说。
    第二轮开始时,前面的策略只剩下1750吨。实际上,2000吨煤我们就能两次运了。
    所以,第一轮不应该跑250公里,而是200公里。在200公里处,我们刚好剩2000吨煤,只需要分两次运输,每公里只损耗3吨。现在就开始省啦。
    同理,我们希望在煤还剩下1000吨的时候,就一次运输。
    所以第二轮应该跑1000/3 = 333+1/3公里。
    到此我们跑了(200+333+1/3)公里,车上还有1000吨煤。
    然后跑完剩下的路程,我们还有1000-(1000-(200+333+1/3))=533+1/3吨。

    33吨煤,不少钱呢,放我老家,能换一个漂亮老婆。
    算了,还是去柬埔寨避避。

    PS:昨天拿这个问题跟一个同事讨论了一下,争论了很久。比较感慨。
    我比较喜欢以数学的思维来考虑问题。很多这类看似很麻烦的问题都有一个突破口,通常是某种形式的数学抽象,或者逻辑模型。
    看清它的本质,问题就变得很简单。这也许就是很多聪明人的天份,与生俱来的一种对数学与逻辑的敏感,一种脑力的境界。

    近年来,我发现自己在脑力上越来越有心无力了,记忆办衰退,一些小曲折小麻烦脑筋就经常转不过弯。真怀念当年那个聪明的小伙子啊。
    好吧,我要努力的写这类的博客。

    别让脑袋生锈!

    回复删除