火车运煤问题(上)

酷壳上面有这样一道题:

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

不少人回复了答案和简要解答过程,粗粗浏览一遍,正确解答不少,但是思路中到了关键步骤就有种天马行空的感觉,缺乏比较严谨的证明和思考过程。那么,对于这个问题,我们应该如何思考?
 首先,从题目的描述,可以得到两个推断:

1、火车需要来回把煤运到若干个中间点后再出发的(如果一次过去不回头,到了终点煤量就是0了),运送过程中需要消耗燃料;

2、在中间点M时,其他地方不存在剩余的煤,否则不是最优解。

对于推论2,证明如下:假设其他地方有剩余的煤,并假设放着煤的地方在N点。若N点在M点的后面,那火车要么回头把那部分煤运到中间点,要么直接把那部分煤丢弃不管,这两种情况都会最终得到“N点没有煤”的结果;若N点在中间点前方m公里的位置,那么为了把煤从M点运到N点,需要消耗至少2m吨煤(因为火车是从中间点出发),那么,先把所有煤运到M点,再把部分煤运送到N点,这种情况下火车在M点可以满载出发,能运到N点的煤量必然比较多。因此这样得到的结果一定优于前者。所以其他地方无剩余的煤

因此,从上面的推断,会得到一个更具普遍性的问题:若起点有n吨煤,运输k公里后,最多还剩多少吨?不妨使用f(n,k)记录“起点有n吨煤,需要运送k公里,剩下煤量的最大值”。由于有若干中间点,那我们设下一个中间点离本次起点的距离为x。然后问题就转化成:对于给定的n和k,如何求x,使得本问题有最优解

显然,这是一个递推的思路,看到“递推”和“最优问题”,很自然就会想,是否可以使用动态规划求解?这是本问题的第二种解法,咱下集再议。

要运到x公里以外的下一个中间点,火车需要若干来回才能把煤运过去。那么,火车需要多少次来回呢?我们先算一算,看看结果有啥规律:

首先,x是否可以无限大?当然不行,要跑到前方x公里处, 那火车剩下的煤量得足够返回才行。所以若火车需要返回,则x<500。

1、若n<=1000,显然火车不需要来回,直接带上所有的煤往前跑,跑到前方x公里时,能放下的煤量为min(1000-x, k-x)。若起点煤量n>1000,则有部分煤被浪费。

2、若n比较大,火车可以通过一次返回得到更多的煤量积累,则跑到前方x公里处消耗的煤量为3x(一个来回再加上单程),由于火车从起点出发两次,累计最多拿2000吨煤,一共运2000吨煤,所以最后该点能放下的煤量为min(2000-3x, n-3x)。若起点煤量n>2000,则有部分煤被浪费。

3、若n再大一点,火车可以两次来回跑到前方x公里处,那两次来回消耗的总煤量为5x,最后该点能放下的煤量为min(3000-5x, n-5x) = n-5x。因为起点最多就3000吨煤,所以n<3000。

我们注意到,若决定了火车返回的次数,则途中消耗煤量与x为线性关系。也就是说,火车直接选前方x公里的N点作为下一个中间点,与火车在中途再选若干个中间点,两种走法消耗的煤量是一样的。因此,在n>2000的时候,我们可以选取一个较小的x值,让火车返回2次把n-2000吨煤烧掉;n>1000的时候,我们可以选取另外一个x值,让火车返回1次吧n-1000吨煤烧掉;n<=1000的时候,带上所有家当欢快地往前奔吧!这个就是最优解。

画个函数图像可以更明确地看到这点,用横轴表示路程,纵轴表示煤量,图上的一点(k, n)表示在离终点k公里处剩下煤量。火车返回两次时位置和煤量的关系使用黑线表示、返回一次时位置和煤量的关系使用红线表示,返回零次时位置和煤量的关系使用蓝线表示,则黑线的起点只能在n=3000水平线以下,红线的起点在n=2000水平线以下,蓝线的起点在n=1000水平线以下。我们要做的事情,就是把这几条线连起来,得到一条贯穿左右的通路,右边终点的高度就表示最终剩余的煤量。

看着这个图,如何取得最优解,一目了然。