Posted by: sharkmao | 4月 18, 2011

运煤

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

From http://coolshell.cn/articles/4429.html

发表在 IQ

«
»

回应

  1. 1.每次出发都要装满
    2.每一次到达的地点比前一次远
    3.最后一次把前面几次卸下的煤都捎上直到终点

    3000吨, 每次最多1000吨, 运3次, 假设第一次在x, 第二次在y

    第一次和第二次都会重复走两遍x, 第三次走一遍, 5x=1000 => x=200
    第二次y点卸下的煤是1000+2x-2y, 到达终点的煤是x+(1000+2x-2y) = 1600-3y

    约束条件:
    1. y点卸下的煤1000+2x-2y>=0
    2. 第三轮经过y点捎上剩下的所有的煤后总量不超过1000, (1000-(y-x))+(1000+2x-2y)>=0

    1,2=> 1600/3 <= y <=600

    Max(1600-2y) = 1600/3

    By: sharkmao on 4月 19, 2011
    at 5:00 下午

    回复

  2. 1.由于火车耗煤速度和其载重速度无关，所以最优化原则应该是每次火车都满载出发
    2.把完成一次将所有煤炭运到一个地点作为一轮。
    3.那么第一轮则至少需要三次完成，同样为了让下一轮最优化，第二轮运煤次数应该是2或者1，这样，为了将3000吨煤运到一个指定地点的就为(delta N)*1000/(2*2+1)，delta N是指第一轮运煤次数和第二轮与煤次数的差值，假设为1，则第一次地点为1000/5，同理，再下一轮应为，1000/（2*1+1）=1000/3，最后剩下1000，由第三轮带走。由于已经将1000的煤运到1000/5+1000/3，所以最终可以运到终点的煤为1000/5+1000/3。如果delta N = 2，则得到2000/5。从1000/5+1000/3可以推导出，轮数越低的地方，运煤代价越高，由于最后Delta N的总和是一定的，所以为了最优化，delta N应该取最小，即1。
    4.可以依次推导出，把4000，5000， etc运到目的地的最佳答案。

    5.变形1：如果是3500
    想法，用500的将3000吨的煤搬到一个位置，然后后续的如上

    变形2：如果煤有很多很多，应该怎么运
    想法，应该没变，最后可以运的煤的总量
    1000/（2N-1）+1000/（2N-3)+1000/（2N-5)+…一旦超过1000，则即停止。
    还需要再想想…

    By: chinabenniao on 4月 19, 2011
    at 5:11 下午

    回复

  3. 评论里面有别人的思路
    http://coolshell.cn/articles/4429.html

    By: sharkmao on 4月 19, 2011
    at 5:17 下午

    回复


留下评论

分类