面试题:火车运煤问题

面试题:火车运煤问题

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

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

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

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

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


查看答案

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

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

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

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

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

    1. 偶然看到这个问题。。。
      想了很久但他答案没公布。。。
      知道看了你的回复,终于知道答案是什么了。。。

  1. 从博客 再谈我是怎么招聘程序员的 来的。
    我的想法就是少走路,多拉货。
    我的做法就是试,但是试的过程就有点像计算机cpu的感觉
    比如,我先从最简单的先拉 x 段距离(x极小)开始,发现 一直到 x为200之前,他们都是等价的,从200 到 1000/3+200也是等价的。
    想完备具体的给出证明,还是不行,脑子没那么清晰,没有把握说这是最好的解(尽管题主说这是最优解),回去再仔细想一想

  2. @shretju

    shretju :
    一种动态规划的方法
    评论里已经有人给出了很简洁的解决方案,下面我想从动态规划的角度给出一种解法:
    假设起始运送货物量为 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不一定是最优的,但已经足够接近了。

    这个方法好,和我简单的想法比较类似。
    我的想法是:把尽可能多的煤运送尽可能多的距离。
    如果煤车能装很多很多,那就直接装上带走了。如果煤堆只剩下<=1000或者说车容量,那么也是直接全装上,走到哪算哪。但是这道题的问题就在于煤堆比车容量多,我的做法是:把所有的煤堆一点一点往前挪。向前移动的步长可以为1公里或0.1公里之类的。那么第一个标记就在旧标记+步长处,然后就让车来回来回地搬过去吧。。。最佳解为533而不是533.33的原因仅仅是因为步长设的不够小。另外,最后搬到中间的时候煤堆只剩1K的时候一股脑的搬到终点也可以视为一步一步向前挪的一种特例:即一次能把全部煤堆都装上车,然后走一个步长,全卸下全装上,再走一步=》合并起来就是一起到终点。
    当然这只是理想的微分情况,实际为了减少装卸损耗的话,如不考虑取余剩下没法带走那部分,那么步长是1还是2还是3都是一样的效果。。。以来回次数为分界,这就可以逐渐合并成大家所说的200+333+527解法了

  3. 这是一道初中数学题, 但是我一直没学会,哈哈!!好像是和曲线有关的一个章节!

  4. 问题的关键是能不能运送半公里就卸货,或者0.1公里,当这个数越小的时候,到达终点的煤就越多。

  5. 抽象:

    本质上是让容量为L的物体在初始补给为n*L的情况下,最大能走多远, 没走1单位距离就消耗1单位补给.

    解答:
    使用递推公式:

    f(1) = 1
    f(2) = f(1) + 1/3
    f(3) = f(2) + 1/5

    f(n) = f(n-1) + 1/(2*n+1)

    通项公式: f(n) = Σ(1/(2*i)+1) (1 <= i <=n)

    题目对应是能走的最远距离减去已知的距离,
    即 (f(3) – 1) * 1000 = 533

    此解法适用于4000吨,5000吨以上的拓展.

  6. Pingback: 运苹果问题
  7. 1、装1000t走200公里,扔下600t,回矿山
    2、装1000t走到200公里处,装200t,走至500公里处,扔下400t,往回走
    3、走到200公里处,走不动了,装上200t,回矿山,此时200公里处还剩200t
    4、装1000t,走至200公里处,装200t,走至500公里处,装400t,走到终点,剩600t

  8. 1、装1000t走200公里,扔下600t,回矿山
    2、装1000t走到200公里处,装200t,再走333公里,扔下334t,往回走
    3、走到200公里处,走不动了,装上200t,回矿山,此时200公里处还剩200t
    4、装1000t,走至200公里处,装200t,走至533公里处,装334t,走到终点,剩533t
    @aaaaaaaaaaaaaaaaaaaaaaaaaa

  9. 我的想法非常极端,每次火车只走一公里,然后就把货物撒下回头去载还没运送的货物,
    比如第一次过程:
    火车满载1000走一公里,把剩下的999扔下回头
    然后又满载1000走一公里,把新带来的999扔下回头,
    。。。三次运送后,货物前进了一公里,共消耗3吨煤,接下来如此类推,
    我最后算出来的结果是833吨
    代码:
    int Cal(int maxload, int dinstance, int total)
    {
    if(dinstance!=0)
    {
    int goBack=total/maxload;
    if(total-maxload*goBack!=0)
    goBack++;
    Cal(maxload,dinstance-1,total-goBack);
    }
    else
    return total;
    }

    int main()
    {
    cout<<Cal(1000,1000,3000);
    return 0;
    }

    当然这非常不现实,不过如果题目没有这种回头限制的话也不能怪我,哈哈哈,当然如果题目中给出的火车公里消耗允许再小点,比如改成没半公里就算一次消耗,也许结果还能更优。

  10. 1、刚开始势必要走三趟,既然如此,就要知道三趟最远能走多远。
    假设要走x,到x之后,煤只剩下2000吨,那么,两次往返,一次往,5x=1000,可以走200公里。
    2、接下来无论如何至少走2趟,同样的道理,一次往返一次往,3x=1000,x=333.33
    3、目前走了533.33公里,剩下1000吨煤,走完剩下的路,最后剩下466.66吨。

  11. 记录一下自己的回答:
    假设可以中途卸货,且卸货过程不消耗任何煤炭。
    运送总量为T吨的煤炭,每公里消耗的煤为c=Ceiling(T/1000)x2-1。这个消耗只适用 运送距离的上限为 d=1000/cost的情况。超过这个上限则需要设立中转站,将剩余的煤集中至此处,然后重新计算c,d。

    即 运送3000吨的煤至200公里或以内的距离,每公里的耗费为5吨。总共能运送3000-总距离x5吨的煤到目的地
    方案为首次装载1000吨的煤上路,到达目的之后卸下1000-总距离x2吨的返回起始点。再重复一次,返回起始点。再装载1000吨煤,到达后卸下1000-总距离吨煤。

    运送3000吨的煤至200公里以上,533.3333公里或以内的距离,总共能运送2000-(总距离-200)x3吨煤到达目的地。
    方案为,在200公里处设立一中转站,重复上一个方案啊。然后用类似的方案从中转站处运送煤至终点。

    运送至533.3333公里以上,1533.3333公里或以内的距离,总共能运送1000-(总距离-200-333.3333)吨煤。
    方案为在200公里和533.3333公里处分别设立中转站。

    这个思路的运输距离上限为1533.3333公里。

发表回复

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