你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?
火车运行时,最好让他满载,起始点记为A
第一步,分三次把煤运送到中间点B
第二步,分两次把煤运送到中间点C
第三步,把煤运送到目的地D
第一步:5*(AB) = 1000;解得AB=200
第二步:3*BC = 1000;解得BC=333.
第三步:AB+BC+CD=1000;解得CD=467
因此,做多运送533吨煤到目的地
假定从A到B需要2m+1次,距离为x,那么运过去消耗(2m+1)x的煤。一开始的时候必须(m+1)>=3才可以把煤运完,而且空载是没有哦效率的,所以(m+1)<4.
所以m=2,而m=1是,所剩煤为2000,m=0时,所剩煤为1000.由m值可以得到距离x,和9楼一样。
同时,在m不变的情况下,可以任意分段,比如m=2是,可以把煤运到50处,然后在运到100处,然后再运到200处,由于m都是等于2,所以到200时,总会剩下2000煤。
所以实际上解有无群多,只要让煤在200,533的地方重新聚集就行了。
首先,要获得最大值,必须在最远的中间”补给点”放下等同其路程的煤作为补给。所以接下来要做的就是,如何让2000吨煤放到最远的地方,同时留下“补给煤”。因为条件限制,所以只能分两次达成上面的目标,第一个补给点,他要消耗的是他路程的5倍的煤,因为他自己消耗两次,第二次送煤的消耗两次,最后一次直达终点的要消耗一次。所以他要在1/5的地方放下,第一个点已经提供补给,所以第二点要补给3次,他自己两次,最后直达的一次。所以是在200+333的地方放下333.所以最后到达的,应该是200+333 = 533. 总数是其他值也可以推导出来了
编程的例子就是:
int sum = 3000;
int load_num = 1000;
int result = 0;
int time = sum / load_num – 1;
for (int i = time; i > 0 ; –i) {
result += load_num / ((i*2) + 1);
}