1
Hyperion 2011-05-23 21:14:22 +08:00
总共能运三次,好像没有什么办法让任何一次运输产生利益……难道有什么窍门?
|
3
makestory 2011-05-23 21:40:02 +08:00
先说个我的结果的最多是能运500顿煤到市场。
在仔细验证一下。 |
5
aligo 2011-05-23 21:46:22 +08:00
基本思考方式是:
拿起1000吨煤,运到1公里处,放下998吨,反复5次。即消耗5吨煤,将2995吨煤运送1公里。在200公里处还能剩下2000吨煤 然后拿起这次只需要消耗3吨煤,即可将所有煤搬运1公里,在约534公里处,剩下不到1000吨煤,一次性走完全程 最后可剩下466吨煤 但是其实这里有可优化的地方,但至少能得出一个关键结论:2000吨以上煤前进1km需要消耗5吨,1000吨以上煤前进1km需要消耗3吨 剩下的就是代入程序进行计算了 |
6
aligo 2011-05-23 21:47:50 +08:00
这道题目主要告诉我们的是:煤老板伤不起啊XD
|
7
ray58750034 2011-05-23 21:50:06 +08:00
需要有两个返回点,假设为x y。
3000 - 5x = 2000 2000 - 3y = 1000 x = 200, y = 333 可运回的煤 = 3000 - 5x - 3y - (1000-x-y) = 1000 - (1000-x-y) = 467。 |
8
ray58750034 2011-05-23 21:54:50 +08:00
额,悲剧的, 1000 - (1000-x-y) 应该等于 x+y = 533 。眼花了。
|
9
aligo 2011-05-23 22:00:11 +08:00
我也订正一下5楼的那个示例运法,是消耗466吨煤,可剩下的大概533以上534未满
就像@ray58750034 同学计算的那样 |
10
aligo 2011-05-23 22:17:30 +08:00
再订正,是532以上533未满
然后有好几个地方可以优化,我不知道能否带来更多一点的煤,但至少可以减少机器磨损减少排放 最典型的就是在199-200公里路段。1公里之前只剩下1吨煤,你需要花2吨煤去运回来那1吨煤 依次类推,应该可以多少优化一点,这里人脑就无能为力了,交给程序了,大概这里才是面试的目的了 |
11
aligo 2011-05-23 22:24:33 +08:00
程序的写法应该是:
给每一块煤都单独建立一个用于跟踪的实例,把车当成一个,记录下此煤在每次路段的移动成本 设煤A在X-Y路段的运输成本为=1或2(取决于是否需要空车往返回)/一起运输的煤总量 如果设煤A在X-Y路段的运输成本大于1,那就可以抛弃此煤 同时煤A-Z的集合在X-Y路段的运输成本大于26,就可以抛弃此煤A-Z 依次类推 我懒得写程序了=口= |
12
makestory 2011-05-23 22:31:40 +08:00
@aligo 思路很赞!
最典型的就是在199-200公里路段。1公里之前只剩下1吨煤,你需要花2吨煤去运回来那1吨煤// 似乎不存在这种情况,应该是花2顿煤取4吨媒,总是划算的。 而且可以不已1km做为迭代搬运的单位,理论可以做到无限小。 这样到达还剩1000顿的时候,火车的位置应该是533.333..... km 最后的搬运的结果也是这个数字 |
13
EricZ 2011-05-23 23:32:11 +08:00
|
14
lanxiaomin 2014-03-07 16:51:30 +08:00
我觉得这个问题,可以用数学里的线性规划来做,先假设一公里耗一吨煤是可以均分的(就是0.5公里耗去0.5吨煤),那么火车第一回合中一定是要运三次的,假定火车走了X公里后卸下煤,回头再拉,则3000吨拉到x处时剩下:3000-6x吨(如果只有一个回合,那么往返必然会耗去最多的煤),所以1000=<3000-6x<=2000; 第二回合最多运两次:3000-6x-4y<=1000; 最多运到的煤为t=3000-6x-4y-x-y;三个条件来做线性规划;
但从直观上简化 第一回合运200公里,则3000-1200=1800;第二回合运200公里,1800-800=1000;第三回合直接运到集市则 1000-400=600吨,应该线性规划能得出更加好的结果。 |
15
lanxiaomin 2014-03-07 16:58:33 +08:00
就简单处理,第一回合(就是一定要来回三次)运200公里 3000-1200=1800;第二回合一样200公里则1800-800=1000;第三回合:1000-400=600吨;
如果用线性规划则:第一回合x公里 1000<3000-6x<=2000;第二回合 y公里 0<3000-6x-4y<=1000;第三回合 运到集市的煤为t=3000-6x-4y-x-y;利用线性规划,得到最优解。(这里并没有考虑到装卸煤所需要的消耗) |