面试题:火车运煤问题

面试题:火车运煤问题

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

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

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

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

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


查看答案

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

 

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

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

好烂啊有点差凑合看看还不错很精彩 (50 人打了分,平均分: 4.52 )
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

    我发现用纸笔来做的话,我就会失去逻辑思维……(汗颜)

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

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

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

  10. 我解了一个上午,最后得出几个不等式方程,还得用用微分才能解出答案。
    很久都没学习了,数学知识下降很多啊。
    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的最大值即可。要用到微分,都忘了。

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

  11. 三辆火车同时出发:
    第一阶段:在(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)吨(这只是理想状态下的最大值,当然火车中途是不能停车的^_^!)

  12. 用(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吨

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

  14. 因为是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个节点
    总的想法是让火车每次往前运煤都尽量处于满载状态

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

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

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

  18. 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 – 车上的煤);
    可以选择调头或者不掉头,动态规划问题
    }

    没有验证~~

发表回复

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