这是一个创建于 4968 天前的主题，其中的信息可能已经有所发展或是发生改变。
山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
 |
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；利用线性规划，得到最优解。（这里并没有考虑到装卸煤所需要的消耗） |
Select Language