首页 > 代码库 > 火车运煤问题
火车运煤问题
题目:
煤矿有 3000 吨煤要拿到市场上卖,有一辆火车可以用来运煤,火车最多能装 1000 吨煤,且火车本身需要烧煤做动力,每走 1 公里消耗 1 吨煤,如何运煤才能使得运到市场的煤最多,最多是多少?
分析:
设出发点为 A ,终点为 B,火车一定不能一下子就从 A 跑到 B,这样就 B 时刚好什么也没剩下。到中点也不行,因为到中点后再回到 A,刚好把自己带的煤全部用完,只烧煤不干活!那到底要走多远返回合适呢?
我们可以倒着推理,最后一次火车到 B 点的最好情况是火车从 A B 之间的某点带 1000 吨煤出发,除去路上消耗的,剩下的都可以运到 B 点。
那 最后这 1000 吨煤应该从哪里出发呢?肯定是从 2000 吨煤过来的,为什么是 2000 吨而不是别的数字呢?别的数字当然也可以,但是可能比较复杂, 2000 吨这个数字比较特殊,刚好是火车运量的 2 倍,刚好是个很完整的数。问题就变成,2000 吨煤中消耗 1000 吨最多能走多远,我们知道,2000 吨用火车需要出发 2 次,加上中间返回的那次,一共 3 次(最后一次出发后不用返回了),也就是消耗的 1000 吨煤火车跑 3 次,能跑多远,1000/3 米。
同理,那 2000 吨应该从起点出发,是从 2000 吨转化而来的,这回运 3000 吨火车需要出发 3 次,加上返回的 2 次,一共 5 次,消耗 1000 吨煤火车跑 5 次,能跑 200 米。
综上,火车最后一次出发是从离起点 200+1000/3 米处出发,到 B 点还有 1000 - (200+1000/3) 米,耗煤也是这么多吨,所以到 B 点还剩 200+1000/3 吨煤。
当然,正向推导也是可以的,这是个分段函数,从起点向终点推也行,这里不再细说,有兴趣的请自行网上搜索。
火车运煤问题