有一只骆驼，它的负重上限是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