《火車運煤問題》分析

 作者：陳太漢

《火車運煤問題》分析

　　題目內容：

　　　　你是山西的一個煤老板，你在礦區開采了有3000噸煤需要運送到市場上去賣，從你的礦區到市場有1000公里，你手里有一列燒煤的火車，這個火車最多只能裝1000噸煤，且其能耗比較大——每一公里需要耗一噸煤。請問，作為一個懂編程的煤老板的你，你會怎么運送才能運最多的煤到集市？

　　　　這是我在《酷殼》看到的一個面試題，主要是被陳浩的幾句話給吸引了，還有就是哥比較喜歡思考，想證實一下哥是否適合做程序。

　　火車運煤問題分析

　　　　表面上看這個問題很難實現，因為火車最多只能載1000噸煤，而行駛1000公里剛好把火車上的1000噸煤燒光。等我們認真思考之后會發現，可以分段運輸。如先運1000噸煤行駛100公里，放下800噸再返回，再運1000噸煤到100公里處，此時車上還有900噸，再加上100噸煤，車上就有1000噸煤，離終點還有900公里，到終點的時候還剩100噸煤。

　　　　老實說哥沒有天才的IQ，我先是邊看《單身男女》邊思考這個問題，差不多用了1個小時沒有得出一個結果，也沒有弄懂怎么來的5x+3y=2000 (y<=1000/3)，以及求x+y的最大值, 回家在吃飯的時候又突然想起這個問題，又邊吃飯邊思考這個問題，有時放下碗在本子上畫畫，差不多用了四五十分鐘，哥突然明白了5x+3y=2000,其實應該是5x+3y>=2000,當然也就明白了x+y的最大值，幾分鐘之后哥又明白了5x>=1000, 最后得出x=200,y=333.333333時x+y得出最大值533.33333333。

　　                                   -->3次                                     -->2次                                        -->1次

　　　　 A（起點）--------------------------------B----------------------------------C-----------------------------D（終點）

　　　                              　<--2次 　　　　　　　　　　　 　<--1次

              |--------------------X-------------------|---------------Y------------------|--------------Z--------------|

　　　　為什么是5x+3y>=2000？

　　　　　　3000/1000=3，將3000噸煤運離原始地點，至少要運三次，因為運輸的次數越多燒掉的煤就越多，到終點時剩下的煤就越少，所以把煤運離起始地點一定是3次，也就是5x(往3次，返兩次)。中間必須停在兩個地方（B,C）將煤放下，因為到C處的時候，車上的煤最大只能有1000噸，因為火車最多只能運1000噸，多了運不了，用兩次運肯定是不可能的。所以從A到C至少燒了3000-1000=2000噸煤，即5x+3y>=2000.

　　　　為什么是x+y的最大值？

　　　　　　在C處剩余的煤最多只有1000噸，離終點越近剩下的煤就越多，所以在x+y取最大值的時候，剩下的煤最大。即剩下的煤=1000-Z=1000-Z=1000-（1000-（x+y））=x+y

　　　　 為什么是5x>=1000?

　　　　　　 同理在B處最多還剩2000噸煤，因為在B處時煤的數量還大于2000時，將這2000多噸煤運離B處至少要三次，三次的情況，我們就認為是A-->B，所以在B處至多只能要剩2000噸，即5x>=3000-200=1000.

　　　　可能有人會問為什么是3次、2次、1次，而不是3次、一次，同樣按照上面的分析，你可以得出3次、1次的情況最多剩余400噸。

　　　　5x+3y>=2000

　　　　5x>=1000

　　　　求x+y的最大值？