火车运煤,驴子吃萝卜,骆驼吃香蕉

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

这个题的其他形式为,驴子吃萝卜,骆驼吃香蕉,而我的问题是,如果你想运1000吨煤到集市,最少需要初始多少吨煤?

这个题的解答并不难,有很多网友都给出了答案,但是想说清楚道理还是比较绕弯。如果想做编程做模拟,代码很简单,但是有一些边界条件、约束条件、中间过程也很绕,所以把这个不是编程题的编程题放在这里解答一下,供参考。

根据题意可知有三种运输方式,分别是往返两次加一次单程,成本为5;往返一次加一次单程,成本为3;一次单程,成本为1. 下面简称T5,T3,T1.  

首先给出最优策略1:用完所有能源,也就是运到终点的能源 + 路上消耗的能源=3000。否则,不论剩余多少能量,我们总可以后退一点,再多装一些,把剩余能量的中的一部分送到终点。

下面引入运输能力这个概念:
以T3举例,从起点向终点方向走2趟,最大可装载2000,运到距离为delta的某点之后,最大剩余2000-delta,因此称T3的运输能力C3 = 2000-delta <= 2000,(delta >= 0)。也就是说,T3最多能运送不超过2000的能量,超过2000就有剩余能量.
同理T5的运输能力C5 = 3000-delta <= 3000,T1的运输能力C1 = 1000 - delta <= 1000.

这样,我们就得出最优策略2:在运输能力范围内,选用成本最低的方式。用R表示剩余未被运输的能量,由策略1和策略2可知,最优的运送方式为:
当2000 <= R <= 3000时, 采用T5方式;
当1000 <= R <= 2000时, 采用T3方式;
当0 <= R <= 1000时, 采用T1方式。
即,先用T5消耗1000,剩余2000之后用T3方式再消耗1000,最后用T1方式运输余下能量。因此最优解为:
T5: 运输距离 x = 1000/5 = 200
T3: 运输距离 y = 1000/3 = 333.333
T1: 运输距离 z =1000 - x - y = 466.667
运送到终点的最大能量 = 1000 - 466.667 = 533.333

证毕.

近一步推广:
首先简化上面的计算过程:  
最大能量 = 1000 - z = 1000 - (1000 - x - y) = x + y = 1000 * (1/3 + 1/5).
现在有初始能量X(假设X可被1000整除,否则可以同理做推广),按照最优策略1和2可得:
因为,最大需要的运输能力的方式Tmax=X/1000 * 2 - 1
所以,能够运输的最大能量 = 1000 * (1/3 + 1/5 + ... + 1/Tmax)
用归纳法很容易证明此结论。

因为1/3+1/5+1/7+...是发散的,所以理论上可以运送任意初始能源X,但是考虑到单程最大能力为1000,只要X比1000多一点,就可以用T3方式先运送一点,再
用T1运送剩余,因此,约束条件为X > 1000.

最后提个问题,如果希望能够卖到集市上1000吨煤,那么最少需要初始有多少吨?


你才山西煤老板!!!

posted on 2011-10-11 11:09 毕达哥拉斯半圆 阅读(2939) 评论(2)  编辑 收藏 引用

评论

# re: 火车运煤,驴子吃萝卜,骆驼吃香蕉 2011-10-11 13:35 cheap lace front wigs

呵呵,不错,有意思  回复  更多评论   

# re: 火车运煤,驴子吃萝卜,骆驼吃香蕉 2011-10-11 13:54 毕达哥拉斯半圆

@cheap lace front wigs
^_^ 你的店也很有意思呀  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年10月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(3)

随笔档案

相册

contact

搜索

最新评论

阅读排行榜

评论排行榜