讨论！经典问题——骆驼运输香蕉的问题

Question

本帖最后由 JebySin 于 2010-10-12 21:22:30 编辑

Answer 1

文字说明：
首先将3000只香蕉运送到X1公里处，一共需要吃掉【5*X1】（在X1距离上共运行了5次）只香蕉。剩余香蕉为【3000-5*X1】。
此处X1的选择为：使剩余香蕉数<=2000。X1=200。剩余香蕉2000，剩余800公里再将2000只香蕉运送到X2公里处，一共需要吃掉【3*X2】（在X1距离上共运行了3次）只香蕉。剩余香蕉为【2000-3*X2】。
此处X2的选择为：使剩余香蕉数>=1000并且最接近1000。X2=333。剩余香蕉1001，剩余467公里。在距离终点467公里处驮上1000之香蕉出发，最后剩余：1000-467=533。代码：
/**
 * 取得剩余香蕉最大值<br>
 * @param total 香蕉总数
 * @param max 每次最多运输数量
 * @param distance 总路程
 * @since 
 */
private static void getMax(int total,int max,int distance){
int remainT = total;//剩余香蕉总数
int remainD = distance;//剩余总路程
int pos = 0;
int cycle = (remainT / max) * 2 -1;
while(cycle > 1){
pos = max / cycle;
remainD-=pos;
remainT = remainT - pos * cycle;
System.err.println("剩余公里:" + remainD + "剩余香蕉:" + remainT);
cycle = (remainT / max) * 2 -1;
}
System.err.println("最终剩余香蕉:" + (max - remainD));
}

Answer 2

三楼的算法不准确，针对本题是可以计算的，要考虑当剩余香蕉总数（remainT）大于每次最多运输数量（max）并且这个数大于等于3的情况判断（remainT-max）是3的几倍，(max - remainD)在加上这个倍数就是最后剩余香蕉的总数。

Answer 3

/**
* 取得剩余香蕉最大值<br>
* @param total 香蕉总数
* @param max 每次最多运输数量
* @param distance 总路程
* @since  
*/
private static void getMax(int total,int max,int distance){
int remainT = total;//剩余香蕉总数
int remainD = distance;//剩余总路程
int pos = 0;
int cycle = (remainT / max) * 2 -1;
while(cycle > 1){
pos = max / cycle;
remainD-=pos;
remainT = remainT - pos * cycle;
System.err.println("剩余公里:" + remainD + "剩余香蕉:" + remainT);
cycle = (remainT / max) * 2 -1;
//在此处加上一句就可以了
//剩余香蕉减去每次最多运输量 x = (remainT - max)之后当这个数值在3~max之间时，执行下面语句
//x如果等于3 即骆驼一次拿满1000根走到一公里处放下998根 回头去取剩下的3根，这事骆驼在消耗两根，
//还剩下2+998=1000 
if ((remainT - max) >= 3 && (remainT - max) < max) {
    System.err.println("最终剩余香蕉:"+ (max - remainD + ((remainT - max) / 3)));
}
}
System.err.println("最终剩余香蕉:" + (max - remainD));
}