229
一道麵試題：火車運煤問題
這個可能是一個比較經典的智力題了，和以前的那個《賽馬問題》很相似，其題目如下：
你是山西的一個煤老板，你在礦區開采了有3000噸煤需要運送到市場上去賣，從你的礦區到市場有1000公裏，你手裏有一列燒煤的火車，這個火車最多隻能裝1000噸煤，且其能耗比較大——每一公裏需要耗一噸煤。請問，作為一個懂編程的煤老板的你，你會怎麼運送才能運最多的煤到集市？
這道題一開始看上去好像是無解的，因為你的火車每一公裏就要消耗一噸煤，而到目的地有1000公裏，而火車最多隻能裝1000噸媒。如果你的火車可以全部裝下，到目的地也會被全部燒光，一丁點也不剩。所以，很多人的第一反應都是覺得這個不太可能。
如果你一開始就覺得不太可能的話，這是很正常的。不過我不知道你還會不會繼續思考下去，如果你不想思考下去了，那麼我很為你擔憂，因為你可能並不是一個不善於思考的人，而是一個畏難的人，還有可能是一個容易放棄的人。這對於你做好 一個需要大量思考的工作的程序員來說可能並不適合。
我一開始也覺得不可能，後來想了一想，想到一個解法可以最多運送500噸煤到市場，方法如下：（希望你先自己想一想再查看這個答案）
？
？
？
？
？
？
？
？
？
？
？
？
？
？
？
？
答案：
- 裝1000噸煤，走250公裏，扔下500噸煤，回礦山。
- 裝1000噸煤，走到250公裏處，拿起250噸煤繼續向前到500公裏處，扔下500噸煤，回礦山。此時火車上還有250噸，再加上在250公裏處還有250噸煤，所以，火車是可以回礦山的。
- 裝上最後1000噸煤，走到500公裏處，裝上那裏的500噸煤，然後一直走到目的。
於是，你最多可以運送500噸煤到市場（當然，火車也回不去了，因為那礦山沒有煤了）
其他方法：
- 火車肯定要從起點出發3次（因為每次最多運1000）；
- 火車前兩次回到起點要用完車上存煤（否則是浪費）。
- 初步方案：火車前兩次都運到某點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點回頭一次。然後想到第三個特征：
-
火車回程要盡可能短。使火車回頭的原因是火車容量為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。
最後更新：2017-04-03 18:51:55