I got this problem from Rustan Leino, who was told it by Rupak Majumdar. I modified it slightly.

I solved it and wrote up my solution.

You have 900 bananas that you want to transport a distance of 300 km. The transport will be done by a monkey. The monkey can carry as many as 300 bananas at any one time. With each kilometer traveled (forward or backward), the monkey consumes one banana. How many bananas can you get across to the other side?

You can get 250 bananas across, using the following strategy.

Have the monkey carry 300 bananas a distance of 100 km, then dump the remaining bananas in the road. The monkey will have consumed 100 bananas, so it winds up dumping 200 in the road.

Have the monkey then return to the start position with an empty load. Thankfully, the monkey can't eat any bananas during this return since it doesn't have any with it.

Have the monkey again carry 300 bananas a distance of 100 km, then dump the remaining bananas in the road next to the already-dumped bananas. It'll again dump 200 bananas.

Have the money return to the start position, then carry the remaining 300 bananas there a distance of 100 km, then dump the remaining bananas in the road next to the already-dumped bananas. It'll again dump 200 bananas.

The monkey is now 100 km along the path, standing next to 600 bananas dumped in the road. Have it pick up 300 off the road, then carry them a further 150 km, then dump the bananas on the road. It'll have eaten 150 of them, so it dumps 150 on the road.

Have the monkey go back 150 km to return to the other pile, which has 300 bananas. Have it carry those bananas 150 km forward, then dump its remaining 150 on the road next to the 150 already there.

The monkey now finds itself 250 km along the path next to a pile of 300 bananas. Have it pick those bananas off the road and carry them the remaining 50 km to the destination. Along the way, it'll eat 50 of them, and deliver to the final destination the remaining 250 bananas.

This is optimal, by the following reasoning. You want to lose as few bananas as possible while traveling 300 km. So, you want to pay as few bananas per km as you can. As long as you have more than 600 bananas, you need three trips to transport all your bananas, and thus have to pay 3 bananas per km. So, the first 300 bananas you spend get you $300/3 =$ 100 km. Once you reach 600 bananas, until you reach 300 bananas you need two trips to transport all your bananas and thus have to pay 2 bananas per km. So, the next 300 bananas you spend get you $300/2 =$ 150 km. From that point forward, you can transport all your bananas in one trip and only pay 1 banana per km. So, you can get away with only spending 50 bananas to go the remaining 50 km. Thus, the best you can hope to finish with is 250 bananas.