磨剑（5）运煤
Tags:
iq
——————— 好几年前写的东西了，朝花夕拾，略有删改。
问题
你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
分析
上学的时候也解过一个类似的问题，貌似是说派加油机给另一架运输机进行空中加油，既要保证加油机能顺利返航，又要保证给运输机加尽可能多的油……反正是一个规划类的智力题，具体不记得了。就运煤来说，先来一个简单的构想，以便我们打开思路：
- 先拉上1000吨煤，跑250公里，还剩750吨煤。扔下500吨煤，用剩下的250吨煤往回跑，回到矿区时刚好煤用光。 我们以500吨煤的代价将500吨煤运了250公里。
- 第二次同理，再将500吨煤运了250公里。
- 第三次有点特殊，我们不需要再回矿区了，所以到250公里处时，我们还有750吨煤。累计三次后，我们把1750吨煤运了250公里。照这个思路接着干。
- 同第1步，我们又拉1000吨煤跑250公里，扔500吨，再返回来。
- 回头拉剩下的750吨煤，跑到250里处还有500吨。这一轮结束后，我们还剩1000吨，距目标还有500公里。
- 拉上这1000吨煤到目的地，还剩500吨。
煤老板忽然阴森森地问，你这是最优解吗？ 心中一惊，一身冷汗。 如果这不是最优解，会怎么样？ 煤老板上边有人，下面也有人啊，我会不会有麻烦？ 要不要去柬埔寨避一避？
话说回来，死也要死得明白。 到底上面是不是最优解呢……我们来分析一下。
首先，有1000吨的煤损耗是铁定的，不然火车不可能从矿区跑到市场。 另外1500吨煤就有变数了，取决于我们的策略。然后来找一下煤损耗的规律。
第一轮中，我们损耗了1250吨煤。原因是我们在250公里的路上跑了五次，可以认为，每公里代价是5吨煤。 以此类推，我们第二轮每公里代价是3吨煤，最后一轮，每公里代价是1吨煤。 即5*250+3*250+1*500=2500。显然，往返运输次数越少，损耗越少。
所以，省煤的关键就在于：能两次运的，就不要分三次运；能一次运的，就不要两次运。
解法
第二轮开始时，前面的策略只剩下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吨煤，不少钱呢，能换一个漂亮老婆！昨天拿这个问题跟一个同事讨论了一下，争论了很久。比较感慨。 我比较喜欢以数学的思维来考虑问题。很多这类看似很麻烦的问题都有一个突破口，通常是某种形式的数学抽象，或者逻辑模型。 看清它的本质，问题就变得很简单。这也许就是很多聪明人的天份，与生俱来的一种对数学与逻辑的敏感，一种脑力的境界。
近年来，我发现自己在脑力上越来越有心无力了，记忆办衰退，一些小曲折小麻烦脑筋就经常转不过弯。真怀念当年那个聪明的小伙子啊。