面试题：火车运煤问题
这个可能是一个比较经典的智力题了，和以前的那个《赛马问题》很相似，其题目如下：
你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
这道题一开始看上去好像是无解的，因为你的火车每一公里就要消耗一吨煤，而到目的地有1000公里，而火车最多只能装1000吨媒。如果你的火车可以全部装下，到目的地也会被全部烧光，一丁点也不剩。所以，很多人的第一反应都是觉得这个不太可能。
如果你一开始就觉得不太可能的话，这是很正常的。不过我不知道你还会不会继续思考下去，如果你不想思考下去了，那么我很为你担忧，因为你可能并不是一个不善于思考的人，而是一个畏难的人，还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。
我一开始也觉得不可能，后来想了一想，想到一个解法可以最多运送500吨煤到市场，方法如下：（希望你先自己想一想再查看这个答案）
【查看答案】
好像这样很不错的了，不过还有更好的方法能运更多的媒过去。你知道这个方法吗？可以提示的是，就是以上述这个方法的思路。我先暂时不把答案放上来，你可以自己想想。过两天我把答案放上来。
更新（2011年4月17日）：大家都很聪明，533是应该是最优解，大家用了很多种方法阐述了这一过程，我最初的想法和朋友xPacificCoolShell的一致！很高兴看到有更为科学的解法，受教了。另外，还有一些朋友提出火车不能随时随地调头的实际情况，非常不错，所以，以后这题不能用火车运煤了，可能是用马运草更好一点了。;)
（转载本站文章请注明作者和出处 酷 壳 – CoolShell ，请勿用于任何商业用途）
(51 人打了分，平均分： 4.45 )
Loading...
《面试题：火车运煤问题》的相关评论
假设两点A和Z距离3000km。先逆向思维，最后存在离终点最近的一点，此刻剩余煤量最多，为1000t。再正向思维，在(2000t,3000t]范围内，火车往返总共5n次，最少5次；同理在(1000t,2000t]范围内，往返3m次，最少3次；最后1000t需1次。那么肯定存在两个中间点2000t处，1000t处。假设2000t处为B，1000t处为Y，那么AB中间总共消耗1000t，BY之间总共消耗1000t，按往返次数最少可得：5AB=1000t,3BY=1000t,AB+BY+YZ=1000km，1000t-YZ=？
错了 应该是444，第三次就不回去了
我的解法可以剩533吨。
0-533公里内，每次搬一公里。
第一阶段，0-200公里，每公里去3趟，回2趟，消耗5吨，到第200公里剩2000吨；
第二阶段，200-533公里，每公里去2趟，回1趟，消耗3吨，到第533公里剩1001吨；
最后，装上剩下的1000吨（丢掉1吨），直接开往终点，消耗467吨；最后剩533吨。
@zturn
作为煤老板的我聘请你去替我运煤，我还是当煤老板
使用极限求值，应该可以求到最优点。
但是，装卸的成本就没考虑啦。作为这样一个煤老板，我觉得这次生意肯定黄了。赔大了。
第一次载上1000吨煤到200处，卸下600吨，回来，煤耗光
再次载上1000吨，如上步骤
第三次将最后的1000吨煤载上，到达200处，此时消耗200吨煤，目前200处煤有2000吨
载上1000吨煤，开到1000/3+200处，卸下1000-2000/3吨煤，再返回200处，载上剩下的1000吨煤到1000/3+200处，此时总共有1000(1000-2000/3+1000-1000/3)吨煤
剩下路程为800-1000/3，则最终剩下的煤为200+1000/3约等于533.333…
只说了答案，解题方式呢？应该有算式把，不然拼什么说是最优的
4/9 t
@Mr. Nobody
虽然没看懂，但觉得没有可操作性，因为车调头的次数太多了，作为煤老板，应该考虑司机的感受
@coyzjc
第三次将最后的1000吨煤载上，到达200处，此时消耗200吨煤，目前200处煤有2000吨
（这里应该是1200吨吧）
思路:
1.确定到底要运几次.
3次.推理过程略去。
所以包括往返两次和第三次直接到目的地。
2.确定每次火车的出发和返回的状态和目的：
2.1第一次出发满载1000，返回不剩煤。设第一次出发到达的地点距离起点x公里，目的：在路上留下头两次往返和第三次经过时足够支持火车走这段x公里的煤，所以5x=1000，x=200
2.2第二次出发满载1000，返回不剩煤。设第二次出发到达的地点距离起点x+y公里,目的：在路上留下第二次往返和第三次经过时足够支持火车走这段y公里的煤, 所以3y=1000，y约等于333
2.3第三次出发满载1000，直接到目的地。前200+333公里消耗的煤都补充上了，就是可以带到目的地的煤了，533。
至于沿途放的煤，每次放的总量确定了，放的方法很多啊。
不说别的.看第二步:”2 装1000吨煤，走到250公里处，拿起250吨煤继续向前到500公里处，扔下500吨煤，回矿山。此时火车上还有250吨，再加上在250公里处还有250吨煤，所以，火车是可以回矿山的。”
这个就有问题啊. 首先” 装1000吨煤，走到250公里处 ” 这时车上还有750吨–> “拿起250吨煤” 这时车上有1000吨–>”继续向前到500公里处” 走了250公里,车上又只有750吨了–>”扔下500吨煤，回矿山。此时火车上还有250吨” 这个没错–>”再加上在250公里处还有250吨煤”这个哪来的啊.来的路上不是已经让你拿起了吗?–>”所以，火车是可以回矿山的” 所以,你是回不去的.!!!
最好应该能送到600.路上还有100留着.
能耗问题，天气问题，装卸货问题，往返时间问题，是我，这单生意我然给你做，这是哪门子智力 ，难怪人说理科生智障的多
很无聊的问题，就像进水管出水管同时打开问多久灌满一样无聊！
533 好像是微软的一个面试题，算600的那个能不能讲出你的思路？
拿1000吨，到200公里点，放下600吨，车上200吨煤。
返回原点。
现在车上0吨煤，原点2000吨煤，200公里点600吨煤。
拿600吨，到200公里点，拿起400吨，车上800吨煤。
到400公里点，放下400吨，车上200吨煤。
返回200公里点，拿起200吨，车上200吨煤。
返回原点。
现在车上0吨煤，原点1400吨煤，200公里点0吨煤，400公里点400吨煤。
拿600吨，到200公里点，放下200吨，车上200吨煤。
返回原点。
现在车上0吨煤，原点800吨煤，200公里点200吨煤，400公里点400吨煤。
拿800吨，到200公里点，拿起200吨，车上800吨煤。
到400公里点，拿起400吨，车上1000吨煤。
到终点，车上600吨煤。
到400公里点，拿起400吨，车上1000吨煤。
到终点，车上600吨煤。—>这。。。1000-600=600？
哈哈
3000吨煤如果运出的话，火车最多只能装1000吨煤，所以至少需要三次。在经过第一次运输后，在第一个卸载点所剩的媒>=2000,<3000，所以第二次运输的话运输2或3次，如果三次的话最后一次运输<1000,没有达到火车装煤的极限，所以在第一个卸载点最后只剩2000吨煤，此地点应该距原始点（3000-2000）/(2+2+1) =200公里处。剩下距终点还有800公里，火车还不能一次运到。假设下一个卸载点距第一个卸载点y公里，那么在第二个卸载点剩余煤应为(2000-3y)<2000,分析同一个卸载点，第二卸载点应该剩余煤1000吨，2000-3y=1000，y=333.33….。所以到终点剩余最多没煤为1000-（1000-200-333.333）=533.333。
你们知道什么是火车吗？还可以随意掉头？！铁轨啊！铁轨！！不到站掉不了头的！！我没看答案想了半天啊啊！！原来是掉头这招！！！
别太在意了。想不到 也不能证明什么。
此类题的 目的是
检验你的思维能力如何。碰到问题敢不敢想。楼主也说了。
纠结就米意思了对吧。
在这个路程上逻辑设置多个火车站：在每站上都可以放煤取煤，这样就演变为类似编程解汉诺塔的问题了。用图的数据结构+递归就可以解出多少个火车站以及分布是合理的了。
啊？算了不是理想结果呀
只知道去时在路上捡了，回来就没捡，哎呀，笨蛋，呵呵
这道题应该是逆推吧 发表一下我的拙见。
终点D，中间点C，中间点B，起点A。
首先为了满足火车运到某个中间点可以卸下一定量的煤并返回，应保证每次运输的距离小于500，这样起点和终点直接至少存在2个中间点。
为了减少煤的损耗，每次运输时应满载，故在C点应有1000吨煤，而为了让C点有1000吨煤，需要火车从B点到C点走3次（2次去，一次回）。而B点储存的煤应该是1000的2倍，所以从B运到C共损失1000吨煤，BC=1000/3；
为了使B点储存2000吨煤，需要从A点到B点往返5次（3次去，2次回），A点有3000吨煤，从A到B损失1000吨煤，则AB=1000/5；
AB=200;BC=333.33333;那么CD=1000-AB-BC=466.6666；
所以最终剩余1000-CD=533.3333吨煤
你这个思路一看就有问题的。应该是时刻保持火车最大装载量，可是你一开始就不让火车装满，肯定效率低的@路人
这个应该是最优思路了吧 @123048591
一公里一公里的向前移动
在3000 – 2000 时，每向前一公里，需要来回移动5次，故在这个时段每公里耗费5吨煤
在2000 – 1000 时，每向前一公里，需要来回移动3次，每公里耗费3吨煤
在1000 – 0 时，每公里1吨煤
所以结果如下：
剩下的煤 已经走了的公里数
3000 : 0
2000 : (1000/5) = 200
1001 : 200 + (1000/3) = 533
最后在走了533公里的时候，火车上还可以有1001吨，但是零下的一吨是带不走的
所以最后应该是 1000吨 – （1000公里 – 533公里）* 1吨每公里 = 533吨
/**
* @param m the total weight of coal
* @param n the capacity of train or the miles count of distance
* @return the weight of the left coal mine
*/
public static int resolve(int m, int n){
int milesLeft = n;
int capacity = n;
int coalLeft = m;
int backAndForthCount = coalLeft / milesLeft + (((coalLeft % milesLeft) > 0) ? 1 : 0 );
int backAndForthTimes = 2 * backAndForthCount – 1;
while(backAndForthTimes > 1){
// 每次向前走一公里耗费的煤
int costPerMile = backAndForthTimes;
int milesToBeMoved = n / costPerMile;
coalLeft -= milesToBeMoved * costPerMile;
milesLeft -= milesToBeMoved;
backAndForthCount–;
backAndForthTimes = 2 * backAndForthCount – 1;
}
return capacity – milesLeft;
}
public static void main(String[] args) {
int miles = 3000;
int capacity = 1000;
System.out.printf(“there are totally %d ton(s) of coal left”, resolve(miles, capacity));
}
应该是533.333吧。
1、第一次中点站应该下一次为2000t最好，所以为1000=5x，x=200；
2、第二个中点站应该等下次只剩下1000t的时候最优，1000=3y,y=333.33;
3、最后剩下的1000直接走完剩下的路，1000-（1000-x-y）。
最后得533.33.
@您这个不对啊.
250公里处第一次留了500 拿走250 还剩250
煤老板表示火车不用烧煤,拉着走就可以~
类似于小学生条件局限的数学题，首先没有给出空车能耗，最优载重量，以及超过最优载重能耗是正比增长，还是成指数增长，还有看了大概看了楼上的，切不说超过最优是否成能耗指数递增，即使成指数，要最优的话，是最忌空车往返的，还有我认为这题的考点在能耗，满载1000直接去终点不会全耗尽煤的，
他没给最优载重，题意暗指能耗是成比例增长，忽略车重，1000吨直接到终点还剩是
1000*（0.999^1000),最后空车往返可不计。
个人愚见，勿怪
火车不用掉头，倒着开就好了。火车不是汽车。有调度给搬道岔就好了，不用自己控制方向。呵呵^_^
设定始发点为A（3000吨），第二个起点为B(2000吨)，第三个起点为C(1000吨)，终点为D。从B到A火车运行了5次，即消耗1000吨煤也就是运行了1000公里，所以B点应该设在200公里处。从B到C火车运行了3次，即消耗1000吨煤运行了1000公里，所以B到C的距离为1000/3。从C到D的距离为1000-200-1000/3 = 1400/3, 但是C点的煤为1000吨，所以剩余的煤为1000-1400/3 = 1600/3.
533吨我感觉就是极限了吧，如果便于计算的话，我还是运送了500吨。
不大明白超过500的是怎么算的，我得出是500，把路程分成4份是500，分成8份，得出的也是500，超过500的是怎么算的呢？
大家讨论很激烈啊！
一辆车一吨煤
假设有3辆车(刚好装满3000)
1000/ (3辆(消耗) + 2辆(返程))) = 200公里 (返回两辆),200公里处剩2000吨
假设有2辆车(刚好装满2000)
1000 / (2辆(消耗)+ 1辆 （返程)） = 333.333333公里 (返回一辆),533公里处剩1000 吨
有没有大牛能抽象成程序呢？
@xPacificCoolShell
我居然算成了2000-3000是6吨，1000-2000是4吨，脑残了
我能算到的是4000/9T
我来看下准确的算式.