面试题：火车运煤问题
这个可能是一个比较经典的智力题了，和以前的那个《赛马问题》很相似，其题目如下：
你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
这道题一开始看上去好像是无解的，因为你的火车每一公里就要消耗一吨煤，而到目的地有1000公里，而火车最多只能装1000吨媒。如果你的火车可以全部装下，到目的地也会被全部烧光，一丁点也不剩。所以，很多人的第一反应都是觉得这个不太可能。
如果你一开始就觉得不太可能的话，这是很正常的。不过我不知道你还会不会继续思考下去，如果你不想思考下去了，那么我很为你担忧，因为你可能并不是一个不善于思考的人，而是一个畏难的人，还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。
我一开始也觉得不可能，后来想了一想，想到一个解法可以最多运送500吨煤到市场，方法如下：（希望你先自己想一想再查看这个答案）
【查看答案】
好像这样很不错的了，不过还有更好的方法能运更多的媒过去。你知道这个方法吗？可以提示的是，就是以上述这个方法的思路。我先暂时不把答案放上来，你可以自己想想。过两天我把答案放上来。
更新（2011年4月17日）：大家都很聪明，533是应该是最优解，大家用了很多种方法阐述了这一过程，我最初的想法和朋友xPacificCoolShell的一致！很高兴看到有更为科学的解法，受教了。另外，还有一些朋友提出火车不能随时随地调头的实际情况，非常不错，所以，以后这题不能用火车运煤了，可能是用马运草更好一点了。;)
（转载本站文章请注明作者和出处 酷 壳 – CoolShell ，请勿用于任何商业用途）
(50 人打了分，平均分： 4.52 )
Loading...
《面试题：火车运煤问题》的相关评论
花几分钟想了简单的..
1. 前提条件是 采用前进一段距离放下煤后回头取了再前进的方式. 不考虑把火车开回去了. 这种亏本生意做一次就够了.到了把火车卖了吧…
要想运到对面去取决于第一次运的距离. >= 500时没有意义 前进与回头会消耗掉所有的煤. 应该在1-500中取最优值.也就是1/1000 – 1/2.
现在取个简单的数. 333. 1/3 第一次运到333位置.每次1千最大运力 那么3次后5次来回距离 消耗 333*5 剩余1435 剩余距离667 = 最终运到的煤是 768..
后续最优值可以计算也可以用程序实现了.
@cooskin
写错了…. 应该是计算 最小平均消耗煤说走的距离.
我认为这道题不难。
首先，可以想到唯一的方法就是火车运一部分煤再中途停下往返装满继续运。
其次，火车至少要从起点处出发三次才能把所有的煤运完，也就是说火车中途要掉头两次。
第三，我们可以把火车中途放下煤的点看做是中途的加油站，那么在第一个“加油站”处，火车要经过5次（包括第一次运到该处），那么作为最有，需要5次用完正好一车煤，也就是1000吨，那么第一个点显然是1000/5=200
第四，那么考虑第二个点的位置时，我们可以知道火车经过三次，而此时火车在经过第一个点时早已把煤补充到1000，也就是说第二个途中加油站提供了从第一个点到第二个点三次的运行所需的煤，那么1000/3=333.3。也就是说第二个点在533.3公里处。
剩下就很容易算了~~~~
思考这个问题好长时间了。现在说说我的想法。 其实这个可以再拓展一下，比如可以有4千吨 5千吨 …… 然后距离是2000米 3000米……
核心思想是从一个点到另一个点的距离最好要满载才能达到最优。
假设有N千吨，可以这样计算，开始把所有的煤运到1米的地方，消耗的煤量是2N-1吨，运到2米处还要消耗2N-1吨。在这过程中我们要寻找一个点，在这个点以后每次消耗的煤量就不是2N-1而是2(N-1)-1了。第一个这样的地方就是消耗了1000吨煤的地方A。因为到了A后，再往后面每运煤1米就只需要消耗2(N-1)-1吨了。这样不断继续下去，假设到了一个点X,距离终点还有W的距离。而还剩下M千吨，1000/(2M-1)如果大于W的话，就可以不用再寻找下一个剩下M-1千吨的位置了。就可以直接把这些运到最终位置。
@Thkfly
不太明白你说的过程，能详细解释下吗
初步测定每100km往返和50km往返（往返时装尽可能多的煤），两者都在距离出发点500km出剩余1100t，然后再耗100t至533.333333km处，此时剩余1000t，然后就回来就ok了~~~
关键是最后1000t煤的形成，因为那时候不用往返浪费了，浪费的少了，剩下的就多了。思想就是：如何使这1000t煤形成的点更往终点靠近。
我最开始想到的是500，然后是533，最后想有没有办法火车还能回去,我以为博主卖掉500火车还能开回去，百思不得其解
1000 – (333*3 + 444*2 + 111) = 556
其实，类似的问题可以有一个更现实的背景。
在马岛战争期间，英国皇家空军（RAF）曾经用火神式轰炸机袭击马岛上阿根廷的空军基地。但是，一旦火神轰炸机携带了足够从英国距马岛最近的基地往返马岛的燃油，就无法携带任何炸弹，and vice versa。已知火神可以相互加油（当时 RAF 确实有其他专门的加油机，但来不及调度了），求策略（当然，出成题目时，需要给定更多参数和一些假定，并要求回答者给出诸如不带弹飞机的燃油载荷之类数据）。
这是真实发生的事情，当时 RAF 让 6 架火神先后起飞（考虑到飞机在不同载荷下的最优巡航速度不同；当然出题时候可以忽略），其中只有一架带弹，途中其他五架火神给带弹的飞机先后加油并返航。这是军事航空史上非常有名的战例。
我做过这个题目，是汽车拉油，对方明确告诉我，必须做到多少以上才算过关
火车不能调头，但是可以装两个车头，倒车……呵呵，运兵车随时准备逃跑，这是历史上真实发生过的故事（有兴趣者自己考证）；双车头交替驱动，还是一代大家很出名的设计（肯定都知道是谁，小学课文都学过）；同时这也是当今很多火车的架构
实在有点看不下去，出题就给人感觉就要这么做，还来看低人说不适合做程序员。说的轻松，走到半路卸煤炭？谁给你卸啊？题目就没说这些东西。有点不爽。
空载火车返程损失的煤可以忽略不计，这个大家普遍忽视的常识问题。
哇哦，简洁明了，厉害！。。
我开始算出来是 400 吨。。假设运到某个点 x（距离起点 x 公里），存储总量是 1000 吨，然后一次性运到终点。所以 5x + 3y = 3000 而且 3y = 1000，求出 x = 400；于是，剩下 600 公里，运送 1000 吨煤，剩下 400 吨……
@xPacificCoolShell
赞赞赞赞赞赞赞赞赞赞！不能更赞！
此事如果发生在中国，当你卸下煤的一瞬间，就会被路人哄抢，一抢而空
因为你是煤老板，所以你可以选择超载
用C语言写一遍:
1 /*************************************************************************
2 > File Name: CoalTrain.cpp
3 > Author: vachel
4 > Mail: [email protected]
5 > Created Time: 2014年05月09日 星期五 10时12分52秒
6 ************************************************************************/
7
8 #include
9 using namespace std;
10
11 //总共3KT煤
12 #define TOTALCOAL 3000.0
13 //运送距离1000KM
14 #define DISTANCE 1000.0
15 //每次最多运送1000T
16 #define MAX_TRANS 1000.0
17
18 int main()
19 {
20 int n = TOTALCOAL / MAX_TRANS;
21 float anMidPoint[n];
22 float nTotalDis = 0;
23
24 for(int i = 0; i < (n – 1); i++)
25 {
26 anMidPoint[i] = MAX_TRANS / (2 * (n – i) – 1);
27
28 nTotalDis += anMidPoint[i];
29 }
30
31 anMidPoint[n – 1] = DISTANCE – nTotalDis;
32
33 cout << "Total coal: \t\t" << TOTALCOAL << " T" << endl;
34 cout << "Transport distance: \t" << DISTANCE << " KM" << endl;
35 cout << "Transport volume: \t" << MAX_TRANS << " T/KM"<< endl;
36 cout << "Profit: \t\t" << MAX_TRANS – anMidPoint[n – 1] << " T"<< endl;
37
38 return 0;
39 }
#: g++ CoalTrain.cpp
#: ./a.out
#: Total coal: 3000 T
#: Transport distance: 1000 KM
#: Transport volume: 1000 T/KM
#: Profit: 533.333 T
我在想为什么拉1000吨煤和空车(不拉煤)耗油都是1T/KM呀. @vachel
@Thkfly
你用的可是贪心算法么？
可是贪心算法？
双头火车就行了，不用掉头
原题是开车穿过沙漠什么的。。
function trans(dist, coal, left_dist){
/*
dist 每段运送(中途卸载)的距离
coal 每段需要运的煤数量
left_dist 每段与市场终点的距离
return 返回到达市场后剩余煤的数量
*/
if(coal2*dist){
amount += coal%1000-dist;
}else{
amount += dist;
}
return trans(dist, amount, left_dist-dist); //递归计算下一段的运煤
}
var best=0;
for(var i=1;ibest) best=tmp;//获取最大值
}
console.log(“最大运煤量”,best);//最大运煤533
原来最佳的方案就是每段运一公里就中途卸载…
function trans(dist, coal, left_dist){
/*
dist 每段运送(中途卸载)的距离
coal 每段需要运的煤数量
left_dist 每段与市场终点的距离
return 返回到达市场后剩余煤的数量
*/
if(coal2*dist){
amount += coal%1000-dist;
}else{
amount += dist;
}
return trans(dist, amount, left_dist-dist); //递归计算下一段的运煤
}
var best=0;
for(var i=1;ibest) best=tmp;//获取最大值
}
console.log(“最大运煤量”,best);//最大运煤533
原来最佳的方案就是每段运一公里就中途卸载…
@冬瓜
发上去代码就变了…
[javascript]function trans(dist, coal, left_dist) {
/* dist 每段运送(中途卸载)的距离
coal 每段需要运的煤数量
left_dist 每段与市场终点的距离
return 返回到达市场后剩余煤的数量 */
if(coal 2*dist){
amount += coal%1000-dist;
}else{
amount += dist;
}
return trans(dist, amount, left_dist-dist); //递归计算下一段的运煤
}
var best=0;
for(var i=1;ibest) best=tmp;//获取最大值
}
console.log("最大运煤量",best);//最大运煤533[/javascript]
最佳的方案就是每段运一公里中途就卸载
def Coal(CoalTotal, ContainPerRound, Dist, ConsumePerDist):
# 剩余煤总量，每次运煤最大量，剩下的距离，每段单位距离消耗
ThisRoundConsume = CoalTotal%ContainPerRound
if ThisRoundConsume = Dist:
return CoalTotal-ThisRoundConsume
return Coal(CoalTotal-ThisRoundConsume, ContainPerRound, Dist-forhead, ConsumePerDist)
print Coal(3000, 1000, 1000, 1)
====================================
3000 1000 1000 1 1000
2000 1000 800.0 1 800.0
1200.0 1000 533.333333333 1 200.0
1000.0 1000 466.666666667 1 466.666666667
533.333333333
====================================
思路： 尽量每次装满，以最大化利用消耗与装载量无关这个因子。
先将所有的煤从A运到B，使下一轮运输刚好能少跑一个来回，如此反复。
加上一些无法运输的异常处理。
/**
你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
*/
function trans(dist, coal, left_dist){
if(coal 2*dist){
amount += coal%1000-dist;
}else{
amount += dist;
}
return trans(dist, amount, left_dist-dist); //递归计算下一段的运煤
}
抱歉, 试了几次, 发了很多重复的, 最后一次也没成功发出能看的代码, 麻烦皓哥把上边的和之前几条都给删了吧
/*
dist 每段运送(中途卸载)的距离
coal 每段需要运的煤数量
left_dist 每段与市场终点的距离
return 返回到达市场后剩余煤的数量
*/
function trans(dist, coal, left_dist){
if(coal <= 1000){
return coal-left_dist;
//如果当前段需要运煤的数量小于1000(小于火车最大装载量),则一次运到市场,剩余煤数量即为 当前段需要运煤数量减去当前段与市场的距离
}
var left=1000-dist*2; //每段中, 在每个来回后中途卸载煤的数量
var amount=Math.floor(coal/1000)*left;// 每段中, 所有来回后送给卸煤的数量
if(coal%1000>2*dist){
amount += coal%1000-dist;
}else{
amount += dist;
}
return trans(dist, amount, left_dist-dist); //递归计算下一段的运煤
}
var best=0;
for(var i=1;i<500;i++){
var tmp=trans(i, 3000, 1000);//分别计算每段运送距离为1到500公里的运送方案的最后剩余煤数量
console.log(i,tmp);
if(tmp>best) best=tmp;//获取最大值
}
console.log(“最大运煤量”,best);//最大运煤533
犯了个低级错误, 转义了下终于发成功了
这道题用贪心就好了
1.可以证明x10.w是在x0剩下的煤量.
3.知道2画个w-x图就完了(w是到x时可能剩下最多的煤)，斜率在x=200和x=533.333变化，斜率分别为-5，-3，－1。于是策略有无限种，不管在哪掉头，掉头几次，保证掉头点的（x,w）在w-x图上就行了。
用数学的方法做的，运5个单次剩2000，再运3个单次剩1000，用剩下的1000走完剩下的距离
X+ Y + Z =1000,5X=1000,3Y=1000
X=200,Y=333.3,Z=466.67
1000-Z=533.3
天哪！我的表达能力太弱了，而且遇到问题喜欢用数学而不是编程逻辑。
菜鸟女程序员一枚,最近受到挫折都来这疗伤。。。
看到跟火车运煤有点像的一题：
小王准备从营地出发，步行穿越一片长达600公里的荒凉之地。他最多只能随身携带300单位的补给，每行走1公里就要消耗1单位的补给，路上也没有任何增加补给的地方。假设小王可以在中途任意设置休息区存放补给，请问至少在营地准备多少单位的补给才能完成穿越？
如果小王一共准备了3300单位的补给，请问他最远能穿越多少公里？
第二问是300/21+300/19+….+300/3+300/1 = 654比较简单
第一问还在想
n=1
s=0
while s 8个中间点
那么小王用8*300 = 2400的补给走了606.54km的路
多了6.54km =》 至少浪费了6.54单位的补给
然后我们要把写浪费的节约下去，就是在第一段节约(节约：让第一段路变短)最优，第一段走了共2*8-1=15次（一次是单向的一次）
至少耗费2400 – 15*6.54 = 2301.9
代码贴错了
n=1
s=0
while s<=600:
s += 300.0/(2*n-1)
n += 1
print n," ",s
你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——满载每一公里需要耗一吨煤。空载每公里需要耗0.5吨煤，请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
看来思路一样的人是有的，和BlowBlood一样，不过最初的开端想法不一样。我是从一开始就考虑了满载的情况和费满载的情况，然后才是后面的思路，这样的话整个推理没有停顿，不需要考虑漏掉什么，一气呵成。而最优解就是这样，从理论上讲，掉头的距离短一点长一点结果一样，但是实际考虑的话，还是掉头越少越好，所以应该是最优解是唯一的。
@楠楠
同理
我不知道为什么大家做的这么一致，只感觉我的思路没问题。我说一下思路和答案，大家看看有什么问题没。
逆推的方式，火车满载率最大即1000吨时能达到运送次数最少的结果，做老板这个应该很实际。
最后一段路是运送一定是运送着1k走剩下的路
到数第二段路是分两次运送2k后剩下1k，或者分3次运送后剩下1k，注，满足满载率后，我们最多分3次，所以第二种情况下，这里就是顺数第一段路了。
倒数第三段路一定是分三次运送3k后剩下2k。
推论是剩下的煤吨数和前面几段路的总和的数量相等。
我们按照刚才的两种情况分别运算比较就得到最优。
先按两段路走完的情况做计算
第一段路分3次剩下1k，火车返回消耗同样的煤数量。3次等于跑来同样路6趟，消耗2k煤，即走了 2000 / 6 = 333公里。按照推论，333公里就是最后运送剩下的煤数333吨。
按3段路走完的情况做计算
第一段路分3次剩下2k，火车返回消耗同样的煤数量。3次等于跑来同样路6趟，消耗1k煤，即走了 （3000 – 2000） / 5 = 166公里。
第二段路分成两次剩下1k,2次等于4趟， 即走了 （2000 – 1000）/ 4 = 255公里。
按照推论，可以剩下166+255 = 416吨煤。
416作为最终结论。要总结为数学公式，我就先不总结了。按照走来回计算，前面同学提供的算法结果应该是 1000 / (5 * 2) + 1000 / (3 * 2) = 266。所以不是最优解。大家帮我看看推理是否有问题
@Submarine
我觉得这是解释得最清楚完整的解释了——事实证明我自己太弱了，怎么也想不清楚，只能看别人解答……
@蜻蜓
感觉你的思路是对的（和前人一致），不过还是有点乱乱的，主要是计算错误1000/5和1000/4都算错了哦
@健那绿
Sorry，应该是1000/5和1000/3，因为3次转移只需跑5趟，2次转移只需跑3趟