面试题：火车运煤问题
这个可能是一个比较经典的智力题了，和以前的那个《赛马问题》很相似，其题目如下：
你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
这道题一开始看上去好像是无解的，因为你的火车每一公里就要消耗一吨煤，而到目的地有1000公里，而火车最多只能装1000吨媒。如果你的火车可以全部装下，到目的地也会被全部烧光，一丁点也不剩。所以，很多人的第一反应都是觉得这个不太可能。
如果你一开始就觉得不太可能的话，这是很正常的。不过我不知道你还会不会继续思考下去，如果你不想思考下去了，那么我很为你担忧，因为你可能并不是一个不善于思考的人，而是一个畏难的人，还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。
我一开始也觉得不可能，后来想了一想，想到一个解法可以最多运送500吨煤到市场，方法如下：（希望你先自己想一想再查看这个答案）
【查看答案】
好像这样很不错的了，不过还有更好的方法能运更多的媒过去。你知道这个方法吗？可以提示的是，就是以上述这个方法的思路。我先暂时不把答案放上来，你可以自己想想。过两天我把答案放上来。
更新（2011年4月17日）：大家都很聪明，533是应该是最优解，大家用了很多种方法阐述了这一过程，我最初的想法和朋友xPacificCoolShell的一致！很高兴看到有更为科学的解法，受教了。另外，还有一些朋友提出火车不能随时随地调头的实际情况，非常不错，所以，以后这题不能用火车运煤了，可能是用马运草更好一点了。;)
(43 人打了分，平均分： 4.84 )
Loading ...
@无知
left 不是答案，得用1000-left;
首先想到最优解的两个特征：1，火车肯定要从起点出发3次（因为每次最多运1000）；2，火车前两次回到起点要用完车上存煤（否则是浪费）。
初步方案：火车前两次都运到某点x，卸下1000-2x，然后用x煤回去，第三次到x点时，车上有1000-x，然后装上x点的煤，若3000-5x不超过1000，直接到终点，用3000-5x=1000的临界条件算得x=400，这也是火车到达终点所剩下的煤。
若3000-5x超过1000，此时与原问题类似，但初始煤变为3000-5x，路程变为1000-x，我们需要选择下一个存煤点，与x点距离y，然后在y点回头一次。
然后想到第三个特征：3，火车回程要尽可能短。使火车回头的原因是火车容量为1000，理想状况为火车每次出发都装满1000的煤，所以火车第三次到达x点时共有煤3000-5x=2000，求得x=200；火车第二次到达y点时站点有存煤1000-2y，火车有煤1000-y，共计2000-3y，理想状况为2000-3y=1000，y=333，火车到达终点剩下煤1000-（1000-x-y）=533。
这题目可以推广为容量k火车要运载Nk煤到距离k点。那么每个中转站点x为N’k-(2N’-1)x=(N’-1)k，N’递减。证明最优解的思路可以从证明火车每次回程最短或者火车每消耗k煤使剩余煤移动距离最远入手。
533完胜
拉三次，第一次的在200位置，因为1000／5，因为来回5次到第一的点.第二次放在333.333位置.因为来回3次到这个点，那第三次到终点剩下533.3333喽.
其实题目还忽略了火车的加速度，如果考虑进去的话可以利用火车的加速度省下不少煤，当然这个说法有点较真，还是马吃草比较无争议。
这个题目有问题吧 难道回程不要烧煤的？好像这里都没提到吧？