面试题：火车运煤问题
这个可能是一个比较经典的智力题了，和以前的那个《赛马问题》很相似，其题目如下：
你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
这道题一开始看上去好像是无解的，因为你的火车每一公里就要消耗一吨煤，而到目的地有1000公里，而火车最多只能装1000吨媒。如果你的火车可以全部装下，到目的地也会被全部烧光，一丁点也不剩。所以，很多人的第一反应都是觉得这个不太可能。
如果你一开始就觉得不太可能的话，这是很正常的。不过我不知道你还会不会继续思考下去，如果你不想思考下去了，那么我很为你担忧，因为你可能并不是一个不善于思考的人，而是一个畏难的人，还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。
我一开始也觉得不可能，后来想了一想，想到一个解法可以最多运送500吨煤到市场，方法如下：（希望你先自己想一想再查看这个答案）
【查看答案】
好像这样很不错的了，不过还有更好的方法能运更多的媒过去。你知道这个方法吗？可以提示的是，就是以上述这个方法的思路。我先暂时不把答案放上来，你可以自己想想。过两天我把答案放上来。
更新（2011年4月17日）：大家都很聪明，533是应该是最优解，大家用了很多种方法阐述了这一过程，我最初的想法和朋友xPacificCoolShell的一致！很高兴看到有更为科学的解法，受教了。另外，还有一些朋友提出火车不能随时随地调头的实际情况，非常不错，所以，以后这题不能用火车运煤了，可能是用马运草更好一点了。;)
（转载本站文章请注明作者和出处 酷 壳 – CoolShell ，请勿用于任何商业用途）
(51 人打了分，平均分： 4.45 )
Loading...
《面试题：火车运煤问题》的相关评论
路程1000，来回就2000….非常的无解啊。
我不同意你的这些方法。你的所有方案前提是可以背着煤走而可以不用火车，这么一说最好的方案是背着1000吨煤直接到目的地。
我看错了 忽略上面评论。
我想了下能运500吨的方法：先从矿区运1000吨开始走，走到250公里的地方下500吨煤下来，还有250吨煤在车上，然后回矿区；再运1000吨开始从矿区走，到250公里的时候把上次下下来的煤运上250吨上来，这时候车上1000吨，继续走到500公里的时候车上还有750吨煤，下500吨下来回矿区，走到250公里时没有煤了，把还剩的250吨煤上上来继续回矿区；这时候还剩下的煤就是500公里那500吨，矿区1000吨，火车在矿区，这样火车从矿区运1000吨开始走，到500公里的时候把那500吨上上来车上有1000吨了，再到集市的时候还剩下500吨煤
不错！和我想的一样。很不错。
其实计算机一直是用这种中间件的方式发展、解决问题的。
一开始就想到这个问题的答案了，呵呵~
实在无解了才偷看答案——老大，你条件里没说能半道把煤卸下来啊，潜规则啊!
拜托把这条件补上吧~~~
哦，我以为这个潜规则你可以思考或推理出来的。半道把煤卸下往返几次是这题有解的方法之一啊。;-) 当然，在面试过程中，如果面试者想不出来这个潜规则，一般都应该提示的，因为面试时间有限。这里，大家都有时间去想，应该能推理出这个潜规则的。
推理不出“潜规则”的朋友应该也不必怀疑自己，这完全是中国教育的问题——把我们教得很死板地不会思考了。哎……
我是这样想的：火车运行时，最好让他满载，起始点记为A
第一步，分三次把煤运送到中间点B
第二步，分两次把煤运送到中间点C
第三步，把煤运送到目的地D
第一步：5*(AB) = 1000；解得AB=200
第二步：3*BC = 1000；解得BC=333.
第三步：AB+BC+CD=1000；解得CD=467
因此，做多运送533吨煤到目的地
强！可见数学对算法的重要性。
更有趣的问题是在最优的情况下，运到的煤跟消耗的煤的比例。
我想的方法比较土。。
先运1000吨至400公里处，卸下200吨，返回
继续运1000吨至400公里处，卸下200吨，返回
继续运1000吨至400公里处，卸下600吨。运1000吨至1000公里处，卸下400吨
。。只运了400吨。-____-!
我想到的解法和9楼一样
先假设路程是1，每次运的煤也是1.
第一次：开到1/5处，卸下3/5的煤，回来；
第二次：开到1/5处，装上1/5的煤，再往前开1/3，到达8/15处，卸下1/3的煤，掉头回到1/5处，正好没煤，装上1/5的煤，回来；
第三次：开到1/5处，装上1/5的煤，再往前开1/3，到达8/15处，装上1/3的煤，到终点.
最后一次消耗掉了1，路上装上了8/15，所以最后运到时还剩8/15.
不知道这样是不是最优？
@Thkfly
这个解不错，可能是最优的了。
但是有个问题在于，我们怎么知道需要分”三次运到B，两次到C，一次到D”?
@Thkfly
大开眼界
@Mine
因为共有3000吨，一次运1000吨，所以第一次要三次，
第二次，因为已经消耗了1000吨，只剩2000吨了，所有2次，
左右只有1000吨了，所以一次
我的理解是这样
@Thkfly
这个是正确的最优解。
假定从A到B需要2m+1次，距离为x，那么运过去消耗(2m+1)x的煤。一开始的时候必须(m+1)>=3才可以把煤运完，而且空载是没有哦效率的，所以(m+1)<4.
所以m=2，而m=1是，所剩煤为2000，m=0时，所剩煤为1000.由m值可以得到距离x，和9楼一样。
同时，在m不变的情况下，可以任意分段，比如m=2是，可以把煤运到50处，然后在运到100处，然后再运到200处，由于m都是等于2，所以到200时，总会剩下2000煤。
所以实际上解有无群多，只要让煤在200，533的地方重新聚集就行了。
@nemo
我也这样想的
假设车只能装载、卸下整数吨数的煤，可以用动态规划
f[n][d]: 车离终点距离d，有n吨的煤需要运送时最多可以送到终点的吨数
f[n][0]=n
f[n][d]=max{f[n-times*k][d-k]}
times=ceil(n/1000)*2-1, k \in [1,floor(n/times)]
复杂度O(nd^2)
有点大材小用了……
我是这么想的：
当煤量在(2000,3000]时，需要运送三次；
当煤量在(1000,2000]时，需要运送两次；
当煤量在[0,1000]时，需要运送一次。
那么，我们只需要设置两个中点站，分别使总剩余煤量为2000，1000。
这么一算，第一段距离为200m，第二段距离为2000/3m，第三段距离为1000-(200 + (2000/3))m
理论最大值为1600/3吨。
不过这个解法假设车运煤的方式只是把所有煤运到同一个点中转
@Thkfly
恩，这个解法很好。
我算的大概是533，想法是每次都充分利用火车的运载量 刚好装满
额。都是强人。我只想到了运500吨的那种~
【每一公里需要耗一吨煤】？不管运多少煤，消耗速度都一样？
空车返回，消耗速度？
中途卸煤，下次再装，要不要开销？
这个算动态规划类问题么?.
刚开始我也想到用中途放下返回的问题，但是如何达到最优值，陷入困难。
经过思考，我的解题思路是这样的：首先，要获得最大值，必须在最远的中间”补给点”放下等同其路程的煤作为补给。所以接下来要做的就是，如何让2000吨煤放到最远的地方，同时留下“补给煤”。因为条件限制，所以只能分两次达成上面的目标，第一个补给点，他要消耗的是他路程的5倍的煤，因为他自己消耗两次，第二次送煤的消耗两次，最后一次直达终点的要消耗一次。所以他要在1/5的地方放下，第一个点已经提供补给，所以第二点要补给3次，他自己两次，最后直达的一次。所以是在200+333的地方放下333.所以最后到达的，应该是200+333 = 533. 总数是其他值也可以推导出来了
编程的例子就是：
int sum = 3000;
int load_num = 1000;
int result = 0;
int time = sum / load_num – 1;
for (int i = time; i > 0 ; –i) {
result += load_num / ((i*2) + 1);
}
中间可以放下
533…
200,1000/3,1400/3
@Thkfly 的应该是最优解
我一开始的的思路，算出来是416吨，说出来和大家分享一下：
整个过程分为三段路程：
第一段从起点开始，煤每前进1公里，需要消耗6吨煤（运3次，每次1个来回），1000/6=166
第二段从166公里开始，此时还有煤3000-166*6=2004，由于2004-2000=4，此时再运3次不合算，因此在166公里，会舍弃4吨煤，以2000吨记。煤每前进1公里，需要消耗4吨煤（运2次，每次1个来回），1000/4=250
第三段从416公里开始(166+250)，此时还有煤2000-1000=1000
此时到终点的时候，应该还有煤416吨
我考虑的是煤堆前进的成本，显然这一步一步前进造成了额外的浪费啊
@travis 恐怕是你自己计算错了。你再仔细理一理 ;)
非常非常有意思的题目！
最开始还以为是无解的，然后试着算了一下发现居然有希望
路程分三段，
第一段要来回5次，耗煤系数为5,
第二段的系数为3，
第三段的系数为1，
然后稍微计算一下就有结果了
@travis
第一段只需要来回5次，最后一次不用矿山了
第二段同理，只有3次
@travis
恩，对比Thkfly的：
1000/6 VS 1000/5
1000/4 VS 1000/3
哈哈，每次分母浪费了1阿
还有就是我用firefox4 怎么点查看答案闪了一下就没有了。。
跳转到javascript: document.getElementById(‘answer’).style.display = ”;这个页面了
这是我的失误，只测试了Chrome，没有测试FF和IE。原来a href=”javascript:”中在FF和IE中不能有语句，只能有function。Chrome下则没有这个限制。真是万恶的Web编程啊。
刚在GReader里面看到，算出来533，点开一看评论，大家都解出来了嘛。
关键就是让火车第二次开得尽量远，并且火车第三次到了第二次所在位置时能正好补满。这就要求火车第一次开得尽量近，省煤。
这道题算是不错的小学数学奥赛题
都是强人啊
受教了。。。。。
1000是基本刻度，解题精髓在于消耗多余的煤把煤移动到一个离终点更近的距离，最后一次运上1000吨然后从这个地方直达终点，还能剩下的就是你能运达的煤。
煤越多需要搬运的次数越多，次数越多消耗就越多。
要运送到相对较近的距离对煤的消耗量为(2n + 1)*Step，Step为一次行进的步长，n=(总煤量 – 1) / 1000,
根据这个公式，
当煤量为2000～3000时，你的运送成本是5*Step
1000～2000时为3*Step，
小于等于1000时为1*Step,
所以第一次选择行进200公里，消耗的煤为5 × 200 = 1000，剩余2000
第二次选择行进333公里，消耗的煤为3 × 333 = 999 =～ 1000，剩余1000
此时一共行进了533公里，还剩下1000吨煤，最后到达终点还剩533吨
其实次数是无所谓的，关键是把握消耗的数量级。
此题具备高中数学知识就够解了，我发现算法其实很多时候要求的数学知识并不是非常精深，很复杂的数学问题的解也许是一个很简单的方程。
思考大于知识。
1000是基本刻度，解题精髓在于消耗多余的煤把煤移动到一个离终点更近的距离，最后一次运上1000吨然后从这个地方直达终点，还能剩下的就是你能运达的煤。
煤越多需要搬运的次数越多，次数越多消耗就越多。
要运送到相对较近的距离对煤的消耗量为(2n + 1)*Step，Step为一次行进的步长，n=(总煤量 – 1) / 1000,
根据这个公式，
当煤量为2000～3000时，你的运送成本是5*Step
1000～2000时为3*Step，
小于等于1000时为1*Step,
所以第一次选择行进200公里，消耗的煤为5 × 200 = 1000，剩余2000（2000～3000）
第二次选择行进333公里，消耗的煤为3 × 333 = 999 =～ 1000，剩余1000（1000～2000）
此时一共行进了533公里，还剩下1000吨煤，最后到达终点还剩533吨（1000内）
其实次数是无所谓的，关键是把握消耗的数量级。看把第二个刻度分解了
第一次选择行进200公里，消耗的煤为5 × 200 = 1000，剩余2000（2000～3000）
第二次选择行进200公里，消耗的煤为3 × 200 = 600，剩余1400（1000～2000）
第三次选择行进100公里，消耗的煤为3 × 100 = 300， 剩余1100（1000～2000）
第四次选择行进33公里，消耗3×33=99～=100，剩余1000（1000～2000）
此时一共行进了533公里，还剩下1000吨煤，最后到达终点还剩533吨（1000内）
此题具备高中数学知识就够解了，我发现算法其实很多时候要求的数学知识并不是非常精深，很复杂的数学问题的解也许是一个很简单的方程。
思考大于知识。
@albert
1000是基本刻度 是如何确定的？n=(总煤量 – 1) / 1000如何得出的？
中间要卸煤，再回去再装，关键是在何处卸煤可以利益最大化
反正去市区很近，何必用火车运
问题在于，你半路扔下的煤等你下次去还会在那里么？早就被人捡走了吧
先运到200米处，三趟使得那里有600＊3。
然后运到500米处，运两次，这时可以带这900走完最后500米，这样终点有四百。
这是一个近似问题我觉得，作为程序员思路是使得最后一处拥有1000的数尽量靠近终点，而在这处前地上都没有煤了，是一个近似问题，对1000做剖分，剖分越细集合越大，解越精确，最值难说。
感觉上精确解是667
顺带这里问问
Mount Fuji Problem?
不知道这个行话怎么说啊
瞧你说的 算法本身就是基于数学的！！！！！！！！！！！！！！@陈皓
顶13楼的,不是说其他的版本不好,只是这个版本火车回头的次数最少,也最易于理解.
3000吨煤,毫无疑问最少的运输次数为3次,第一次时,其实就是为后两次运输的补给作准备,假设其行走最远距离为x,则它本身的来回2x,加上第二次在这段距离上的来回2x,再加上最后一次的来(没有回)x,5x=1000,即x=200.
第二次时,由于之前的200距离无需考虑煤的消耗,所以在200的基础上,假设其继续走了y,即它自己在y上的来回2y加上第三次的来(同样没有回)y,3y=1000,即y=1000/3.
第三次时火车尽管往前开,遇到煤再补给上就ok了.
我有个不靠谱的想法，在这道题里，我们可以把关键视为如何使火车的运载效率最大化的问题，成本是运行过程中消耗的媒量，而收获则是运送到目的地的媒量。这样效率可以简化为 运载量/消耗量。在一次运载过程中，我们在起点都会装载饱和数量的媒，那么，一次运输的运载量其实取决于运载距离的长短。所以我想，如果无限缩短每次的运载距离，是不是可以得到一个比较大的效率？
看这分析，太爽了。
昨天没时间回复.
假设火车一次装满1000T,往前开1Km,卸下998T,剩下1T开回去.所以火车把全部的煤拉到1Km处需要消耗5T.最后一次不需要回去了.结论就是超过2000T的煤需要5T/Km的消耗.这样往前推进,到200Km的地方,还剩2000T煤.
接下来的一段路,1000T到2000T之间的煤,需要3T/Km的消耗.到达下一个点(还剩1000T)的点,是多远呢? 1000T/3T=333.33Km
最后,车子在533.33Km的地方还剩1000T煤,满载到达终点,还剩533.33T
看样子要用到微积分,但是数学从来没及格过,所以将就看吧.
哈，我的思路并不好，由于在运输过程中，在每一小段的起点媒量都是递减的，因此必定有一趟车无法满载的情况，因而也就无法计量其效率。正确的分析方法应该是：对于一段任何长度的距离，运输的成果 = 起点的媒量 – 运载过程消耗的媒量。耗媒取决火车行驶的路程，因而关键则在于减少运输的次数。如果要分X次运输，则耗媒 = (2 * X – 1) * 距离。如果能找到几个分点，使到第一个分点时，耗媒量恰等于1000吨，则在接下来的一段路程中只需运载X-1次。所以btpot的解法是最好的。
不知道想得对不对：
((1000/3 + 1000)/3 + 1000)/3=555