小学生的解法:
只要在500K处,存有50升油,汽车就可以到达终点
假设400K处有足够的油,走2趟就可以了,第一趟装50升,放30升,第二趟装30升,到达时还有20升,满足要求。这样,在400K处有80升存放就可以满足要求,显然,第二趟没有充分使用运力,是一种浪费。
所以,干脆在400k处只存放50升,第二趟从300K处取,这样,第一趟还得多留10升的回程油(剩20升),第二趟从300k处运50升,到达500k时,剩余30升,刚好满足要求。
从上面分析知道,如果0k-500k的距离是无限的,每运50升到一个点,在其-100k,-200k处各存放50升,是最有效方案。
但接近起点时,情况会发生变化,所以不能按照此方案无限算下去。
现在,我们的运输目标是,400k 50升,300k 50升
为400k 50升,需要在300k,200k各安排50升
现在的目标:200k50升,300k100升
为300k100升,从200k处运2次各50升,从100k处运2次50升
现在的目标:100k100升,200k150升
为200k150升,从100k运3次各50升,从0k运3次各50升
现在的目标:0k150升,100k250升
为100k250升,从0k运8次50升(每次有效30升),1次20升(有效10升)
现在知道,0k处需要备150+8*50+20=570
这个方案只有一次运输20升有点浪费,基本是最优方案了