2 qq 33773522 qq_33773522 于 2018.02.12 11:40 提问

关于吉普车穿越沙漠的算法问题 40C

问题描述:

用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑,耗油率为1加仑/公里。由于沙漠中没有油库,必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠,应在什么地方建油库,以及各处的贮油量。

问题如上,是一道非常经典的算法问题
但是我和别人争论了很久

争论是这样的:
这道题网上开始分析时,使用了倒推法,即反着来看(从终点向起点来看)
第一个加油点是距离终点500公里的地方,贮存油量500加仑
而我对此产生了疑问,凭什么这就是最短的呢??
我不能第一个加油点是距离终点300公里的地方,贮存油量300加仑吗?
为什么网上的解答都先入为主得给出了这个500公里的设定而没有一点让人信服的证据呢?

5个回答

zhang886688
zhang886688   2018.02.12 12:01

我觉得不用建油站的,我在车上拉500加仑的油到500公里处加上继续走就是了,您觉得呢。

fire_evil
fire_evil 题目说总装油量是500加仑,就是说不管你在车上怎么装都是装500加仑吧
9 天之前 回复
qq_41733123
qq_41733123 500公里处
9 天之前 回复
qq_33773522
qq_33773522 哈哈哈哈,我一开始也是这么想的,不过好像问题不是这样的,比如说我开200公里,然后用邮箱里的油加100公里的油,再回来花200公里,正好加起来500是这样的
9 天之前 回复
abcfgh
abcfgh   2018.02.12 15:43

这应该是一道面试题:
原题如下
一辆载油500升的汽车从A开往1000公里外的B,已知汽车每公里耗油量为1升,A处有无穷多的油,其他任何地点都没有油,但该车可以在任何地点存放油以备中转,问从A到B最少需要多少油?
解答:
最少耗油的要求,先得有几个前提: 1.汽车到达终点时油箱是空的。2.路上的每一个中转点都没有剩下油。

现在画一个数轴,代表起点到终点的路径,在这个数轴上取m个点,分别记为X(1),X(2),...,X(m)。X(i)表示第i个点到终点的距离。1号点为起点,m号点为终点。所以有X(0)=0,X(m)=1000。设汽车油箱的容量为A,由题目可知A=500。设S(i)表示在第i最少存放多少升油,那么显然S(m)=0,而我们要求的就是S(0)。再设n(i)为从第i-1点到第i点需要的往返次数(注意,一去一回代表一次往返)。好,以上就是需要定义的一些符号,

下面开始推导过程:

从i-1点往i点运油时,最节省的情况是从i-1点出发时应该油箱装满油,然后在i点放下油后回到i-1点时油箱是空的,这时候运油的

效率是最高的。所以有: S(i) = A - [X(i)-X(i-1)] + {A - 2*[X(i) - X(i-1)]}*n(i)。

上式中A - [X(i)-X(i-1)]是最后一次从i-1点到i点油箱中剩下的油;{A - 2*[X(i) - X(i-1)]}*n(i)表示在n(i)次往返过程中总共 在i点存下的油。把上式化简合并一下得到式(1):

S(i) = [n(i) + 1]*A -[2*n(i) + 1]*[X(i) - X(i-1)] -----(1)

又因为到第i点存下的油等于第i-1点存下的油减去从i-1点到i点的总损耗,而从i-1点到i点的总损耗为[2*n(i) + 1]*[X(i) - X(i-1)],所以有下式:

S(i) = S(i-1) -[2*n(i) + 1]*[X(i) - X(i-1)]。

把(1)式带入上式则可得到式(2-1):

S(i-1) = [n(i) +1]*A -----(2-1)

同理有式(2-2)

S(i) = [n(i+1) +1]*A -----(2-2)

用(2-1)减去(2-2)得到式(3):

S(i-1) - S(i) = [n(i) -n(i+1)]*A -----(3)

因为S(i-1) - S(i)表示的是从i-1点到i点的总损耗,而A是固定值,所以由(3)式得知,要使总损耗最小,就需要n(i) - n(i+1)最小

,因为S(i-1) - S(i)必然>0,所以n(i) - n(i+1)>0,且n[i]是整数,所以就有min([n(i) - n(i+1)]) = 1。所以有式(4):

n(i) - n(i+1)= 1==> n(i) = n(i+1) + 1 -----(4)

把式(4)代入式(2-2)就得到式(5):

S(i) =n(i)*A -----(5)

再把式(5)代入式(1)并化简就可以得到式(6):

X(i) - X(i-1) =A/[2*n(i) + 1] -----(6)

X(i) - X(i-1)表示的相邻两点之间的距离,所以显然要达到终点的话就必须有:

又因为n(m)=0,即从最后一个中转点到终点是不需要往返的。再由式(4)就有:n(m-1) = 1,n(m-2) = 2, …,即有n(i) = m-i成立。我们从终点往起点回退,再由上式就有:

所以求出来m=8。但是m=8时,求出来的和 约等于1010.9比1000大,所以不能由式(5)直接算S(0),而应该先算S(1) = (m-1)*A = (8-1)*500 = 3500升。也就是说在第一个中转点应该要存3500升油。然后再算从第0点到第1点的损耗,由前面的计算我们可以得到X(1) = 1000 – (500 + 500/3 + 500/5 + 500/7 + 500/9 + 500/11 +500/13) ≈ 22.433米。

所以从第0点到第1点的总耗损可以由前面的总损耗公式[2*n(i) + 1]*[X(i) - X(i-1)]求出: [2*n(1) + 1]*(22.433- 0) = (2*7 + 1)*22.433 = 336.495

所以总耗油量就约为 3500 + 336.495 = 3836.495升。

题目可归结为求数列 an=500/(2n+1) n=0,1,2,3......的和Sn什么时候大于等于1000,解得n> 6   当n=6时,S6=977.57

所以第一个中转点离起始位置距离为1000-977.57=22.43公里

 所以第一次中转之前共耗油 22.43*(2*7+1)=336.50升
  此后每次中转耗油500升
  所以总耗油量为7*500+336.50=3836.50升

转自 http://blog.csdn.net/taoqick/article/details/12432769

qq_16669583
qq_16669583   2018.02.12 15:51

个人感觉这辆车在建立临时油库时,需要不断来回跑,你建立500公里的油库总比建立700公里的优酷所耗费的油量要少,最后一次通过沙漠的油是固定的

bky_lb
bky_lb   2018.02.12 13:10

这个问题可以抽象为:有三个点ABC,A到C的距离是固定的,B点在它们中间。总路程为A到B的距离+B到A的距离+A到C的距离,就可以推出当B越靠近A(或者说越远离C)的时候,总路程越短。这个题目里面B到C的距离最大就是500,所以取了500。可能比较抽象了,但是就是这个意思。

asd1374016245
asd1374016245 吉普车自身需要油耗,保证自身往返建立油库的前提是保证 往返油量+可用建油库油量;距离1000KM,单次最大载油量500加仑,油耗是1加仑/KM,注定了最小公倍数刚好1000,所以倒推方式,最后一次行程走500KM,是最优算法。(如果 总行程、最大载油量、油耗,不是倍数关系,那么答案就会如楼主所说,可以有多解)
9 天之前 回复
TheSaviour
TheSaviour   2018.02.12 15:17

题目要求“**先用这辆车在沙漠中建立临时油库**”,因此临时油库的油也是靠吉普车往返运送的,总耗油量大大超过1000公里的耗油量,正向计算比较困难,所以反着推最后一次加满500跑到终点燃油消耗完毕才能实现耗油最少。因此最后一个加油站应该距终点500公里。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!