面试题：火车运煤问题
这个可能是一个比较经典的智力题了，和以前的那个《赛马问题》很相似，其题目如下：
你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
这道题一开始看上去好像是无解的，因为你的火车每一公里就要消耗一吨煤，而到目的地有1000公里，而火车最多只能装1000吨媒。如果你的火车可以全部装下，到目的地也会被全部烧光，一丁点也不剩。所以，很多人的第一反应都是觉得这个不太可能。
如果你一开始就觉得不太可能的话，这是很正常的。不过我不知道你还会不会继续思考下去，如果你不想思考下去了，那么我很为你担忧，因为你可能并不是一个不善于思考的人，而是一个畏难的人，还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。
我一开始也觉得不可能，后来想了一想，想到一个解法可以最多运送500吨煤到市场，方法如下：（希望你先自己想一想再查看这个答案）
【查看答案】
好像这样很不错的了，不过还有更好的方法能运更多的媒过去。你知道这个方法吗？可以提示的是，就是以上述这个方法的思路。我先暂时不把答案放上来，你可以自己想想。过两天我把答案放上来。
更新（2011年4月17日）：大家都很聪明，533是应该是最优解，大家用了很多种方法阐述了这一过程，我最初的想法和朋友xPacificCoolShell的一致！很高兴看到有更为科学的解法，受教了。另外，还有一些朋友提出火车不能随时随地调头的实际情况，非常不错，所以，以后这题不能用火车运煤了，可能是用马运草更好一点了。;)
（转载本站文章请注明作者和出处 酷 壳 – CoolShell ，请勿用于任何商业用途）
(50 人打了分，平均分： 4.52 )
Loading...
《面试题：火车运煤问题》的相关评论
呵呵。想看答案呢。
哎呀，这个一看就跟微软那个飞机围绕地球飞是一样类型的题目～
每次运一千吨，分3次，前2次都到666.66667公里处卸煤，第3次到原先卸下处装上666.66667吨，这时火车上共有1000吨，路程还有333.33333公里。
很明显，到目的地后还有1000-333.333333=666.666667吨煤。
不好意思，算错了，没有考虑回程。
1.装1000T，走1KM，用掉1T，卸下998T，留1T回去；回去后再装1000T，走1KM，用掉1T，卸下998T，留1T回去；回去后再装最后1000T，走1KM，用掉1T，这次不用回去；由此可以看出，可以用2+2+1=5T的代价前进1KM；
2.用上述方法向前走了200KM后，用掉了1000T，现在只剩2000T；
3.后面仍然按上面的方法，不过这次只需要运2000T，代价也就减少到2+1=3T了，一直这样向前走，直到最后剩下1000T；也就是用1000T来前进，可以前进1000/3=333KM；
4.此时剩下1000T，共前进了200+333=533KM，还剩下467KM；一次运过去，用掉467T，剩下1000-467=533T；
最优化问题啊，牛人太多了
@eagle
我的答案是1000/3吨，设立两个节点，把路程分成三段！！
没有看别人的答案，最后我是这样解的：
因为运煤的来回都会有消耗，假设剩余煤量是M，一共有多种可采纳的消耗方式，假设前进x公里
当2000<M<3000时，5次的方式可以保证把所有的煤地往前运
当1000<M<2000时，3次的方式可以保证把所有的煤地往前运
当0<M<1000时，1次的方式可以保把所有的煤尽量地往前运
所以第1点是(M-2000)/5 = 200，第二个点是1000/3, 最后剩余1000顿煤 和 还需要走(1000 – 200 – 1000/3)公里,200+1000/3也就是剩余煤量
最后可以有归纳法拓展一下:
比如3000<M<4000,最开始需要用7次的方式来运，然后5次，3次，1次，
最多能运(M-3000)/7+1000/5+1000/3
比如4000<M<5000,最开始需要用9次的方式来运，然后7次，5次，3次，1次,
最多能运(M-4000)/9 + 1000/7 + 1000/5 + 1000/3
@小谢
我的是错误的！对不起了
正解！赞@庞华林
个人觉得最佳答案是:2/3 * 1000 = 666.67
用3个火车运 到2/3的位置其中两个把煤全给另外一个.
因为题目没有给出火车要返回和铁路只有一个条的约束
@wader
可是火车只有一个
我还是太年轻了……考虑不周
不知道
哈~~~水题，先运1000吨距出发地250公里的位置，放下500吨，则车上还有250吨，刚好能回到出发地，回到出发地后再运1000吨出发，到距出发地500公里时，放下250吨，则车上还有250吨，回走到距出发地250公里的位置（因刚在这放下了500吨，现在往车上加煤250则可回到出发地）加煤，此时这个位置还有250吨煤，车回到出发地，最后运1000吨煤，到距出发地250公里时加煤剩下的250吨，（车花费了250吨）刚好又是1000吨煤，到距出发地500公里时加煤250吨，车上还有1000吨，走完剩下的500公里花费500吨，则最后送达目的地的是1000-500=500
@情定星海
同意，正解
最佳是2000/3
分三批次到1000/6处，再分两批次到1000/6+500处
最后一次到达目的地
帅气的解法，不过不详细~@庞华林
想到了卸装煤 想到了 到400KM卸200吨煤，结果不成立。惭愧。。
我想到的也是卸煤，不过没算出最优解。不过为什么空载和满载消耗会是一样呢？这肯定不符合常理啊。
傻啊，换个火车啊，或者叫买家自己来运！哈哈，看大家解得这么开心，开开玩笑
T _ T 算了半天 还是没有头绪
初始是3000，运3次，
第一次消耗1000，到点333
第二次消耗1000，到点500+333=833
第三次消耗267，到终点，
一共运回733顿。
没算回程的消耗，其实思路应该是一致的，
前两次的耗煤量*2,到最后1000的时候直接拉到终点
1，1000/6=167
2, 1000/4=250
3, 1000-167-250= 583
@神奇之光
又漏了，不是双倍消耗，是双倍-1
1，1000/5=200
2, 1000/3=333
3, 结果应该是533
用数学表达
1000-x x
|————————————|————-|
start 临界点 end
假设: a、临界点(能一次性运完的点)卸下来的煤的总数为：count
b、最后能剩余的煤为surplus
c、分n次到达临界点
1、(1000-x) * n = 3000 – count
2、count <= 1000
3、surplus = count – x
感觉靠自己主观推断3次运送，并且假设临界点是卸下来的煤是1000，毫无意义。我相信还是用数学公式计算下吧。最好能用程序表达出来
我的想法是利益最大化
第一次到1/3处，放下333t，然后第二次运行到这里时，还有1000t
然后设此点为A点，到达的距离为B点，这个距离为x
x要满足
1、留下的煤最多同时火车能回到起点
2、第三次火车到这里时 正好装满火车上的剩余空间
1000-（x+333+x） = (x+333)
x = 111
第二次火车运行到444处，放下445
最后一次运行445公里，正好到此处全部装上，最后到达目的地剩余445
但这个和一般的解法500km还是更多的533解法差距都很大
但感觉思路还是挺正确的 不知道哪里有问题
这道题其实高中的线性规划知识就可以解决。
不难想出火车要走完1000km，最多会经历三个阶段：
|____________|______________|________________|
起点 A B C（终点）
1.从起点开始，分3次把3000吨煤拉到A点，路程为5a；
2.从A点开始，分2次把剩下的煤拉到B点，路程为3b；
3.从B点开始，1次把剩下的煤拉到终点，路程为c。
所有消耗的煤的数量为t = 5a + 3b + c，由于煤的总数是一定的，所以我们要求的也就是t最小。
目标：min t = 5a + 3b +c
条件：
a + b + c =1000
5a + d + c <= 3000 (来来回回消耗的煤不能大于3000)
3000 – 5a <= 2000 (到达A点时，煤的数量不能超过2000，否则不可能分两次拉完)
3000 – 5a – 3b <= 1000 (到达B点时，煤的数量不能超过1000，否则不可能一次拉完)
看似是三元一次方程组，其实c可以用a b表示 (c = 1000 – a – b)。然后在坐标系中，用高中的线性规划知识即可求出t的最小值以及此时的a、b、c， 然后3000 – t = 533 就是煤最大的运送量。
（上一条有个地方错了，重新贴一下）
这道题其实高中的线性规划知识就可以解决。
不难想出火车要走完1000km，最多会经历三个阶段：
|____________|______________|________________|
起点 A B C（终点）
1.从起点开始，分3次把3000吨煤拉到A点，路程为5a；
2.从A点开始，分2次把剩下的煤拉到B点，路程为3b；
3.从B点开始，1次把剩下的煤拉到终点，路程为c。
所有消耗的煤的数量为t = 5a + 3b + c，由于煤的总数是一定的，所以我们要求的也就是t最小。
目标：min t = 5a + 3b +c
条件：
a + b + c =1000
5a + 3b + c <= 3000 (来来回回消耗的煤不能大于3000)
3000 – 5a <= 2000 (到达A点时，煤的数量不能超过2000，否则不可能分两次拉完)
3000 – 5a – 3b <= 1000 (到达B点时，煤的数量不能超过1000，否则不可能一次拉完)
看似是三元一次方程组，其实c可以用a b表示 (c = 1000 – a – b)。然后在坐标系中，用高中的线性规划知识即可求出t的最小值以及此时的a、b、c， 然后3000 – t = 533 就是煤最大的运送量。
@gock
请问为什么最多会是3个阶段呢？这个是如何求出来的？理由是？
这个问题，首先要考虑什么情况才是最优情况。依照题意，火车只要活动就会消耗煤，所以每次火车出发时只有满载才是最优情况，并且不能扔掉煤不要。有了这个前提，我们接着往下分析。
求得最优解的过程肯定要减少火车折返的所消耗的总路程。由于全长1000公里，所以我们肯定需要采用多次中转的方式来运送，中转的过程中随着煤的消耗，折返的次数也会减少，所以我们要尽量减少多次折返时所前进的距离。
只有一辆火车，每次出发都是满载，那么我们需要3次将煤运送到下一站，在此期间需要折返5次。下一站出发如果要满足最优条件，则此期间需要消耗掉一车或者两车煤，根据第二段的分析，我们应该减少5次折返时所前进的距离，故此次运送需要消耗1车煤。1000/5 = 200公里。依次类推，第二次运送折返3次，需要消耗1车煤，前进距离为1000/3 = 333.33……公里。第三次由于仅剩一车煤，满载前进，出去路途消耗，到达终点剩余煤为1000-(1000-(200+333.33) = 533.3333吨。
@wader
老大，自己好好想想吧。
把所有煤运到100公里处，需要三趟，往返5次，消耗500吨，还剩2500，同理运到200公里处剩2000吨，运到300公里处剩1700,400公里处剩1400,500公里处剩1100；还有1100吨煤，500公里路，100吨送人不要了，拉上1000吨到市场还剩500吨
第五站若保证剩1000吨煤可以定在533.333333公里处，这样最终运过去1000 – (1000 – 533.333) = 533.33333吨
。。。不太懂这和编程有什么关系。貌似和数学关系较大
应该用到动态规划吧，求最优解，只简单列得出方程，不懂解~~！
先解决运500吨过去的方案。考虑路中只设置一个转运点，可以设为距起点x km.则有3000-5x-(1000-x)=500.解得X=375,即在距起始出发点375km处设置一个转运点。同理，要保证火车最后运输煤的量最大，则要分3个转运点运输。为什么这是最优的方案呢？因为分为两个转运点最多能运500吨煤，而分成4个或者4个以上就会增加火车往返的次数，况且只有3000吨煤（如果多一些煤还可以考虑），所以为了保证每次往返只消耗一车煤，则第一个转运点应该设置在1000/5=200 km处，第二个转运点应该设置在200+1000/3=533.33km处，所以最终能运到目的地的煤为1000-（1000-200-1000/3）=533.33吨，取整数为533吨。
maximum [(a+b,a,b)|a<-[200..400],b<-[0..500],2000-5*a-3*b==0] haskell
车算整数的时候532
maximum [(a+b,a,b)|a<-[200,200.4..400],b<-[0,0.4..500],let p = 2000-5*a-3*b in p<1 && 0<p]
来点有浮点的
maximum [a+(2000-5*a)/3|a<-[200..400]] 更快的版本
始发站有3000吨煤，每次只能装1000，所以，将所有的煤运离始发站，火车要走5次同样的路程
这就意味着，我们将所有的煤向前推动1公里，就要消耗5吨煤
因为我们要装三次车，每次装1000吨
问题是我们这次向前推进多少合适
我们第二次向前推进时，还要装车，也许还会有第三次，直到我们只剩下1000吨煤为止，我们才一直驶向终点站
那么，这就意味着，我们每次装车都应该装1000吨煤，否则，就是在浪费运力
所以，我们第一次应该向前推进200公里，这样，我们剩下2000吨，才能保证每次装车可以装1000吨煤，使得运力最大化
那么我们这次每向前推进1公里，就只要消耗3吨煤
如此，我们有1000吨煤可以消耗
也就是说可以向前推进三分之一千米
这意味着我们要用剩下的1000吨煤跑完最后的（800-1000/3）公里的路程
那么最后剩下533.3333吨煤
就这种试题来说，
最多运到目的地的 ((n-1)/(n+1))*每次可运量， n等于 总的待运量/每次可运量
就本体来讲 n=3 运到目的地的最大值为（1/2）*1000 = 500
第一个333公里消耗1000，折返3次，运煤2000
第二个333公里消耗1000，折返3次，运煤1000
第三个333公里消耗333，折返1次，运煤667
这个思路最清晰，顶一个!
因为我们不知道要运多少次才能最节省，说3次的只不过是根据经验判断的而已，如果煤炭数、公里数、运载量分别为a、b、c的话，就无法这样判断了。
我觉得应该这样来算，假设我们有很多火车，那么用到的火车数就是a/c，有余数的话，需要进位计算，而由于需要返程，我们需要另外的a/c-1辆火车的跟随。
这样，除最后一次消耗的煤炭量是a/c外，前面每公里消耗的煤炭量就是2*a/c-1，a/c有余数的话，需要进位计算。
而我们可以根据a/c的数值，进行分段计算，前面每段的距离为c/（2*a/c-1）,每段消耗的煤炭数为c。最后一段消耗量为a/c*(b-前面每段的距离)。
比如本题，开始的时候a/c=3，那么就分3段，消耗的总煤量为1000+1000+1*(1000-1000/(2*3000/1000-1)-1000/(2*2000/1000-1))=2466.667吨，剩余533.333吨。
根据上面的分析，写程序计算的话，也就很好设计了。