智游城

标题: 运萝卜问题 [打印本页]

作者: 老陈 时间: 2013-2-1 09:32
标题: 运萝卜问题
一头驴能负重1000只萝卜，现需要搬运3000只萝卜到1000公里外的目的地，驴每走1公里吃一只萝卜，问怎样搬运到终点剩下的萝卜最多？多少个？

作者: dengxianqi 时间: 2013-2-1 11:03
不负重走路的话，不需要吃萝卜吧？

作者: notch 时间: 2013-2-1 13:08
驴子不负重也是要吃萝卜的，所以不能空身回来
消耗的萝卜和背多少萝卜没关系，只和路程有关
所以驴子出发的时候要近可能的多背

那么3000萝卜可以分三次背，要求中继点的时候剩下2000
所以第一段200公里
记下来2000萝卜分两次背，要求中继点时候剩下1000
第二段333公里
第三次1000萝卜直接背到目的地
一共剩533萝卜

作者: Howard 时间: 2013-2-2 01:57
此问题我知道网上肯定有答案，为了避免受影响，我没有进行任何搜索

首先从极端条件开始考虑。

1. 驴子背负最大负重1000根，直接干到终点，剩余0。任何小于1000根，就连终点都走不到，这肯定不行。

2. 如果背负1000根，行走超过500公理，那么它已经没有回头路，只能继续前行至终点，结果跟1相同。

由1、2，驴子的第一中转站一定是1公理到499公理之间的一个距离。那么全程至少需要两个中继站。是否更多？现在还不知道。

因为驴子吃萝卜速度跟负重无关，完全没必要背任何少于1000根的东西。

设从任一中继站（含起点）出发时的胡萝卜为m，到达下一中继站（含终点）的距离为d，则：

1）m是【2001，3000】时，需要两次半往返，剩余m-5p
2）m是【1001，2000】时，需要一次半往返，剩余m-3p
3）m是1000或更少，只需一次单程，剩余m-p

可见，萝卜消耗速度与路程成正比，但斜率有变化

如果第一中继站设在1公里处，第二中继站设在2公理处，那么到达2公理时，会消耗2×5×1=10根。
如果第一中继站直接设在2公理处，那么到达时会消耗2×5=10根。
完全等效。

关键在于函数不连续处，也就是，到达下一中继站时剩余2000跟之上与之下？

如果到达下一中继站后，剩余了2001根，可想而知，则为这一跟胡罗卜，再往下走仍需承受5p的消耗速度，无法享受3p。

相反，如果剩余1999根，那么在达到这1999根时，有一点点距离本可以享受3p，却承担了5p。此处似乎1998根更好。剩余1998根时，最后走的一公里本可以少吃两根胡萝卜。

所以2000跟胡萝卜必须要设置一个中继站。

同理，1000根也要设置一个。

所以我的答案跟notch相同，200公理处设置2000根中继站，533.3公理处设置1000根中继站。

notch兄已经英明指出，我只不过把他的思维展开证明一下

但是还有一点补充，就是在这两个标志性中继站之间，还可以设置任意多的小中继站，只要别让驴子饿死在路上就行。

比如，在533.3中继站前，每一公里都设置一个中继站。只不过在533后就别设了，一路运到终点。

这样，最少可设置2个中继站，最多可设置533.3个。

答完了，现在去搜索正确答案

作者: shuijing 时间: 2013-2-2 03:13
可不可以租台大卡车，把萝卜驴子一同运到千里之外{:soso__9717536260333092701_1:}

作者: grandmacau 时间: 2013-2-2 04:35
搜索结果最多的是534根。

作者: grandmacau 时间: 2013-2-2 04:41
节省大家一点时间，把某搜索结果公布一下：

假设到目的地时有1000根萝卜，那么在目的地之前一定不只1000根，那么至少要驮两次才会到目的地，那样从出发地到目的地边缘都会有往返的里程，那所走的路程将大于3000公里，故最后能卖出萝卜的数量一定是小于1000根的。那么在走到某一个位置的时候萝卜的总数会恰好是1000根。因为驴每次最多驮1000，那么为了最大的利用驴，第一次卸下的地点应该是使萝卜的数量为2000的地点。因为一开始有3000萝卜，驴必须要驮三次，设驴走X公里第一次卸下萝卜则：5X=1000（吃萝卜的数量，也等于所行走的公里数）X=200，也就是说第一次只走200公里验算：驴驮1000根走200公里时剩800根，卸下600根，返回出发地前两次就囤积了1200根，第三次不用返回则剩800根，则总共是2000根萝卜了。第二次驴只需要驮两次，设驴走Y公里第二次卸下萝卜则：3Y=1000， Y=333.3验算：驴驮1000根走333.3公里时剩667根，卸下334根，返回第一次卸萝卜地点第二次在途中会吃掉334根萝卜，到第二次卸萝卜地点是加上卸下的334根，刚好是1000根。而此时总共走了：200+333.3=533.3公里，而剩下的466.7公里只需要吃466根萝卜所以可以卖萝卜的数量就是1000-466=534

欢迎光临智游城 (http://zhiyoucheng.co/)