随笔 - 30  文章 - 67  trackbacks - 0
<2011年4月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(8)

随笔分类

随笔档案

文章档案

收藏夹

Oops

搜索

  •  

积分与排名

  • 积分 - 83504
  • 排名 - 275

最新评论

阅读排行榜

评论排行榜

 

题目描述:

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

下面我想阐述下我的思考过程:

确实是个好题,我开始没想到好办法,就开始试了几组数据,大概的思路应该和大家的差不多: 就是设两个中转站,如下图所示:

 

第一次尝试:

具体的过程是这样的:

第一趟: 从采煤区运1000吨煤到200公里处,这时消耗掉200吨,留下600吨,后携带200吨返回。

第二趟: 从采煤区运1000吨煤到200公里处,这时消耗200吨,但是我们增加200吨,这时200公里处剩下400吨,然后继续前行到达500公里处,卸下400吨后返回,在200公里处在添加200吨煤,后返回到采煤区。

第三趟: 从采煤区1000吨煤到200公里处,增加200吨煤,然后继续前行到500这个地方,这时我们的列车上还有700吨煤,我们添加300吨继续前行到集市,我们这时还剩500吨。

所以运送到集市为500吨。

但是我们发现有100吨煤在500公里还没用,说明还有改进空间。

第二次尝试:

但是我发现200公里处是最优的,所以我假设我们需要两个中转站: x1公里处, x2公里处;同时我们令:x1 = 200;

我们按照上面的过程继续 f1 表示x1的剩余量, f2表示 x2的剩余量;

第一趟: f1  =  1000 - 2 * x1; f2  =  0;

第二趟: f1  = 1000 - 4 * x1; f2 =  1000 - 2* (x2-x1);

第三趟: f1 =  1000 - 5 * x1; f2 = 1000 - 2*(x2 – x1) + 1000 – (x2 – x1);

我们发现: 当我们把x1 = 200带入得到: f1 = 0; f2 = 2600 – 3*x2;

我们假设我们取其中的f3 但是f3 <= 1000

最后的载运量令为f = f3 – (1000 – x2);  

所以我们令f3 = 1000 得到f = 1600/3; 最优值大概是533.333…..

故事还没结束:。。。。。

但是我们还没发现完里面的玄机:我们发现 1600/3 – 200 = 1000/3;

这是偶然吗,哦NO, 继续 200 = 1000/5

我们发现0-----x1 火车经过5次, x1 ----x2火车经过3次, 这是偶然吗,当然不是

现在思考整个过程:1000吨在0 ---x1消耗的,需要5次, 同理1000吨是在x1----x2消耗,需要3次。

现在明白了吧其实结果就是1000/5 + 1000/3;

假设现在是4000吨煤呢: 道理很显然了吧 1000/7 + 1000/5 + 1000/3

如果是一般情况呢: n*1000    (n>=2), 显然n = 1 时答案为0

这个结果就是 1000 * (1/3 + 1/5 + 1/7 + ….. + 1 / (2*n-1)), 查了下这是个发散的级数,所以还是比较符合现实规律的, 煤假设是无穷的,那么运的也应该是无穷的。

不知道存在问题不, 希望大家给出

posted on 2011-04-12 23:10 Cunch 阅读(3150) 评论(5)  编辑 收藏 引用 所属分类: YY

FeedBack:
# re: 关于山西煤老板那个面试题自己的想法[未登录] 2011-04-13 10:43 zk
数学太强了,发散的概念早忘记了

我的想法:
假设当前的煤量有L,到下个中转站的距离为x,那么到下一个中转站的可以运到的煤量为 L - (upper(L/1000) * 2 - 1) * x

得到:

2000<= x <= 3000, L - 5x
1000<= x < 2000, L - 3x
0 <= x < 1000, L - x

所以,中转站为200, 1000/3

最后的结果跟lz一样  回复  更多评论
  
# re: 关于山西煤老板那个面试题自己的想法[未登录] 2011-04-13 10:52 cc
@zk
2000<= x <= 3000, L - 5x
1000<= x < 2000, L - 3x
0 <= x < 1000, L - x

条件错了,不好意思

2000<= L <= 3000, L - 5x
1000<= L < 2000, L - 3x
0 <= L < 1000, L - x

ps: upper(L/1000)的意思为向上取整  回复  更多评论
  
# re: 关于山西煤老板那个面试题自己的想法 2011-04-13 11:15 Cunch
@zk
你的想法挺好的,其实就是做到怎么不浪费呗  回复  更多评论
  
# re: 关于山西煤老板那个面试题自己的想法 2011-04-13 14:35 pumpkin
个人感觉作为面试题的话考算法的概率比数学大些吧。
个人想法是dp,f[x]表示在第x公里处最多还能剩的煤数,f[0]=3000。
f[x]=max(f[j]-cost(j,x))(0<=j<x)  回复  更多评论
  
# re: 关于山西煤老板那个面试题自己的想法 2011-04-13 23:24 Cunch
@pumpkin
你的dp似乎有问题, 还有你的blog真吓人  回复  更多评论
  

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