运苹果问题

Question 1.10: There are two cities, A and B, 1,000 miles apart. You have 3,000 apples at City A, and you want to deliver as many as possible of them to City B. The only delivery method available is a truck.There are, however, two problems. The truck can hold at most only 1,000 apples, and if there are any apples at all in the truck, the hungry dishonest driver will steal and eat one apple for every mile he drives. What is the maximum number of apples you can deliver from City A to City B? Note that you are welcome to stop part way, dump off some apples, and then come back and pick them up later.

 

这其实是一个经典的智力题,火车运煤问题。谁先谁后就不去考证了。先把这个问题贴一下:

你是山西的一个煤老板,你在矿区开采了有 3000 吨煤需要运送到市场上去卖,从你的矿区到市场有 1000 公里,你手里有一列烧煤的火车,这个火车最多只能装 1000 吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?

直观的分析比较简单了:一开始必须返回 3 次,每公里成本是 5(苹果问题里是 3)。假设运到一个中间点,那么中间点的量肯定小于 3000,

  • 若为 2001~3000,则运到下一个中间点还需折返 3 次,成本还是 5(3);
  • 若为 1001~2000,只需折返2次,此时成本降为 3(2);
  • 若为 1~1000,只需一次即可运完,成本为 1(1)。

第一程成本最高,应距离最短,应消耗掉 1000,所以第一程距离为 200(333);同理第二程距离为 333(500);第三程直接到终点,距离为 467(167)。于是能最多运 533(833)。


问题是,如果初始的量改为 ,还能不能这么简单地找出最佳运输方法呢?Focustc 提出的方法非常有借鉴意义:

 吨煤最多可以运输多远?

这个问题就没有那么难以回答:1000 吨显然是 1000 公里;2000 吨多出的那一程显然消耗完多出的这 1000 吨为最佳,所以多出的距离为 公里;3000 吨比 2000 吨多出的那一程又以消耗完多出的 1000 吨为最佳,那么多出了 公里……所以 吨煤最多可以运输 公里。对于苹果问题,这个答案是公里。那么对于原问题,先把货物搬运到距离为 )的中间点,然后再搬运到距该中间点 )的另一中间点,…,直到可以直接运到终点站。

需要注意的是,具体数值可能不为上述最远距离直接减 1000,因为终点站可能处在两个中间点之间。

Figure: The Apple Truck by Julie Ronning Talbot

文章归档

阅读更多

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注