卡车运油一题的求解

本文主要是介绍卡车运油一题的求解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

原题目：假设有一辆车，它的油箱恰好和一个油桶一样大，而且车上恰好可以运载一个油桶。假设一桶油可以让车开一百公里。现在在起点，车装满了油，另外起点还有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，但是具体算法还要再检查一下，再继续发布。

这篇关于卡车运油一题的求解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！