面试题：火车运煤问题

面试题：火车运煤问题

评论 336 条评论 194,405 人阅读

这个可能是一个比较经典的智力题了，和以前的那个《赛马问题》很相似，其题目如下：

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

这道题一开始看上去好像是无解的，因为你的火车每一公里就要消耗一吨煤，而到目的地有1000公里，而火车最多只能装1000吨媒。如果你的火车可以全部装下，到目的地也会被全部烧光，一丁点也不剩。所以，很多人的第一反应都是觉得这个不太可能。

如果你一开始就觉得不太可能的话，这是很正常的。不过我不知道你还会不会继续思考下去，如果你不想思考下去了，那么我很为你担忧，因为你可能并不是一个不善于思考的人，而是一个畏难的人，还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。

我一开始也觉得不可能，后来想了一想，想到一个解法可以最多运送500吨煤到市场，方法如下：（希望你先自己想一想再查看这个答案）


【查看答案】

好像这样很不错的了，不过还有更好的方法能运更多的媒过去。你知道这个方法吗？可以提示的是，就是以上述这个方法的思路。我先暂时不把答案放上来，你可以自己想想。过两天我把答案放上来。

 

更新（2011年4月17日）：大家都很聪明，533是应该是最优解，大家用了很多种方法阐述了这一过程，我最初的想法和朋友xPacificCoolShell的一致！很高兴看到有更为科学的解法，受教了。另外，还有一些朋友提出火车不能随时随地调头的实际情况，非常不错，所以，以后这题不能用火车运煤了，可能是用马运草更好一点了。;)

（转载本站文章请注明作者和出处 酷 壳 – CoolShell ，请勿用于任何商业用途）

相关文章

好烂啊有点差凑合看看还不错很精彩 (51 人打了分，平均分： 4.45 )
Loading...

《面试题：火车运煤问题》的相关评论

  1. 我总结一下吧：
    一开始我是想到把1000公里平均分段，在分段点放下部分再折返取，这样的思路有如下结论：
    分2段剩0吨，分3段剩2吨，分4段剩500吨，分5段剩400吨，分6段去不到终点（？），分7段剩285.71吨，分8段剩500吨，分9段剩444.44吨，分10段剩400吨。
    但经过各位高手的分析，发现是有改进的方法，就是在分段的时候，如果按平均分的话，如果剩余数刚刚到1000吨的临界点时，如果还在路上，不在分段点上改变策略(这个词可能不合适)，就有可能会有浪费在路上的消耗。所以可以按剩余吨数来进行分段，每一个满载吨数分一段，段的距离就由满载吨数除以需要往返的次数决定，这样可以再推广到原有大于3000吨煤的情况。按照这样分段的话，剩余533.333吨应该是最优的方法了。如果还有更好的方法吧，望高手指教！

    回复

  2. 如果我是煤老板，我会用三辆这样的火车来运…

    最多可以运输 833.33333333333333333

    调什么头啊

    -_-!!

    回复

  3. 用步进的方法来算：（即是算出每前进一米需要多少吨）
    设一个值初始为3000（出发时的吨数），一个时间段为1000（公里数）
    大体步骤：
    1.大于2000之前，每前进一米需要走三趟，来回算起来总共5次（因为运完第三趟不用返回出发地，所以少一次），即消耗5吨，消耗时间t1；
    2.1000~2000之间，需要来回两趟，来回算起来共3次，即消耗3吨，消耗时间t2；
    3.小于1000时，直接运输到目的地，消耗时间（1000-t1-t2）；

    回复

  4. 简单示例代码：

    var tons = 3000;
    var miles = 1000;

    while(tons > 2000) {
    tons -= 5;
    miles–;
    }

    while(tons > 1000) {
    tons -= 3;
    miles–;
    }

    var final_tons = tons – miles;

    document.write(“tons: “+tons+”miles: “+miles+”final tons: “+final_tons);

    结果：532

    回复

  5. Nado :
    简单示例代码：
    var tons = 3000;
    var miles = 1000;
    while(tons > 2000) {
    tons -= 5;
    miles–;
    }
    while(tons > 1000) {
    tons -= 3;
    miles–;
    }
    var final_tons = tons – miles;
    document.write(“tons: “+tons+”miles: “+miles+”final tons: “+final_tons);
    结果：532

    为什么我的是532？？？？？？？？？
    我要检查检查~~~~~

    回复

  6. ⊙﹏⊙b汗
    应该是求极限值~~~我粗心的将一米划为最小值了…..
    改进下代码：
    var tons = 3000*10000;//放大N倍，将最后结果再除回此数即可得到最优结果(N越大，结果越精确)
    var miles = 1000*10000;

    while(tons > 2000*10000) {
    tons -= 5;
    miles–;
    }

    while(tons > 1000*10000) {
    tons -= 3;
    miles–;
    }

    var final_tons = tons – miles;
    final_tons = final_tons/10000;

    document.write(“tons: “+tons+”miles: “+miles+”final tons: “+final_tons);
    最后得到的结果：
    tons: 9999998
    miles: 4666666
    final tons: 533.3332

    我发现用纸笔来做的话，我就会失去逻辑思维……（汗颜）

    回复

  12. 基本思路有了，为也想到了走到半路扔下一些，然后回去再拉，过来的时候再装上，可我没算出数字来

    回复

  20. 思路：设火车能够在铁路旁卸货存放，因此，可以设火车行走Xi千米以后卸货返回，且卸货Xi吨煤后。当火车返回重新装满煤以后重新开往市场，在Xi处重新装上卸载在路旁的Xi吨煤矿，此时火车回复1000吨，同样，火车继续往前开，在Xi+1处卸载Xi+1吨煤，返回；如此往复，通过n次以后到达市场。限制条件则是煤矿总量3000吨，且卸载后煤矿存量可以保证火车返回矿区。
    因此，通过实际模拟后，可以看出，火车最后到达市场时仅剩煤矿500吨。（火车在超过500千米路程的道旁是无法卸载超过500吨煤矿的。）
    具体数学算法忽略

    回复

  21. 假设能掉头，能中途装卸，第一次在250公里处卸下500吨，回去；第二次在250公里处补充满，在500公里处卸下250吨，回去

    回复

  22. 我解了一个上午，最后得出几个不等式方程，还得用用微分才能解出答案。
    很久都没学习了，数学知识下降很多啊。
    y = 2000-2*x1-2*x2。
    已知：
    0<= x1<=x2 <=500 …………….(1)
    1000<=3*x1 ………………………(2)
    x1+x2<=1000……………………..(3)
    2000<= 2*x1+3*x2 ……………..(4)
    根据4个不等式求y的最大值即可。要用到微分，都忘了。

    这只是其中一种情况呢，还有几种，我得哭了。

    回复

  25. 三辆火车同时出发：
    第一阶段：在(1000/3)Km地段三列火车共计消耗1000吨煤，剩余2000吨煤、两列火车、1000-1000/3Km
    第二阶段：在(1000/3+1000/2)Km地段剩下的两列火车共计消耗1000吨煤，剩余1000吨煤、一列火车、1000-(1000/3+1000/2)Km
    第三阶段：在终点剩下的一列火车共计消耗（1000-(1000/3+1000/2)）吨煤，剩余（1000/3+1000/2）吨煤

    |—-第一阶段
    |—-1000/3—-|—-第二阶段
    |—-1000/3—-|—-1000/2—-|—-第三阶段
    |—-1000/3—-|—-1000/2—-|—-1000-（1000/3+1000/2）—-|

    最优解：（1000/3+1000/2）吨（这只是理想状态下的最大值，当然火车中途是不能停车的^_^!）

    回复

  26. 用(x[k],y[k])表示距起点x[k]公里处得中转站，屯煤y[k]吨。(x[0],y[0])=(0,3000)
    那么从x[k]到x[k+1]需要运ceil(y[k+1]/1000)次。
    来回共损耗:(2*ceil(y[k+1]/1000)-1)*(x[k+1]-x[k])吨煤。
    那么整个全称总共蚝煤：2*Sum（ceil(y[k+1]/1000))*(x[k+1]-x[k]))-1000 吨，sum表示k从0-n求和
    由于ceil(y[k+1]/1000)只能取3,2,1，为了描述方便，假设：
    x1是最后一个需要运三次才到的中转站；
    x2是最后一个需要运二次才到的中转站；
    x3是最后一个需要运一次才到的中转站；
    那么整个损耗公式可以化简为：2(x1+x2+x3)-1000
    为了使损耗最小，必须x1,x2,x3最小。（x3很显然，最后一站，应该是x3=1000)
    当y[k]>2000时，x[k]=(3000-2000)/5=200
    同理可以推得：x2>=(2000-1000)/3+x1=1000/3+200=1600/3
    那么损耗最小就是：2(x1+x2+x3)-1000=2(200+1600/3+1000)-1000=7400/3
    那么还剩3000-7400/3=1600/3 ,约为533吨

    回复

  28. 没看答案的情况下，想到了500的解法，跟大家的一样。能像到533的解法的应该数学都不错。看到有人说火车不可以随时掉头，这想法挺有趣，但是陈老师不必将题目从“火车烧煤”改成“马吃草”，因为火车是可以通过前后各挂一个车头来实现“掉头”的，当年“人”字形铁路上用的就是这样的，呵呵～

    回复

  30. 因为是3000吨的煤总量，所以将路线分割为3段，也就是中间设置两个节点。三段路程分别是x/y/z。
    原因如下：
    让3000吨货物到第一个节点时能留下2000吨煤，
    让2000吨货物到第二个节点时能留下1000吨煤，
    这样最后火车可以满载1000吨煤走剩下的最后一段路线，达到运载货物最多的目的。
    （总之，每个节点都要有1000整数的煤，以达到最大化，避免零头浪费）

    第1个节点公式
    公式 3000-5x=2000，得出x=200

    第2个节点公式
    公式 2000-3y=1000，得出y=333.3循环
    则 z=1000-x-y=466.6循环

    最后剩余1000-z=533.3循环吨煤

    如果是4000吨煤，每次最大运输也是1000吨煤，则分4段路程，设3个节点
    总的想法是让火车每次往前运煤都尽量处于满载状态

    回复

  32. 个人比较喜欢 庞华林 的思维 言简意赅 开始想了好多方法都没这个简单易懂
    我再自己试试证明一下

    回复
  33. Pingback： 面试题：火车运煤问题 « Caran懜想天堂

  37. 何必想得太复杂呢。
    分三个阶段想，一第一个阶段必须要拉三次（掉头两次），第二阶段拉两次，第三阶段拉一次
    那么第一阶段需要达到的目的就是只剩下2000T煤，也就是需要把三车煤都运到离起点200KM（200=1000/5）的一个点，
    同理第二阶段就需要拉到离起点533KM的点，其中有一车还可以再送到前面0.5公理（或者直接扔掉一T煤），
    这时还有1000T煤，再走1000-533KM，也就是可以剩下533T煤。

    回复
  38. Pingback： 再谈“我是怎么招聘程序员的”（上） | Xeno Joshua

  43. @庞华林
    请问，这三个节点的公式是如何推出来的啊？比如，为什么第一个节点的是3000-5x=2000，而不能是其他的呢，为什么是5x呢？

    回复
  44. Pingback： 论畏难与惧怕思考 « Yong.Zhang's Blog

  45. total = 3000;

    array[1001];

    每次掉头地点 x 公里 => array[x] += (1000 – 2x);
    => total -= (1000 – 2x);

    每次走完 1000 公里得到的煤的质量 =>
    车上的煤 = MAX(1000, total)
    for (i = 1; i 0; i ++, 车上的煤 –){
    车上的煤 = MAX(1000, 车上的煤 + array[x]);
    array[x] -= MIN(array[x], 1000 – 车上的煤);
    可以选择调头或者不掉头，动态规划问题
    }

    没有验证~~

    回复
  49. Pingback： 再谈“我是怎么招聘程序员的”（下） | Xeno Joshua

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注