猴子背香蕉最优解问题的程序实现
- 1 min问题描述：
- 有只猴子在树林采了200根香蕉堆成一堆，猴子家离香蕉堆100米，猴子打算把香蕉背回家， 每次最多能背100根，可是猴子嘴馋，每背一米要吃一根香蕉，问猴子最多能背回家几根香蕉？
个人理解：
- 每走一米都吃一根香蕉，包括往回走
- 肯定是一次携带的越多，往返的次数越少，能省下的香蕉才越多，所以我认为需要两次往返，每次携带100根
- 目前问题就是走几步返回拿剩余的香蕉才能得到最优解的问题
程序分析：
- 假设每走一步回去拿剩余的香蕉，当走1米时剩余99根香蕉，并且需要拿一根香蕉回到起点，即在第一米处留下了98根香蕉
- 当回到起点拿上剩余的100根香蕉后，走到一米的地方还剩99根，加上剩余的香蕉总数为99+98=197根，所以每走一米需要3根香蕉
- 当然你每到一个位置的时候你都可以直接回家，如在1米的位置你可以直接拿100根香蕉直接回家，路程上还需要消耗99根，所以到家还剩1根
程序实现：
为了快速实现我采用的是Go语言实现，其他语言逻辑一样：
/**********************************************
** @Des: monkey - example
** @Author: archerzdip
** @Date: 2019-03-01 23:22
** @Last Modified time: 2019-03-01 23:22
***********************************************/
package main
import "fmt"
func main() {
// 距离
distance := 100
// 最优解
bestLeft := 0
// 每次走的步数
for i := 1 ; i <= distance/2 ; i++ {
// 总数
total := 200
// 剩余
left := 0
// 走到第几步
for j := i ; j <= distance ; j += i {
leftStep := 100 - j
if total > 0 {
total -= i*3
}
if total > distance {
left = 100 - leftStep
} else {
left = total - leftStep
}
if left > bestLeft {
bestLeft = left
}
if total < 0 || left < 0 {
break
}
fmt.Printf("每次走%d步，当走到第%d步时，还剩香蕉%d根，距离终点还剩%d米，走到终点还剩%d根。\n", i,j,total,leftStep,left)
}
}
fmt.Printf("最优解为：%d根",bestLeft)
}
结果：
最优解为：33根
从结果中可以看出每走1米回去取剩余的，当走到33米的时候直接回去可剩余33根；每次走33米当走到33米的时候拿上100根直接回去也可剩余33根，所以33根为最优解。
可能问题
- 目前想到的逻辑为这样，若逻辑错误则程序肯定不对
- 该程序没实现我第一次走1米，下一次走其他米数的情况，但我觉得结果应该相同
- 目前正在学习Go，可能没能体现出Go的优势
反馈
该逻辑是我自己的理解，可能有问题欢迎指正。 感谢！！！