一道小题，挺有意思，期待算法

zyzme

一个商人骑一头毛驴要穿越1000公里长的沙漠，去卖3000根胡萝卜。

已知毛驴一次性可驮1000根胡萝卜，但每走1公里又要吃掉1根胡萝卜。（无论是否驮萝卜都要吃）

问：商人最多可卖出多少胡萝卜？


求解释，求真相。

网上给出了不少解答，大家也可以搜索一下，没有令人满意的。

百度一下，你就知道。      Google一下，你知道的会很多。

zyy

我沿着正常的思路得到0

zyzme

我沿着正常的思路得到0
zyy 发表于 2010-10-30 13:15

你是不是每往返一次，萝卜都在路上消耗完了啊？
那样不行的，每次走近一点。

jankingyu

网上提供的驮3、2、1次算法是对的。

jankingyu

驴每次最多驮1000，为了最大的利用驴，取驮最大，行走路程最近。
一开始有3000萝卜，驴必须要驮三次（过程萝卜只要大于2000，往返路程5
x），设驴走X公里刚好剩余2000，
则：5X=1000（吃萝卜的数量，也等于所行走的公里数）
X=200，也就是说第一次只走200公里，在此点位置萝卜还有2000根，路程还有800km。
接下来就是二次驮（只要萝卜数大于1000，往返路程3y）
第二次驴只需要驮两次，设驴走Y公里第二次卸下萝卜
则：3Y=1000， Y=333.3；此点位置533.3km，萝卜还有2000根，路程还有466.7km。
取整：若y=333，则位置为533km，萝卜还有1001根，路程还有为467,那么（人不下来走）最有选择就是扔掉一根萝卜（或直接给驴再吃掉），此时直接到终点剩余萝卜533。若y=334，位置为534，萝卜还有998，到终点就为464。所以最多应为533

zyzme

5# jankingyu

觉得这个方法还有可以改进的地方，不过我还没想出来。
我不是指结果，只是觉得方法不够严谨。