面试题:火车运煤问题

面试题:火车运煤问题

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

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

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

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

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


查看答案

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

 

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

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

好烂啊有点差凑合看看还不错很精彩 (50 人打了分,平均分: 4.52 )
Loading...

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

  1. 各位,我昨晚想了很久,但是一直没想到最优解533怎么算的。
    首先,我把每段停车的地点记为(

    Fidel :
    这个问题,首先要考虑什么情况才是最优情况。依照题意,火车只要活动就会消耗煤,所以每次火车出发时只有满载才是最优情况,并且不能扔掉煤不要。有了这个前提,我们接着往下分析。
    求得最优解的过程肯定要减少火车折返的所消耗的总路程。由于全长1000公里,所以我们肯定需要采用多次中转的方式来运送,中转的过程中随着煤的消耗,折返的次数也会减少,所以我们要尽量减少多次折返时所前进的距离。
    只有一辆火车,每次出发都是满载,那么我们需要3次将煤运送到下一站,在此期间需要折返5次。下一站出发如果要满足最优条件,则此期间需要消耗掉一车或者两车煤,根据第二段的分析,我们应该减少5次折返时所前进的距离,故此次运送需要消耗1车煤。1000/5 = 200公里。依次类推,第二次运送折返3次,需要消耗1车煤,前进距离为1000/3 = 333.33……公里。第三次由于仅剩一车煤,满载前进,出去路途消耗,到达终点剩余煤为1000-(1000-(200+333.33) = 533.3333吨。

    昨天想了两个小时,才想到了S(i+1)=S(i)-(2*【S(i)/1000】+1)*(L(i+1)-L(i))这个公式。Li每次停车放煤相对于起点的距离。S(i)是每个停车点最终剩下的煤…
    但是一直解就是解不出…

  2. 较快算法:
    3000吨媒想办法变成2000吨->(3000-2000)/5=200,即分三次运送200公里,现在离终点还剩800公里;
    2000吨媒想办法变成1000吨->(2000-1000)/3=333,即分两次运送333公里,现在离重点还剩467公里;
    最后一次搞定:1000-467=533;

  3. @守望
    这个问题很好理解,因为火车有消耗,所以必须让其尽可能的装满在路上行驶(像资本家剥削工人一样),由3000/1000 = 3知,必须到起点三次;且到第一个中转站时也能使其装满,则必是煤车到此地时有煤2000 车往返五次,(来3回2)第一中转点据地点1000/5=200米,同理第二中转点有煤1000 往返第一中转点三次,距离第一中转点1000/3=333.333米;最后在第二中转点满载到终点。 知道这个原理的话,当有nK吨煤时也很好求解了~~

  4. 很好的一道题,但对于本题来说,火车能卸煤的地点一般都是固定的,那么多吨煤在铁轨附近说卸就卸啊。。。

  5. 装1000吨煤,走250公里,扔下500吨煤,回矿山。
    装1000吨煤,走到250公里处,拿起250吨煤继续向前到500公里处,扔下500吨煤(这里有错,应该是扔下250吨,因为此时火车上只有750吨煤,扔500吨,则会不去了),回矿山。此时火车上还有250吨,再加上在250公里处还有250吨煤,所以,火车是可以回矿山的。
    装上最后1000吨煤,走到500公里处,装上那里的500吨煤,然后一直走到目的。
    于是,你最多可以运送500吨煤到市场(当然,火车也回不去了,因为那矿山没有煤了)

  6. 首先,1/3+1/7 +…+ 1/(2n-1) < 1,所以煤场有再多的煤运到市场也不会超过1吨,所以下面的的解法对煤任意多都是没有问题的,通过这个极限,还可以求出最多能运多少到市场。
    coal=3000
    left=1000
    while (coal != 1000)
    {
    left -= 1000 / ((coal/1000)*2 – 1); /*消耗1000吨煤能使N吨煤移动的距离*/
    coal -= 1000;
    }
    left就是答案了

  7. 我的思路是这样的:让火车最大负重(1000吨),进行最小消耗(每次只走1公里),那么他就可以卸下998吨,因为还要回城需要1吨煤,所以只能放下998吨。那么每公里火车需要消耗2吨煤,一共1000公里,共需消耗2000吨,最后运到城里的就是3000吨煤。

  8. GretaKing :
    我的思路是这样的:让火车最大负重(1000吨),进行最小消耗(每次只走1公里),那么他就可以卸下998吨,因为还要回城需要1吨煤,所以只能放下998吨。那么每公里火车需要消耗2吨煤,一共1000公里,共需消耗2000吨,最后运到城里的就是3000吨煤。

    擦,忘了折返次数了,我这个解题思路应该是消耗煤最多的,5000吨都不够烧的。

  9. 一种动态规划的方法
    评论里已经有人给出了很简洁的解决方案,下面我想从动态规划的角度给出一种解法:
    假设起始运送货物量为 t,终点路程为 s, 火车容量为 c, 可以运抵终点的最多货物量为函数 F(t,s).
    在写出递归式前,先列举3种基本情况:(1)t<s: 货物量不足以运送到此距离,所以F(t,s)=0; (2)s<t<c: 火车一次就可以装完货物,所以F(t,s)=t-s; (3)2s<cc使得火车一次无法运完,但因为c>2s,火车可以采用往返的方式多次运输,这种情况下最优的方式就是减少总共往返的次数,也就是直接运到终点而不在中间站卸货,所以F(t,s)=(t/c-1)*(c-2s)+(c-s)

    有了这三种基本情况,接着给出递归式: F(t,s) = max{ F( F(t,i) , s-i ) } for all 1=<i<s.
    递归式的意思就是,整个问题可以分成两部分,首先从起始点以最优运货量运到位置 i,然后再从位置 i 将当时剩余的货物量以最优方式运到终点。然后再递归的解决两个字问题。至于这个问题是否满足“最优子问题”的准测,大家可以很容易证明。

    最后程序结果确实就是大家给出的 533吨。 即先运到200m处,剩余2000吨,再运到533m处,剩余1001吨,最后运到终点,剩余533吨。
    我在解的时候把火车可停的位置离散化了,也就是只能停在整数距离上,所以533不一定是最优的,但已经足够接近了。

  10. 顺便把python的代码也贴上:
    C=1000
    T=3000
    S=1000
    transport=[[0]*(S+1) for i in range(T+1)]
    offloadpoint=[[[0,0] for j in range(S+1)] for i in range(T+1)]
    #initialize the basic cases
    #(1)the basic case:t<=s makes transport near half part are 0's
    #(2)for the second basic case
    for s in range(1,C):
    for t in range(s+1,C+1):
    transport[t][s]=t-s
    offloadpoint[t][s]=[s,0]
    #(3)for the third one
    for t in range(C+1,T+1):
    for s in range(1,C/2+1):
    transport[t][s]=(t/C-1)*(C-2*s)+(C-s)
    offloadpoint[t][s]=[s,0]
    for s in range(1,S+1):
    for t in range(s+1,T+1):
    if t<=C or (sC): #either the second or the third basic case
    continue
    print ‘\r’,t,s,
    min_points_num=S
    for i in range(1,s):
    x=transport[transport[t][i]][s-i]
    points_num=offloadpoint[t][i][1]+offloadpoint[transport[t][i]][s-i][1]+1
    if x>transport[t][s] or (x==transport[t][s] and points_num<min_points_num):
    transport[t][s]=x
    offloadpoint[t][s]=[i,points_num]
    min_points_num=points_num

    print '\n'
    print "the maximum amount is ",transport[T][S]

    #recursively print out the intermediate offloading points
    def print_offloadpoints(amount,src,dst):
    point=offloadpoint[amount][dst-src][0]
    if point==0:
    return -1 #no offload point
    elif point==(dst-src):
    print src+point,transport[amount][dst-src]
    return 0
    print_offloadpoints(amount,src,src+point)
    print_offloadpoints(transport[amount][point],src+point,dst)
    return 1

    print_offloadpoints(T,0,S)

  11. 不用切三段这么麻烦,就一点点的走就行。假设不用每次都走一公里,也就是说,走半公里就用0.5吨煤的话:

    开始是3000吨煤,每次走一公里要用5吨煤:三次去,两次回。
    走到1000/ 5 = 200公里的时候,只有2000吨煤了,这时候每次前进1公里要3吨煤:两次去,一次回。
    走到1000/3 = 333.33公里的时候,只有1000吨煤了,直接向前走就行了。

    这时候,一共走过了1000/ 5+1000/3=200+333.33=533.33公里。每走1公里要耗费1吨煤,而路程正好是1000公里,所以走过的这些公里就是到最后可以剩下的吨数。是533.33

  12. 首先想到最优解的两个特征:1,火车肯定要从起点出发3次(因为每次最多运1000);2,火车前两次回到起点要用完车上存煤(否则是浪费)。
    初步方案:火车前两次都运到某点x,卸下1000-2x,然后用x煤回去,第三次到x点时,车上有1000-x,然后装上x点的煤,若3000-5x不超过1000,直接到终点,用3000-5x=1000的临界条件算得x=400,这也是火车到达终点所剩下的煤。
    若3000-5x超过1000,此时与原问题类似,但初始煤变为3000-5x,路程变为1000-x,我们需要选择下一个存煤点,与x点距离y,然后在y点回头一次。
    然后想到第三个特征:3,火车回程要尽可能短。使火车回头的原因是火车容量为1000,理想状况为火车每次出发都装满1000的煤,所以火车第三次到达x点时共有煤3000-5x=2000,求得x=200;火车第二次到达y点时站点有存煤1000-2y,火车有煤1000-y,共计2000-3y,理想状况为2000-3y=1000,y=333,火车到达终点剩下煤1000-(1000-x-y)=533。

  13. aoneatwo :
    首先想到最优解的两个特征:1,火车肯定要从起点出发3次(因为每次最多运1000);2,火车前两次回到起点要用完车上存煤(否则是浪费)。
    初步方案:火车前两次都运到某点x,卸下1000-2x,然后用x煤回去,第三次到x点时,车上有1000-x,然后装上x点的煤,若3000-5x不超过1000,直接到终点,用3000-5x=1000的临界条件算得x=400,这也是火车到达终点所剩下的煤。
    若3000-5x超过1000,此时与原问题类似,但初始煤变为3000-5x,路程变为1000-x,我们需要选择下一个存煤点,与x点距离y,然后在y点回头一次。
    然后想到第三个特征:3,火车回程要尽可能短。使火车回头的原因是火车容量为1000,理想状况为火车每次出发都装满1000的煤,所以火车第三次到达x点时共有煤3000-5x=2000,求得x=200;火车第二次到达y点时站点有存煤1000-2y,火车有煤1000-y,共计2000-3y,理想状况为2000-3y=1000,y=333,火车到达终点剩下煤1000-(1000-x-y)=533。

    这题目可以推广为容量k火车要运载Nk煤到距离k点。那么每个中转站点x为N’k-(2N’-1)x=(N’-1)k,N’递减。证明最优解的思路可以从证明火车每次回程最短或者火车每消耗k煤使剩余煤移动距离最远入手。

  14. 拉三次,第一次的在200位置,因为1000/5,因为来回5次到第一的点.第二次放在333.333位置.因为来回3次到这个点,那第三次到终点剩下533.3333喽.

  15. 其实题目还忽略了火车的加速度,如果考虑进去的话可以利用火车的加速度省下不少煤,当然这个说法有点较真,还是马吃草比较无争议。

  16. 刚看到题目也有无解的感觉,一转念觉得有问题,不像看起来那么直接。只要满足几个原则就可以确定解了,题出什么无所谓,问题都一类。
    一、火车可掉头。(就能分段拿煤换路程了)
    二、从每个节点运出煤都必须无剩余。(哪怕剩余的一点点煤也能使火车带煤向前推进)
    三、完成一个节点的运送到达下一节点时。重组装煤时,剩余总煤量应为车载负荷的整数倍。(不出现半车煤起运的情况)
    四、满足三原则下,两节点之间消耗的煤应尽量少。(少走2x的路程啊)
    原则定出来思路就出来了。

  17. 刚看到题目也有无解的感觉,一转念觉得有问题,不像看起来那么直接。只要满足几个原则就可以确定解了,题出什么无所谓,问题都一类。问题很好想,没计算量。结果:分段运,第一个节点在200处,第二个在200 333.33处,答案是533.33。想对了就很简单。
    这题想解最优是有运送原则的(如下):
    一、火车可掉头。(就能用分段的方式拿煤换路程了,货物煤是可以一点一点装车的,这样才行*^_^*)
    二、从每个节点运出煤都必须无剩余。(若剩余,哪怕剩余的一点点煤也能使火车带煤向前推进。浪费!)
    三、完成一个节点的运送到达下一节点时。剩余总煤量应为车载负荷的整数倍。(确保再运向下一节点不出现半车煤起运的情况,耗煤代价一样当然要多运才行,半车就运走太不环保了-_-||)
    四、满足原则三的情况下,两节点之间消耗的煤应尽量少。(本题就少走2x的路程啊,拉五趟比拉两趟费劲多了T_T)
    原则定出来思路就出来了。原则一二基本废话,是地球人都能想到。一看原则三四,说明每到一个节点就应该损失一个车辆负载(不能不损失煤吧,是满足原则四的),这里到第一个节点时损失1000的煤拉了五趟单程,当然就在200处了。后面同理,再损失1000拉三趟单程,就到533.33处了,这时还有1000的煤。规律就是这样简单,原则想通就好。
    打住,完!~zZ

  18. 三千吨的煤,搭上一列火车,费了很多劲,最后送达500吨到市场。如果我是煤老板,肯定不会同意这么干。因为这500吨要买多少钱才能把成本赚回来?定价太高了能卖出去吗?如果卖不出去还不如放在矿区算了。呵呵。我觉得程序员的算法不管多么高超,也不能忘记解决问题的目的是要提供社会价值。

  19. x点是200,从200的点到y点,消耗煤应该是y-200。火车第二次到达y点时站点有存煤1400-2y,火车有煤1200-y,共计2600-3y,y点应该是533。最后,从y点出发,1000吨的煤,消耗467,到达目的地后,剩下煤533。我是这么分析的,不知道对不对,求赐教。@aoneatwo

  20. 受教了,我只想到了500。另外我想说的是博主的文章非常不错,是我看过的最好中文技术类博客之一,每读一篇,都有共鸣,继续关注。

  21. 重载火车可以头尾都有火车头的,题目改改重载火车每公里1吨,空载火车每公里0.7,大家哭去吧

  22. var t=3000; //total coals
    var y; //final left coals
    var s=1000; // distance
    var c=1; //per consume per mile
    var b=1000; // most volume per travel;
    var n = Math.floor(t/b);
    console.log(“n = ” + n);
    var a = new Array(); // for store n stage’s movement distance
    a[0] = (t – n * b) / (2 * n + 1); // for per travel full volume, first consume the remainder coals
    var i = 1;
    var sum = a[0];
    /*find the final*/
    while (sum < s )
    {
    a[i] = b/(2 * (n-i+1) – 1);
    sum += a[i];
    i++;

    }
    console.log("i = " + i);
    console.log("sum = " + sum);
    var Consume = 0;
    /*前i-1次运输消耗量*/
    for (var j = 0; j < i-1; j++) {
    console.log("第"+ (j+1) +"运输距离:"+ a[j]);
    Consume += a[j]*(2 * (n-j+1) – 1);
    }
    console.log("前"+ (i – 1) +"次运输消耗量"+Consume);
    /*前i次总运输消耗量*/
    Consume += (2*(n-i+2)-1)*(a[i-1]-(sum – s));
    console.log("前"+i+"次总运输消耗量"+Consume);

    y = t – Consume;

    console.log("终点剩余煤炭数: " + y);

  23. 程序还没写出来, 至于为什么可以这么跑也不是特清楚:
    1、先运1000t煤到250km处, 放500t煤,然后返回
    2、再运1000t煤到250km处, 放500t煤,然后返回
    3、再运1000t煤到500km处, 放250t煤,返回250km处
    4、从250km处运1000t煤到500km处, 到500km处,载上250t煤
    5、到1000km处, 放下500t煤。。

  24. 我们采取最浪费时间的解决方案,火车前进1公里,然后放下998吨,然后回来,这样第三次到放货点的时候已经火车都走了2.5公里,用了2.5吨煤。然后继续前行1公里,放下996吨,再回来,这样还是用了2.5吨。直到我们的货物只有2000吨的时候,我们只需要1.5吨煤就可以推进1公里了。到距离只有1000吨的时候,我们每公里消耗煤1吨。这样算下来就是
    1000/2.5+1000/1.5=400+666.5>1000了,所以消耗的就是400*2.5+600×1.5=1900,运到终点就是1100吨货

  25. @paul.xu

    天哪,似乎还真是这样,你的分析很有道理,得出的数值也更大,哈哈!
    只有把煤搬上搬下的工人们倒霉了 :)

  26. paul.xu :
    我们采取最浪费时间的解决方案,火车前进1公里,然后放下998吨,然后回来,这样第三次到放货点的时候已经火车都走了2.5公里,用了2.5吨煤。然后继续前行1公里,放下996吨,再回来,这样还是用了2.5吨。直到我们的货物只有2000吨的时候,我们只需要1.5吨煤就可以推进1公里了。到距离只有1000吨的时候,我们每公里消耗煤1吨。这样算下来就是
    1000/2.5+1000/1.5=400+666.5>1000了,所以消耗的就是400*2.5+600×1.5=1900,运到终点就是1100吨货

    不对不对,超过 2000 吨时,每公里要消耗 5 吨煤,超过 1000 吨时是 3 吨煤/公里,最终结果只能运 467 吨煤到市场

  27. 虽然你们说533是最优解但是那些煤要存放还要搬上火车 这些不要成本的???,3000吨就算运出了533吨但那些人工成本 多少?你还要找地方存放谁有这么大的地方给你存放煤炭???租地方???还是自己建场地???现在煤炭多少钱一吨???如果你是老板你怎么考虑额外的成本计算???

  28. function geta1X(a0, s, c, k) {//a0,初始值,s,距离,c,火车容量,k,能耗系数,
    //返回值,到达目的地的剩余量
    var x, dx;
    x = 0;
    while (a0 > c && x<s) {
    dx = (a0 – c * (Math.ceil(a0 / c) – 1)) / (k * (2 * (Math.ceil(a0 / c) – 1) + 1));
    x += dx;
    a0 = a0 – k * dx*((2 * (Math.ceil(a0 / c) – 1) + 1));
    alert("这一次将所有煤运送到离出发点" + x+";剩余煤"+a0); //中间结果
    }
    return c – (s – x) * k; //最终结果
    }
    var r = geta1X(3000, 1000, 1000, 1);
    alert(r);
    var r = geta1X(3500, 1200, 800, 0.5); //
    alert(r);
    这里是最后一个例子的结果:{
    这一次将所有煤运送到离出发点66.66666666666667;剩余煤3200
    这一次将所有煤运送到离出发点295.23809523809524;剩余煤2400
    这一次将所有煤运送到离出发点615.2380952380952;剩余煤1600
    这一次将所有煤运送到离出发点1148.5714285714284;剩余煤800
    最终774.2857142857142}

    原发于CSDN 博客。
    http://blog.csdn.net/wzhiyuan/article/details/8064577

    另外,经常看楼主的博客,受益非浅。

  29. 后来又研究了一下,我上面说的不完全正确,在最后一次不需要返回的情况下,用这个公式可以的,如果需要返回,只有用我博客中说的极限公式了。
    function geta1(a0, s, dx, c, k) {
    var a1;
    for (var i = 0; i < s / dx; i++) {
    a1 = a0 – k * dx * (2 * (Math.ceil(a0 / c) – 1) + 1);
    a0 = a1;
    }
    return a1;
    }

    // alert(geta1(3000, 1000, 0.1, 1000, 1));
    // alert(geta1(5000, 10, 0.1, 1000, 1));

  30. 不好意思,又来了。我最后研究了一下,发现原来的例子出错了,
    最终结果如下,
    function geta1X2(a0, s, c, k) {
    var x, dx;
    x = 0;
    while (a0 > c && x s){
    dx = s-x;
    }
    a0 = a0 – k * dx * ((2 * (Math.ceil(a0 / c) – 1) + 1));
    x += dx;
    alert(“这一次将所有煤运送到离出发点” + x + “;剩余煤” + a0); //中间结果

    }
    return a0; //最终结果
    }

    geta1X2(5500,700,1000,0.5);
    结果如下,
    这一次将所有煤运送到离出发点90.9090909090909;剩余煤5000

    这一次将所有煤运送到离出发点313.13131313131316;剩余煤4000

    这一次将所有煤运送到离出发点598.8455988455989;剩余煤3000

    这一次将所有煤运送到离出发点700;剩余煤2747.1139971139974

    如果博主看到,将我无用的上面两条删除吧。谢谢。
    经常在博主这里看文章,非常受益。

  31. @aoneatwo
    2000-3y=1000,算出来结果应该不是333,因为当y=333时, 最后一车的吨数为2000-3y=1001,这个吨数大于一车的容量,一车装不下,那么最后一步就不能成功执行

  32. 一看到这题粗略想一想发现可能是道物理题:
    如果煤老板守时是真命题的话,假定 火车 的速度为匀速。那么:
    水平方向受力平衡:有
    μMg = F牵
    可见牵引力和火车的重量是成正比关系,而
    W = F牵 * S
    所以火车消耗的能量与重量是有关系的。 假定“每一公里需要耗一吨煤”是满载时所消耗的能量,那么,这时:
    P = (1000kg * q J/kg)/(1000m/v m/s) = vq W
    而P = F牵 * v 联立第一个公式,于是:
    μMg = q
    汗,煤炭的热值是固定的(原煤 20934千焦/公斤),μ 受材料本身因素影响而不变。M是给定的,那么我们可以求出
    μ = 0.00214,gg了下发下这摩擦系数是低于正常值的(http://zhidao.baidu.com/question/130489014.html)。

    钻个牛角尖,这毕竟是道面试题~ 工程上真要做的话就得先积分了。领悟这道题精髓就行了:)

  33. @Submarine
    其实我一直纠结于为什么需要把两个中间点一个设为2000 一个设为1000. 想了想是因为每一次需要满载才能达到最优。

  34. 呵呵,这题目其实很有哲理,人的懂得回头啊~
    大概与以前一个过桥类题目有点相似思路,大概意思是,一座桥长1500米,你2分钟最多走800米,桥中间每两分钟都有人出来看下,发现有人在走,立马让他回头阻止他过桥。

发表回复

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