在酷壳看到一个分享出来的面试题，觉得很有意思，可以好多种算法和思路

[hxddh2010]

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

[Hyperion]

总共能运三次，好像没有什么办法让任何一次运输产生利益……难道有什么窍门？

[aligo]

@Hyperion 运3000吨煤需走3次，一共需要往返5次，也就是5000公里，所以。。。

[makestory]

先说个我的结果的最多是能运500顿煤到市场。
在仔细验证一下。

[Hyperion]

@aligo ...还有回程...额! 那怎么运...难道答案和超载有关系? 还是有办法不走5000的全程?

[aligo]

基本思考方式是：
拿起1000吨煤，运到1公里处，放下998吨，反复5次。即消耗5吨煤，将2995吨煤运送1公里。在200公里处还能剩下2000吨煤
然后拿起这次只需要消耗3吨煤，即可将所有煤搬运1公里，在约534公里处，剩下不到1000吨煤，一次性走完全程
最后可剩下466吨煤

但是其实这里有可优化的地方，但至少能得出一个关键结论：2000吨以上煤前进1km需要消耗5吨，1000吨以上煤前进1km需要消耗3吨

剩下的就是代入程序进行计算了

[aligo]

这道题目主要告诉我们的是：煤老板伤不起啊XD

[ray58750034]

需要有两个返回点，假设为x y。
3000 - 5x = 2000
2000 - 3y = 1000
x = 200, y = 333
可运回的煤 = 3000 - 5x - 3y - (1000-x-y) = 1000 - (1000-x-y) = 467。

[ray58750034]

额，悲剧的， 1000 - (1000-x-y) 应该等于 x+y = 533 。眼花了。

[aligo]

我也订正一下5楼的那个示例运法，是消耗466吨煤，可剩下的大概533以上534未满
就像@ray58750034 同学计算的那样

[aligo]

再订正，是532以上533未满
然后有好几个地方可以优化，我不知道能否带来更多一点的煤，但至少可以减少机器磨损减少排放
最典型的就是在199-200公里路段。1公里之前只剩下1吨煤，你需要花2吨煤去运回来那1吨煤
依次类推，应该可以多少优化一点，这里人脑就无能为力了，交给程序了，大概这里才是面试的目的了

[aligo]

程序的写法应该是：
给每一块煤都单独建立一个用于跟踪的实例，把车当成一个，记录下此煤在每次路段的移动成本
设煤A在X-Y路段的运输成本为=1或2(取决于是否需要空车往返回)/一起运输的煤总量
如果设煤A在X-Y路段的运输成本大于1，那就可以抛弃此煤
同时煤A-Z的集合在X-Y路段的运输成本大于26，就可以抛弃此煤A-Z
依次类推
我懒得写程序了=口=

[makestory]

@aligo 思路很赞！
最典型的就是在199-200公里路段。1公里之前只剩下1吨煤，你需要花2吨煤去运回来那1吨煤// 似乎不存在这种情况，应该是花2顿煤取4吨媒，总是划算的。
而且可以不已1km做为迭代搬运的单位，理论可以做到无限小。
这样到达还剩1000顿的时候，火车的位置应该是533.333..... km 最后的搬运的结果也是这个数字

[EricZ]

找到一个比较好的解法：

http://blog.csdn.net/wormsun/archive/2011/04/22/6342943.aspx

[lanxiaomin]

我觉得这个问题，可以用数学里的线性规划来做，先假设一公里耗一吨煤是可以均分的（就是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吨，应该线性规划能得出更加好的结果。

[lanxiaomin]

就简单处理，第一回合（就是一定要来回三次）运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；利用线性规划，得到最优解。（这里并没有考虑到装卸煤所需要的消耗）