有只猴子在树林采了100根香蕉堆成一堆 原型

有一只猴子在树林里采了100根香蕉堆成一堆,猴子家距离香蕉堆50米,猴子打算把香蕉背回家。每次最多能背50根,可猴子嘴馋,每走一米要吃一根香蕉,那么猴子最多能背多少根香蕉回家?
这个题目的原型是什么?如何数学表达?有什么标准的数学解决方法?
已邀请:

海马非马

赞同来自:

有个运油问题和这个类似。但这个似乎更简单。不知道有没有特别好的办法,分析,尝试,二分,局部调整之类吧。
1. 如果分两次不中断的运回家,结果为0;
2. 如果先走25米,返回,起点->25米->起点->25米->终点,结果25。这是个更好的结果。

有没有更好的办法呢?
1. 最优解必定在猴子尽量背最多香蕉的情况下得到。也就是说不用考虑猴子从起点背10根,20根,48根香蕉的情况,这个似乎是不证自明的。
2. 第一个返回点不在25米处,比如1米,12米等处,会不会有更好的结果呢?简单分析易知,不会。猴子反程不消耗香蕉,每前进一米次(每米每次)的成本是一根香蕉(当香蕉还没有耗光时), 运到25米处时,每米至少需要两次,所以在25米处剩50根香蕉是可能的最优结果。这个负荷是猴子可以一次运到的。

3. 有没有某个方案能运送50个香蕉到某个大于25米的点,比如26米处,从而得到一个更优解呢?简单分析发现不可能。

综上25个是最优结果,但路线可以有很多,最简洁的是:起点->25米->起点->25米->终点

要回复问题请先登录注册