V2EX › lanxiaomin 的所有回复 › 第 1 页 / 共 1 页

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

2014-03-07 16:58:33 +08:00

回复了 hxddh2010 创建的主题 › 问与答 › 在酷壳看到一个分享出来的面试题，觉得很有意思，可以好多种算法和思路

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

2014-03-07 16:51:30 +08:00

回复了 hxddh2010 创建的主题 › 问与答 › 在酷壳看到一个分享出来的面试题，觉得很有意思，可以好多种算法和思路

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