火車運(yùn)煤?jiǎn)栴}
（可
參見原帖），你是山西煤老板，你開采了3000噸煤需要運(yùn)送到市場(chǎng)上去賣，從你的礦區(qū)到市場(chǎng)有1000公里，你手里有一列燒煤的火車，這個(gè)火車最多只能裝1000噸煤，且其能耗比較大——每一公里需要耗一噸煤。請(qǐng)問，作為一個(gè)懂編程的煤老板的你，你會(huì)怎么運(yùn)送才能運(yùn)最多的煤到集市？
這個(gè)題的其他形式為，驢子吃蘿卜，駱駝吃香蕉，而我的問題是，如果你想運(yùn)1000噸煤到集市，最少需要初始多少噸煤？
這個(gè)題的解答并不難，有很多網(wǎng)友都給出了答案，但是想說清楚道理還是比較繞彎。如果想做編程做模擬，代碼很簡(jiǎn)單，但是有一些邊界條件、約束條件、中間過程也很繞，所以把這個(gè)不是編程題的編程題放在這里解答一下，供參考。
根據(jù)題意可知有三種運(yùn)輸方式，分別是往返兩次加一次單程，成本為5；往返一次加一次單程，成本為3；一次單程，成本為1. 下面簡(jiǎn)稱T5，T3，T1.
首先給出最優(yōu)策略1：用完所有能源，也就是運(yùn)到終點(diǎn)的能源 + 路上消耗的能源=3000。否則，不論剩余多少能量，我們總可以后退一點(diǎn)，再多裝一些，把剩余能量的中的一部分送到終點(diǎn)。
下面引入運(yùn)輸能力這個(gè)概念：
以T3舉例，從起點(diǎn)向終點(diǎn)方向走2趟，最大可裝載2000，運(yùn)到距離為delta的某點(diǎn)之后，最大剩余2000-delta，因此稱T3的運(yùn)輸能力C3 = 2000-delta <= 2000，(delta >= 0)。也就是說，T3最多能運(yùn)送不超過2000的能量，超過2000就有剩余能量.
同理T5的運(yùn)輸能力C5 = 3000-delta <= 3000，T1的運(yùn)輸能力C1 = 1000 - delta <= 1000.
這樣，我們就得出最優(yōu)策略2：在運(yùn)輸能力范圍內(nèi)，選用成本最低的方式。用R表示剩余未被運(yùn)輸?shù)哪芰?，由策?和策略2可知，最優(yōu)的運(yùn)送方式為：
當(dāng)2000 <= R <= 3000時(shí), 采用T5方式；
當(dāng)1000 <= R <= 2000時(shí), 采用T3方式；
當(dāng)0 <= R <= 1000時(shí), 采用T1方式。
即，先用T5消耗1000，剩余2000之后用T3方式再消耗1000，最后用T1方式運(yùn)輸余下能量。因此最優(yōu)解為：
T5: 運(yùn)輸距離 x = 1000/5 = 200
T3: 運(yùn)輸距離 y = 1000/3 = 333.333
T1: 運(yùn)輸距離 z =1000 - x - y = 466.667
運(yùn)送到終點(diǎn)的最大能量 = 1000 - 466.667 = 533.333
證畢.
近一步推廣：
首先簡(jiǎn)化上面的計(jì)算過程：
最大能量 = 1000 - z = 1000 - (1000 - x - y) = x + y = 1000 * (1/3 + 1/5).
現(xiàn)在有初始能量X（假設(shè)X可被1000整除，否則可以同理做推廣），按照最優(yōu)策略1和2可得：
因?yàn)?，最大需要的運(yùn)輸能力的方式Tmax=X/1000 * 2 - 1
所以，能夠運(yùn)輸?shù)?strong>最大能量 = 1000 * (1/3 + 1/5 + ... + 1/Tmax)
用歸納法很容易證明此結(jié)論。
因?yàn)?/3+1/5+1/7+...是發(fā)散的，所以理論上可以運(yùn)送任意初始能源X，但是考慮到單程最大能力為1000，只要X比1000多一點(diǎn)，就可以用T3方式先運(yùn)送一點(diǎn)，再
用T1運(yùn)送剩余，因此，約束條件為
X > 1000.
最后提個(gè)問題，如果希望能夠賣到集市上1000噸煤，那么最少需要初始有多少噸？
你才山西煤老板?。?！