主题：【讨论】吃胡萝卜的驴的主人的烦恼 -- 独角兽
家园 这类题目的一般解 更一般的形式是穿越沙漠的吉普车或者环球航行的飞机
一般来说，假设路径长度为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胡萝卜
看看上面的例子可以知道这类问题的一般思路了
在
- 复 这类题目的一般解
家园 送花，昨天晚上按你这个思路做出来啦d - 复 这类题目的一般解
家园 关键在于 每次都要尽可能高效的发挥驴子的运输能力
所以每一步行动要让剩下的胡萝卜是载重的整数倍
楼主不妨试试看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 帖 引用 (帖内工具实现)
家园 沉宝大侠，高 还有没有别的思路呀? 其实俺想到的比这个方案差一些。这个方案同事想到了。我们怎么也想不明白为什么差。就是说这个最优方案的指导方针是什么？
大家继续呀！
- 复 沉宝大侠，高
家园 哈哈，如果你很严肃地要最优方案的话 那只好上数学了。
胡萝卜最多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
家园 农民能不能把萝卜放在沙漠中，能得话才有意思。 家园 不能就无解了吧？
家园 533颗 一头驴最多载重1000颗胡萝卜，老农往返三趟，可把全部胡萝卜运到200公里处，这时小毛驴自身吃掉1000颗胡萝卜，所以还剩2000颗胡萝卜。从此地再前进333公里，往返两趟，小毛驴自身吃掉999颗胡萝卜，扔掉1颗带不走的，老农带着1000颗胡萝卜从533公里处继续赶路。从533公里到1000公里小毛驴要吃掉467颗胡萝卜，所以老农最多还可以卖533颗胡萝卜。