有关火车运煤问题的思考

室友参加某公司的笔试结束,问了我下面这道题:

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

PS.中间任意地点可以丢下煤,也可以折返,折返过程中也需耗煤。

题目来源:CoolShell

变种题目包括:驴子运胡萝卜、马运草等。

乍一看,这题似乎有问题:1000吨带上去,开到终点就没了,怎么办?

转念一想,这题应该是可以选择在中途放下煤的。

在网上查看答案之前,自己模拟了一个比较典型的情况:

第一次运1000吨,在250km处放下500吨,返程;

第二次运1000吨,在500km处放下500吨,返程;

第三次运1000吨,到500km处刚好拿上500吨,直接走。

这样到终点就有了500吨

感觉500这个答案既像是标答,又感觉不太准(要是随便一试就是答案这题也太水了吧)

另一个搞ACM的室友说,这是DP(Dinamic Programming,动态规划)问题。

看了一些分析之后,于是有了思路:

  • 总共3000吨煤,一次出发最多只能运1000吨,那么最少要出发3次,且前两次返回起点时,火车为空;
  • 最后一次出发不用返回;
  • 既然前两次要返回,那么一定会在路上投放煤。不妨将起点计作A点,终点记作D点,路上的两点分别计作B、C点,其中B距起点A较近。

那么,目标就是求解最优的B、C点位置了。

整个运送过程如下:

而又可以将上述过程理解成:

即:先将煤运到中转站B,再运到中转站C,最后运到D。每次从一个中转站出发的时候一定尽量满载。

C到D一定是一次运完,所以C点存放1000吨。A到B至少3次运完,B点煤的数量比A少,比C多,只能是2000吨。

这样就可以求解了:

AB:走5次消耗1000吨,$AB=1000/5=200$.

BC:走3次消耗1000吨,$BC = 1000/3 = 333.3$

因此,从A到D最多运送533.3吨煤。

扩展:一般情况

原问题链接的评论区中,用户@albert分析的很好:

1000是基本刻度,解题精髓在于消耗多余的煤把煤移动到一个离终点更近的距离,最后一次运上1000吨然后从这个地方直达终点,还能剩下的就是你能运达的煤。 煤越多需要的搬运次数越多,搬运次数越多消耗就越多。 要运送到相对较近的距离对煤的消耗量为$(2n + 1)Step$,Step为一次行进的步长,$n=totalNum / 1000-1$,totalNum为总煤量 根据这个公式, 当煤量为2000~3000时,你的运送成本是5Step 1000~2000时为3Step, 小于等于1000时为1Step, 所以第一次选择行进200公里,消耗的煤为5 × 200 = 1000,剩余2000(2000~3000) 第二次选择行进333公里,消耗的煤为3 × 333 = 999 =~ 1000,剩余1000(1000~2000) 此时一共行进了533公里,还剩下1000吨煤,最后到达终点还剩533吨(1000内)

其实次数是无所谓的,关键是把握消耗的数量级。比如第二个刻度分解了 第一次选择行进200公里,消耗的煤为5 × 200 = 1000,剩余2000(2000~3000) 第二次选择行进200公里,消耗的煤为3 × 200 = 600,剩余1400(1000~2000) 第三次选择行进100公里,消耗的煤为3 × 100 = 300, 剩余1100(1000~2000) 第四次选择行进33公里,消耗3×33=99~=100,剩余1000(1000~2000) 此时一共行进了533公里,还剩下1000吨煤,最后到达终点还剩533吨(1000内)

以及,本题目其实具备初中数学知识(甚至小学知识)就已经够解了,很多时候善于思考还是很重要的。

(可惜我在拿到答案前并没有思考出来…干脆记一笔方便以后回味吧)

假装有打赏功能