老板运煤问题及解决方案

亦凉 2022-01-14 19:07 301阅读 0赞

最近在网上看到了老板运煤的问题，感觉挺有意思的。就把自己的想法写了出来，共大家参考，看大家有没有更好的解决思路。

问题是这样的：

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

由于火车一次最多只能运1000吨煤，而且每运一公里火车要消耗掉一吨煤，如果第一次运1000吨煤，运了1000公里，到了终点，火车的煤也消耗完了，显然这样是不行的，所以运到某一个位置要把煤卸载下来，然后回去再运剩下的，另外还要注意的是火车回去也要消耗煤的，这是一个反复的过程，关键是确定这个位置，另外还有一个最优的问题，也就是说火车每次运的时候都尽可能的运最多的煤。

假设火车第一次运1000吨煤，走了500公里，消耗了500吨，还剩下500吨煤，如果卸载一些煤下来，火车就回不去了，如果不卸载，刚好能回到出发点，因为回去毕竟也要消耗掉500吨煤，这样根本就运不到煤，所以火车第一次卸载的煤的地点距离出发点一定要少于500公里。

如果火车第一次运1000吨煤，走了250公里，卸载了500吨煤，这样刚好能回去运剩下的，同样第二次也卸载了500吨，由于第三次不用回去了，所以运到250公里的时候火车上还有1000-250=750吨煤，加上前两次卸载的煤

那么第一次卸载煤的地点如何确定呢，考虑到最优化策略，假设距离出发点X公里的地点开始卸载煤，那么一次卸载煤为 1000-2X，同理第二次卸载煤也为1000-2X，那么第三次运到X公里处火车上煤为1000-X,那么到此所有剩下的煤为1000-2X+1000-2X+1000-X=3000-5X,考虑到最优化策略，3000-5X应该是1000的整数倍，这样才能达到火车每次都运做多的煤，

显然应是2倍，即3000-5X=2000 ,所以X=200公里，这是剩下的煤为2000吨。那么剩下的就是把这2000吨煤再运800公里就到了目的地。同理假设再运1000吨煤到Y公里处开始卸载煤，那么有1000-2Y+1000-Y=1000,那么Y =1000/3公里，剩下煤1000吨，剩下的距离为1000-200-1000/3=466.66...公里，那么最终到目的地剩下的煤为1000-466.666=533.33吨。

因此步骤应该是：

首先运到200米处，剩2000吨煤  
再次运到1000/3米处，剩1000吨煤  
最后运到目的地，剩533.333吨煤

对于这一类问题，如果是4000吨煤呢？如何

第一次卸载煤X公里，则 1000-2X+1000-2X+1000-2X+1000-X=4000-7X=3000(为什么是3000呢，根据最优化策略，应该是1000的整数倍，最大取3000)，那么X=1000/7公里，也就是剩下3000吨煤。

第二次卸载煤再往前走Y公里，则1000-2Y+1000-2Y+1000-Y=2000 ,则Y=200公里，剩下2000吨煤，

第三次卸载煤再往前走Z公里，则1000-2Z+1000-Z=1000,则Z=1000/3公里，剩下1000吨煤，那么剩下的路程呢，为1000-1000/7-200=4600/7公里，

那么到目的地剩下的煤为1000-4600/7=2400/7吨