卡车运油一题的求解

这是天涯上很久以前的一个帖子,多年前求解过,但是具体过程写得不好,自己都看得都晦涩了。所以重新写一遍。

原题目:假设有一辆车,它的油箱恰好和一个油桶一样大,而且车上恰好可以运载一个油桶。假设一桶油可以让车开一百公里。现在在起点,车装满了油,另外起点还有100桶油。问,这车通过运油并途中自加油的方式,最远能离开起点多远?

首先简化一下题目,一桶油可以走一个单位长度(不用100公里,这样后面容易折算一些)
从某一个途中点A(i)运油到下一个途中点A(i+1),可作以下考虑:
1、把车辆的油箱里的油也计入,出发点A(i)有x桶油(x可以为小数),下一个加油点A(i+1)有y桶油(y也可以是小数)
2、为保证最大化运油效率,卡车从A(i+1)返回A(i)时,油箱留存的一点点油应该恰好用完,设距离为s,因此单程的油量也是s
3、总的往返次数为2m+1,其中返回次数为m,由1、2可得,x-y=(2m+1)*s。这里2m是往返m次,1是最后一次前往第i+1点。
4、前m次去,肯定要把油装满,即2桶油,去的路上用掉了s桶油,然后再装s桶油返回第i点,所以可以推论出:前m次实际运到的油量为(2-2*s)*m。(此处隐含了一个条件 s < 1)
5、最后一次前往第i+1点时,第i点剩下的油为 x-2m,然后把这剩下的油拖到第i+1点后,最后一次能运到第i+1点的油量为 x-2m-s。
6、考虑一种意外的情况,即到最后一次,由于第i点剩余的油量不足s了,就不值得回去了。这样是不是会因此而浪费一部分油呢?其实不会,如果出现这种情况,就应该缩小s,以满足最后一次的效率。当然最好的方案是,最后一次也能拉满,即也拉上 2桶油,即 x-2m = 2。
7、思考到这里,发现每次循环中 s 的设定,只有满足 x-2m = 2是效率最高的,即每个途中点的油量必须是 2的整数倍数。
8、由于起点(定义为第1点)的油量为101,不是2的整数倍数。所以在第2个点就必须设法将其凑整为2的整数倍数,最近的一个数就是100。这样,第一个关键问题,就是要用1的油耗量,让s尽可能的远。根据分析3,1=(2m+1)*s,其中m=50(因为先得把100桶油运走)。故 s=1/101。
9、  继续考虑到第3点,运到第3点98个油量,总油耗为2=(2m+1)*s,其中m=48,解得s=2/97
10、继续考虑到第4点,运到第4点96个油量,总油耗为2=(2m+1)*s,其中m=47,解得s=2/95
11、继续考虑到第5点,运到第4点94个油量,总油耗为2=(2m+1)*s,其中m=46,解得s=2/93
12、以此类推,卡车运油一题的求解,其中最后一个 2,是最后一次用2桶油不跑往返,直接跑直线的距离。上式使用电子表格可计算得5.86524。

以上的分析8,不一定是最优方案。以前用模拟退火,算到过5.87,但是具体算法还要再检查一下,再继续发布。

上一篇:记录两张数据库表及Ibatis操作


下一篇:[NOIP2020]移球游戏