V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
hxddh2010
V2EX  ›  问与答

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

  •  
  •   hxddh2010 · 2011-05-23 20:39:24 +08:00 · 5953 次点击
    这是一个创建于 4917 天前的主题,其中的信息可能已经有所发展或是发生改变。
    山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?
    15 条回复    1970-01-01 08:00:00 +08:00
    Hyperion
        1
    Hyperion  
       2011-05-23 21:14:22 +08:00
    总共能运三次,好像没有什么办法让任何一次运输产生利益……难道有什么窍门?
    aligo
        2
    aligo  
       2011-05-23 21:37:18 +08:00
    @Hyperion 运3000吨煤需走3次,一共需要往返5次,也就是5000公里,所以。。。
    makestory
        3
    makestory  
       2011-05-23 21:40:02 +08:00
    先说个我的结果的最多是能运500顿煤到市场。
    在仔细验证一下。
    Hyperion
        4
    Hyperion  
       2011-05-23 21:41:40 +08:00
    @aligo ...还有回程...额! 那怎么运...难道答案和超载有关系? 还是有办法不走5000的全程?
    aligo
        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吨

    剩下的就是代入程序进行计算了
    aligo
        6
    aligo  
       2011-05-23 21:47:50 +08:00
    这道题目主要告诉我们的是:煤老板伤不起啊XD
    ray58750034
        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。
    ray58750034
        8
    ray58750034  
       2011-05-23 21:54:50 +08:00
    额,悲剧的, 1000 - (1000-x-y) 应该等于 x+y = 533 。眼花了。
    aligo
        9
    aligo  
       2011-05-23 22:00:11 +08:00
    我也订正一下5楼的那个示例运法,是消耗466吨煤,可剩下的大概533以上534未满
    就像@ray58750034 同学计算的那样
    aligo
        10
    aligo  
       2011-05-23 22:17:30 +08:00
    再订正,是532以上533未满
    然后有好几个地方可以优化,我不知道能否带来更多一点的煤,但至少可以减少机器磨损减少排放
    最典型的就是在199-200公里路段。1公里之前只剩下1吨煤,你需要花2吨煤去运回来那1吨煤
    依次类推,应该可以多少优化一点,这里人脑就无能为力了,交给程序了,大概这里才是面试的目的了
    aligo
        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
    依次类推
    我懒得写程序了=口=
    makestory
        12
    makestory  
       2011-05-23 22:31:40 +08:00
    @aligo 思路很赞!
    最典型的就是在199-200公里路段。1公里之前只剩下1吨煤,你需要花2吨煤去运回来那1吨煤// 似乎不存在这种情况,应该是花2顿煤取4吨媒,总是划算的。
    而且可以不已1km做为迭代搬运的单位,理论可以做到无限小。
    这样到达还剩1000顿的时候,火车的位置应该是533.333..... km 最后的搬运的结果也是这个数字
    EricZ
        13
    EricZ  
       2011-05-23 23:32:11 +08:00
    lanxiaomin
        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吨,应该线性规划能得出更加好的结果。
    lanxiaomin
        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;利用线性规划,得到最优解。(这里并没有考虑到装卸煤所需要的消耗)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5579 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 06:40 · PVG 14:40 · LAX 22:40 · JFK 01:40
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.