主题：【讨论】吃胡萝卜的驴的主人的烦恼 -- 独角兽

更一般的形式是穿越沙漠的吉普车或者环球航行的飞机

一般来说，假设路径长度为L，单位距离消耗的能源或者食物为1，每辆吉普（飞机，驴）载重为W

第一种情况

起点处的能源为N，问到达终点处最多可剩下多少能源（楼主问题即如此）

第二种情况

假设路途中不能存放能源，最多需要多少吉普接力才能穿越长度为L的沙漠，所有的吉普必须安全返回沙漠两端

还有其他变种

具体到楼主这道题目，思路是这样的：

首先设法把3000胡萝卜向前输送到某中继点，成为2000，那么容易看出至少要前进三次（3000/最大载重1000），则必须返回两次，这样这段距离上驴子跑了5次，长度为（3000-2000）/5=200

接下来，设法把2000胡萝卜向前输送到某中继点，成为1000，那么容易看出至少要前进两次（2000/最大载重1000），则必须返回一次，这样这段距离上驴子跑了3次，长度为（2000-1000）/3=333

最后，驴子前进到终点，则还剩下1000-（1000-200-333）=533胡萝卜

看看上面的例子可以知道这类问题的一般思路了

在

那只好上数学了。

胡萝卜最多3000颗，小毛驴顶多拉三趟。假设小毛驴拉三趟走过x1公里，拉两趟走过x2公里，拉一趟走过x3公里。所以有约束条件

x1 + x2 + x3 - 1000 = 0

显然 x1>=0，x2>=0，x3>=0

小毛驴拉三趟时消费的胡萝卜是 5x1 颗，所以

5x1 + x4 - 3000 = 0 (x4 >= 0)

小毛驴拉两趟时最多有胡萝卜不能超过2000颗

-5x1 + x5 + (3000 - 2000) = 0 (x5 >= 0)

它消费的胡萝卜是 3x2 颗，所以

5x1 + 3x2 + x6 - 3000 = 0 (x6 >= 0)

小毛驴拉一趟时最多有胡萝卜不能超过1000颗

-5x1 - 3x2 + x7 + (3000 - 1000) = 0 (x7 >= 0)

它消费的胡萝卜是 x3 颗，所以

5x1 + 3x2 + x3 + x8 - 3000 = 0 (x8 >= 0)

农夫的目标是尽可能多卖胡萝卜，他的目标函数是

max y = -5x1 - 3x2 - x3 + 3000

根据上述目标函数及约束条件，用单纯形法得最优解 (200,333.33,466.67,2000,0,1000,0,533.33)

然而，胡萝卜是整根的，所以x1、x2、x3必须取整数（也就是说这是一个整数规划问题）。在最优解附近用穷举法验算，得整数最优解x1=200,x2=333,x3=467。最终目标函数值为y=533

每次都要尽可能高效的发挥驴子的运输能力

所以每一步行动要让剩下的胡萝卜是载重的整数倍

楼主不妨试试看3500胡萝卜可以卖多少

稍微一般的公式是(L=1000,W=1000,N=kW)

1000(L)-[1000(L)-1000(W)/3-1000(W)/5-...-1000(W)/(2k-1)]

=W[1/3+1/5+...+1/(2k-1)]

方括号里是奇数倒数的和序列，不少同学是不是能想起中学物理那个搭积木的问题？

这个问题的吉普车形式更著名些，广泛流传为面试题，《蚁迹寻踪及其他数学探索》中有深入探讨重要的结论是

吉普越多越简朴，还有，奇数倒数的和序列是发散的，所以如果有充足燃料理论上可以走无限远

飞机环绕地球的问题稍微复杂一点点，因为可以逆向飞行加油。

• 呵呵
• fyi

1，由于驴子的最大运载能力是1000个，因此在起点的胡萝卜的存量总数大于2000个的时候，驴子必须跑3个来回才能完成一趟运输，也就是消耗5个胡萝卜前进1公里（最后一趟不必回头了），不小于1000的5的最小公倍数是1000，也就是说消耗1000个胡萝卜，前进1000/5=200公里，这时候剩余的胡萝卜是2000个；

2，当胡萝卜的总数在1000-2000个之间的时候，驴子每完成一趟运输任务，必须跑2个来回，也就是消耗3个胡萝卜，不小于1000的3的最小公倍数就是1002，也就是说，驴子消耗1002个胡萝卜，前进1002/3=334公里，剩余998个胡萝卜；

3，现在剩下的胡萝卜一把就可以全背上了，不用再折腾了，上路吧，带着998个胡萝卜，前面还有1000-200-334=466公里的路程，于是到达花花世界的时候就还有998-466=532个胡萝卜了。

1 驴子3个来2个回，1000/5=200

2 驴子2个来1个回，1000/3=333

3 正确，1个来不回

所以3000个萝卜的时候是消耗5个萝卜前进一公里。于是按您的思路，得出的就是跟沉宝兄一样的结果了。

但是您的逻辑我还没有完全想清楚，容我再想想。

我比较能理解荷子兄的算法。但是不明白为甚这是最优的。就是我同事就是这个3000－－》2000－－》1000的思路。

回给自己了

荷子:关键在于

2，前进999/3=333公里，剩余1001个胡萝卜；

3，带着1000个胡萝卜，前面还有1000-200-333=467公里的路程，于是到达花花世界的时候就还有1000-467=533个胡萝卜了。

于是赶快回头改，还是被大伙儿抓住了啊。

不过嘛，做题写步骤，就是错了也能蒙几分回来的。这可是当年的高考密技之一呢。

俺的中转站设定是为了实现最后一趟的时候消耗等于补给。于是：

（1）1000萝卜出发，在250m处返回，留下500萝卜。

（2）1000萝卜出发，在250m处补给250个萝卜，在500m处返回，留下250个萝卜。

（3）1000萝卜出发，在250m处补给250个萝卜，在500m处补给250个萝卜，到了花花世界就剩500个萝卜了。

独角兽坚持认为虽然俺的萝卜少了，但是俺的思路也是优美的呜呜

533个……

一公里一公里的挪3000个胡萝卜，头200公里吃掉1000个，再333公里又吃掉1000个，最后一趟运到地方还剩533个，中间还扔了一个，呵呵。

回来也要吃吧.那怎么够卖呢..亏死了.

所以还是在家自己慢慢吃吧.