(本文来自酷壳网:http://coolshell.cn/articles/4429.html)
题目如下:
你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?
这道题一开始看上去好像是无解的,因为你的火车每一公里就要消耗一吨煤,而到目的地有1000公里,而火车最多只能装1000吨媒。如果你的火车可以全部装下,到目的地也会被全部烧光,一丁点也不剩。所以,很多人的第一反应都是觉得这个不太可能。
如果你一开始就觉得不太可能的话,这是很正常的。不过我不知道你还会不会继续思考下去,如果你不想思考下去了,那么我很为你担忧,因为你可能并不是一个不善于思考的人,而是一个畏难的人,还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。
我一开始也觉得不可能,后来想了一想,想到一个解法可以最多运送500吨煤到市场,方法如下:(希望你先自己想一想再查看这个答案)
查看答案如下:
于是,你最多可以运送500吨煤到市场(当然,火车也回不去了,因为那矿山没有煤了)
好像这样很不错的了,不过还有更好的方法能运更多的媒过去。你知道这个方法吗?可以提示的是,就是以上述这个方法的思路。我先暂时不把答案放上来,你可以自己想想。过两天我把答案放上来。
更新(2011年4月17日):大家都很聪明,533是应该是最优解,大家用了很多种方法阐述了这一过程,我最初的想法和朋友xPacificCoolShell的一致!很高兴看到有更为科学的解法,受教了。另外,还有一些朋友提出火车不能随时随地调头的实际情况,非常不错,所以,以后这题不能用火车运煤了,可能是用马运草更好一点了。;)
我是这样想的:火车运行时,最好让他满载,起始点记为A
第一步,分三次把煤运送到中间点B
第二步,分两次把煤运送到中间点C
第三步,把煤运送到目的地D
第一步:5*(AB) = 1000;解得AB=200
第二步:3*BC = 1000;解得BC=333.
第三步:AB+BC+CD=1000;解得CD=467
因此,做多运送533吨煤到目的地
刚开始我也想到用中途放下返回的问题,但是如何达到最优值,陷入困难。
经过思考,我的解题思路是这样的:首先,要获得最大值,必须在最远的中间”补给点”放下等同其路程的煤作为补给。所以接下来要做的就是,如何让2000吨煤放到最远的地方,同时留下“补给煤”。因为条件限制,所以只能分两次达成上面的目标,第一个补给点,他要消耗的是他路程的5倍的煤,因为他自己消耗两次,第二次送煤的消耗两次,最后一次直达终点的要消耗一次。所以他要在1/5的地方放下,第一个点已经提供补给,所以第二点要补给3次,他自己两次,最后直达的一次。所以是在200+333的地方放下333.所以最后到达的,应该是200+333 = 533. 总数是其他值也可以推导出来了
编程的例子就是:
int sum = 3000;
int load_num = 1000;
int result = 0;
int time = sum / load_num – 1;
for (int i = time; i > 0 ; –i) {
result += load_num / ((i*2) + 1);
}
(来源:http://blog.csdn.net/chentaihan/article/details/6439402)
题目内容:
你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?
这是我在《酷壳》看到的一个面试题,主要是被陈浩的几句话给吸引了,还有就是哥比较喜欢思考,想证实一下哥是否适合做程序。
火车运煤问题分析
表面上看这个问题很难实现,因为火车最多只能载1000吨煤,而行驶1000公里刚好把火车上的1000吨煤烧光。
等我们认真思考之后会发现,可以分段运输。如先运1000吨煤行驶100公里,放下800吨再返回,再运1000吨煤到100公里处,
此时车上还有900吨,再加上100吨煤,车上就有1000吨煤,离终点还有900公里,到终点的时候还剩100吨煤。
老实说哥没有天才的IQ,我先是边看《单身男女》边思考这个问题,差不多用了1个小时没有得出一个结果,也没有弄懂怎么来的5x+3y=2000 (y<=1000/3),以及求x+y的最大值,
回家在吃饭的时候又突然想起这个问题,又边吃饭边思考这个问题,有时放下碗在本子上画画,差不多用了四五十分钟,
哥突然明白了5x+3y=2000,其实应该是5x+3y>=2000,当然也就明白了x+y的最大值,几分钟之后哥又明白了5x>=1000,
最后得出x=200,y=333.333333时x+y得出最大值533.33333333。
-->3次 -->2次 -->1次
A(起点)--------------------------------B----------------------------------C-----------------------------D(终点)
<--2次 <--1次
|--------------------X-----------------------|---------------Y-------------------|--------------Z---------------|
为什么是5x+3y>=2000?
3000/1000=3,将3000吨煤运离原始地点,至少要运三次,因为运输的次数越多烧掉的煤就越多,到终点时剩下的煤就越少,所以把煤运离起始地点一定是3次,也就是5x(往3次,返两次)。
中间必须停在两个地方(B,C)将煤放下,因为到C处的时候,车上的煤最大只能有1000吨,因为火车最多只能运1000吨,多了运不了,用两次运肯定是不可能的。所以从A到C至少烧了3000-1000=2000吨煤,即5x+3y>=2000.
为什么是x+y的最大值?
在C处剩余的煤最多只有1000吨,离终点越近剩下的煤就越多,所以在x+y取最大值的时候,剩下的煤最大。即剩下的煤=1000-Z=1000-(1000-(x+y))=x+y
为什么是5x>=1000?
同理在B处最多还剩2000吨煤,因为在B处时煤的数量还大于2000时,将这2000多吨煤运离B处至少要三次,三次的情况,我们就认为是A-->B,所以在B处至多只能要剩2000吨,即5x>=3000-200=1000.
可能有人会问为什么是3次、2次、1次,而不是3次、一次,同样按照上面的分析,你可以得出3次、1次的情况最多剩余400吨。
3000>=5x+3y>=2000
5x>=1000
求x+y的最大值?
原文:http://www.cnblogs.com/liuzhi/p/3922311.html