问题描述:
用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑,耗油率为1加仑/公里。由于沙漠中没有油库,必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠,应在什么地方建油库,以及各处的贮油量。
问题如上,是一道非常经典的算法问题
但是我和别人争论了很久
争论是这样的:
这道题网上开始分析时,使用了倒推法,即反着来看(从终点向起点来看)
第一个加油点是距离终点500公里的地方,贮存油量500加仑
而我对此产生了疑问,凭什么这就是最短的呢??
我不能第一个加油点是距离终点300公里的地方,贮存油量300加仑吗?
为什么网上的解答都先入为主得给出了这个500公里的设定而没有一点让人信服的证据呢?