Osheep

时光不回头,当下最重要。

一个火车运煤算法的思考

《一个火车运煤算法的思考》

image.png

一、问题描述

你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大――每一公里需要耗一吨煤。

请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?

二、思考过程

这道题一开始看上去好像是无解的,因为你的火车每一公里就要消耗一吨煤,而到目的地有1000公里,而火车最多只能装1000吨媒。如果你的火车可以全部装下,到目的地也会被全部烧光,一丁点也不剩。所以,很多人的第一反应都是觉得这个不太可能。

三、结论:

  • 装1000吨煤,走250公里,扔下500吨煤,回矿山。

  • 装1000吨煤,走到250公里处,拿起250吨煤继续向前到500公里处,扔下500吨煤,回矿山。此时火车上还有250吨,再加上在250公里处还有250吨煤,所以,火车是可以回矿山的。

  • 装上最后1000吨煤,走到500公里处,装上那里的500吨煤,然后一直走到目的。

同学们一定还有更好的方案,请集思广益!!!

点赞