骆驼运香蕉问题（140714）

闵应骅

   计算机科学要研究算法，有过程的问题、优化的问题、复杂性的问题等等。这些问题常常可以用很通俗的语言表达出来，而其含义却很深远。譬如，货郎担问题、八皇后问题、邦占廷将军问题都是这样。北大毕业的才子洪加威（1936-，现在美国，参见http://blog.sina.com.cn/s/blog_45de2bb30101hebn.html）在国际会议上提出三个中国人问题，以祖父、父亲、儿子三个中国人在迷宫里怎样机智地确定有没有回路的形象比喻，首次在世界上提出关于决定性空间完全性问题。所以，不要认为这些通俗的说法不起眼，可能恰恰是说明了问题的本质。

上周美国天普大学吴杰教授访问中科院计算所，点名要见我。我与他的联系已经30年了。上世纪80年代，承他邀请，我访问过他的大学，并在他家面临着湖的院子里为我举办了家庭派对。此后，我们联系很多。他是龙星计划创始人之一，第一批龙星计划特邀教授来华讲课。这次，他来做了一个报告，其中提到了一个骆驼运香蕉的问题。banana-eating camel problem在百度里被自动翻译成“香蕉吃骆驼的问题”，可笑不可笑！自动翻译真不可信。至少也应该翻成“吃着香蕉的骆驼”吧！但这问题还是很有意思，听说外企招聘面试的时候还提过这样的问题。特转述如下。

想当初，一个沙漠地区的农民收获了3000香蕉，要送到1000英里以外的市场去卖。他只有一头骆驼，这骆驼一次最多驼1000个香蕉，而且每走1英里就要吃掉1个香蕉。那么，他最多能送多少香蕉到市场呢？很显然，如果一直走下去，到终点，香蕉也就吃光了，一个也不剩。所以，需要在路中间停下，存一些香蕉，下次来补上已经吃掉的。

这问题的解如下图所示，是这样的：骆驼首先驼1000香蕉出发，走了200英里，撂下600香蕉往回走。再取1000香蕉出发，到了Store1，检起200香蕉继续走，到533英里处，撂下333香蕉往回走，到200英里处，再检200香蕉回到原地。再取1000香蕉出发，在200英里处检起200香蕉往前走，到533英里处，再检起那333香蕉往前走。这时，它还有1000香蕉。再走467英里到了市场，还剩1000-467=533香蕉。所以，骆驼最多只能送533香蕉到市场。

   你能证明这是最优解吗？200和1000/3这两个数是怎么出来的？想一想，也许有点意思。