橫越沙漠的駱駝 - 拼圖

有一隻駱駝，它的負重上限是1000根香蕉，要穿過1000公里的沙漠。
現在起點有香蕉三捆，各1000根。
駱駝每走一公里要吃一根香蕉。
駱駝可以在中途缷下香蕉，折返回去拿香蕉(同樣一公里要吃一根)
,過上次途中缷下的香蕉可以進行補充。
問駱駝最多能載多少重香蕉到終點？

(1) 載1000根。到200公里處，身上剩800根，放下600根，帶200根回起點，剩0根。
(2) 載1000根。到200公里處，身上剩800根，載上200根，留下400根，
到533公里處，身上剩667根，放下334根，帶333根回200公里處，剩0根。
載上200根，留下200根，回起點，剩0根。
(3) 載1000根。到200公里處，身上剩800根，載上200根，
到533公里處，身上剩667根，載上333根，留下1根，
到終點，剩533根。

所以533是構造的出來的
以下證明此方法為最多


定義折返點為駱駝到達後改變負載後往反方向前進的點
上例中折返點為200,533兩個

如果最好的方式只有一個折返點，設為x


├───────┼───────┤
0 x 1000
2000根 ─────→放1000-2x
2000根 ←───────
1000根 ─────→放1000-2x
1000根 ←───────
0根 ────→拿2(1000-2x)─────→到達

在最好的情形下
最後拿2(1000-2x)之後應該有1000根
所以x=2(1000-2x) x=400
到達終點時還剩400根，這當然不是最好

剩下的部分分兩類
(1)說明在兩個折返點時，200,533最好
(2)三個以上折返點是浪費

因為我還有報告要寫
先打到這裡
明天再繼續
謝謝






--
企鵝的網誌
www.wretch.cc/blog/demipenguin
胡言亂語
瘋瘋癲癲

--