一個火車運煤算法的思考

image.png

一、問題描述

你是山西的一個煤老闆，你在礦區開采了有3000噸煤需要運送到市場上去賣，從你的礦區到市場有1000公裡，你手裡有一列燒煤的火車，這個火車最多隻能裝1000噸煤，且其能耗比較大――每一公裡需要耗一噸煤。

請問，作為一個懂程式設計的煤老闆的你，你會怎麼運送才能運最多的煤到集市？

二、思考過程

這道題一開始看上去好像是無解的，因為你的火車每一公裡就要消耗一噸煤，而到目的地有1000公裡，而火車最多隻能裝1000噸媒。如果你的火車可以全部裝下，到目的地也會被全部燒光，一丁點也不剩。是以，很多人的第一反應都是覺得這個不太可能。

三、結論：

• 裝1000噸煤，走250公裡，扔下500噸煤，回礦山。
• 裝1000噸煤，走到250公裡處，拿起250噸煤繼續向前到500公裡處，扔下500噸煤，回礦山。此時火車上還有250噸，再加上在250公裡處還有250噸煤，是以，火車是可以回礦山的。
• 裝上最後1000噸煤，走到500公裡處，裝上那裡的500噸煤，然後一直走到目的。

同學們一定還有更好的方案，請集思廣益！！！