面试题:火车运煤问题
这个可能是一个比较经典的智力题了,和以前的那个《赛马问题》很相似,其题目如下:
你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?
这道题一开始看上去好像是无解的,因为你的火车每一公里就要消耗一吨煤,而到目的地有1000公里,而火车最多只能装1000吨媒。如果你的火车可以全部装下,到目的地也会被全部烧光,一丁点也不剩。所以,很多人的第一反应都是觉得这个不太可能。
如果你一开始就觉得不太可能的话,这是很正常的。不过我不知道你还会不会继续思考下去,如果你不想思考下去了,那么我很为你担忧,因为你可能并不是一个不善于思考的人,而是一个畏难的人,还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。
我一开始也觉得不可能,后来想了一想,想到一个解法可以最多运送500吨煤到市场,方法如下:(希望你先自己想一想再查看这个答案)
【查看答案】
好像这样很不错的了,不过还有更好的方法能运更多的媒过去。你知道这个方法吗?可以提示的是,就是以上述这个方法的思路。我先暂时不把答案放上来,你可以自己想想。过两天我把答案放上来。
更新(2011年4月17日):大家都很聪明,533是应该是最优解,大家用了很多种方法阐述了这一过程,我最初的想法和朋友xPacificCoolShell的一致!很高兴看到有更为科学的解法,受教了。另外,还有一些朋友提出火车不能随时随地调头的实际情况,非常不错,所以,以后这题不能用火车运煤了,可能是用马运草更好一点了。;)
(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)
《面试题:火车运煤问题》的相关评论
看了答案才发现,原来火车回程,是不需要烧煤的啊……我说我怎么做不出来……
偶然看到这个问题。。。
想了很久但他答案没公布。。。
知道看了你的回复,终于知道答案是什么了。。。
当然要烧了
从博客 再谈我是怎么招聘程序员的 来的。
我的想法就是少走路,多拉货。
我的做法就是试,但是试的过程就有点像计算机cpu的感觉
比如,我先从最简单的先拉 x 段距离(x极小)开始,发现 一直到 x为200之前,他们都是等价的,从200 到 1000/3+200也是等价的。
想完备具体的给出证明,还是不行,脑子没那么清晰,没有把握说这是最好的解(尽管题主说这是最优解),回去再仔细想一想
@shretju
这个方法好,和我简单的想法比较类似。
我的想法是:把尽可能多的煤运送尽可能多的距离。
如果煤车能装很多很多,那就直接装上带走了。如果煤堆只剩下<=1000或者说车容量,那么也是直接全装上,走到哪算哪。但是这道题的问题就在于煤堆比车容量多,我的做法是:把所有的煤堆一点一点往前挪。向前移动的步长可以为1公里或0.1公里之类的。那么第一个标记就在旧标记+步长处,然后就让车来回来回地搬过去吧。。。最佳解为533而不是533.33的原因仅仅是因为步长设的不够小。另外,最后搬到中间的时候煤堆只剩1K的时候一股脑的搬到终点也可以视为一步一步向前挪的一种特例:即一次能把全部煤堆都装上车,然后走一个步长,全卸下全装上,再走一步=》合并起来就是一起到终点。
当然这只是理想的微分情况,实际为了减少装卸损耗的话,如不考虑取余剩下没法带走那部分,那么步长是1还是2还是3都是一样的效果。。。以来回次数为分界,这就可以逐渐合并成大家所说的200+333+527解法了
这是一道初中数学题, 但是我一直没学会,哈哈!!好像是和曲线有关的一个章节!
问题的关键是能不能运送半公里就卸货,或者0.1公里,当这个数越小的时候,到达终点的煤就越多。
@楠楠
思路不错!
抽象:
本质上是让容量为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吨以上的拓展.
1、装1000t走200公里,扔下600t,回矿山
2、装1000t走到200公里处,装200t,走至500公里处,扔下400t,往回走
3、走到200公里处,走不动了,装上200t,回矿山,此时200公里处还剩200t
4、装1000t,走至200公里处,装200t,走至500公里处,装400t,走到终点,剩600t
1、装1000t走200公里,扔下600t,回矿山
2、装1000t走到200公里处,装200t,再走333公里,扔下334t,往回走
3、走到200公里处,走不动了,装上200t,回矿山,此时200公里处还剩200t
4、装1000t,走至200公里处,装200t,走至533公里处,装334t,走到终点,剩533t
@aaaaaaaaaaaaaaaaaaaaaaaaaa
牛逼@~
@scaiz
问一下,斜率分别为-5,-3,-1。这几个斜率是怎么来的?谢谢
我的想法非常极端,每次火车只走一公里,然后就把货物撒下回头去载还没运送的货物,
比如第一次过程:
火车满载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;
}
当然这非常不现实,不过如果题目没有这种回头限制的话也不能怪我,哈哈哈,当然如果题目中给出的火车公里消耗允许再小点,比如改成没半公里就算一次消耗,也许结果还能更优。
满载1000丢999火车就回不去啦,丢998?
历史告诉我们:客户就是上帝,那是真的。
@Zingphoy
小哥你好像没有把回头的消耗算上
小哥你好像没有把回头的消耗算上
@抱兔兔
。。。我还没看答案,算出的是533,照你这么说的话,答案有误?
运出来五百的办法想到了,在回去也要消耗煤的条件下。
1、刚开始势必要走三趟,既然如此,就要知道三趟最远能走多远。
假设要走x,到x之后,煤只剩下2000吨,那么,两次往返,一次往,5x=1000,可以走200公里。
2、接下来无论如何至少走2趟,同样的道理,一次往返一次往,3x=1000,x=333.33
3、目前走了533.33公里,剩下1000吨煤,走完剩下的路,最后剩下466.66吨。
剩 533.33
第一页的答案都不对。
记录一下自己的回答:
假设可以中途卸货,且卸货过程不消耗任何煤炭。
运送总量为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公里。