五千年(敝帚自珍)

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

共:💬53 🌺43
全看树展主题 · 分页首页 上页
/ 4
下页 末页
家园 这类题目的一般解

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

一般来说,假设路径长度为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)]

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

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

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

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


本帖一共被 2 帖 引用 (帖内工具实现)
家园 我算出来是532个,方法如下:

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的思路。

家园 fyi

回给自己了

荷子:关键在于

家园 532也不对

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个,中间还扔了一个,呵呵。

家园 要不要考虑回来路上的口粮???

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

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

全看树展主题 · 分页首页 上页
/ 4
下页 末页


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河