有一隻駱駝，它的負重上限是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 胡言亂語 瘋瘋癲癲 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 219.70.168.103