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