29．95
算法分析
设出发城市为0站，目的城市为n+1站。汽车目前在i站(0≤i≤n)，应加多少油，驶往哪一站可使得整个行程的花费最少。我们不妨采用贪心策略，即下一个目的站的单位油价尽可能低于i站；如果所有可达油站的单位油价都高于i站的话，则下一个目的站的单位油价亦应该尽可能地便宜。为此，我们在由i站直接可达的所有油站j (dj-di≤c*D2，i+1≤j≤n+1) 中，计算两个油站序号：
min1—单位油价低于i站且距离最近(以最小代价到达)的一个油站；
min2—在由i站直接可达的所有油站中，单位油价最便宜（但高于i站）的一个油站；
显然，若min1站存在的话，应成为首选的方向，油箱仅加入驶往min1站所需的油量(
dmin1?di)，以便到达min1站时换上更便宜的汽油；反之，若i站直接可达的所有油站
D2dn?1?di≥c*D2)D2的油价均高于i站，则应选择其中油价最低的min2站作为方向，由于i站的油价比min2站便宜，因此不妨让汽车在i站加满油，或者在直接可达目的城市的情况下(
加入驶往最终目的地所需的油量。问题是，汽车在i站时，油箱可能尚有剩油，设剩余油量rest。因此只要在i站加入C*D2-rest的油量，便可将油箱加满；如果i站直接可达目的城市，则加入
dn?1?di-rest的油量，便可使汽车最终到达目的城市。汽车到达min1站时，D2油箱中的油正好耗尽(rest←0)；否则汽车到达min2站时，油箱内的剩余油量应为rest←rest+
dmin2?di。
D2 我们从0站出发，按照上述方法依次类推，直至到达目的城市n+1为止。设 k—当前站(0≤k≤n+1)；
j—由k站驶往的下一目的站(k k←0； reset←0； cost←0； {出发时的准备} repeat j←k； min1←0； min2←0； while (j if (min1=0)and(pj if j=k {即便在k站装满油，也无法到达任一站点，则失败退出} then begin 输出无解信息；halt；end； {then} if min1>0 {若由k站出发直接可达一个油价更低的油站} then begin need← dmin1?dk； {计算k站加入 D2的油量} if need<0 then need←0 {若min1站位于k站左方，则不需加油} cost←cost+pk*need； {累计费用} rest←0； {汽车抵达min1站时油正好耗尽} k←min1； {由min1出发，继续延伸旅行路线} end；{then} else begin {否则，所有可达油站的油价都高于i站} {若无法直接到达目的城市，则计算油箱在k站满载时需加入的油量；否则计算汽车直达目的城市需新增的油量} if c*D2≤dn+1-dk then need←c*D2-rest else need← dn?1?dk-rest； D2 cost←cost+need*pk； {累计费用} rest←rest+need- dmin2?dk； {计算汽车到达min2站时的 D2剩油量} k←min2； {由min2站出发，继续延伸旅行路线} end；{else} until k=n+1； {直至汽车驶至目的城市为止} 输出总费用cost； 这里需要提醒读者的是，并不是所有具备最优子结构的问题（这些问题的最优解包含其子问题的最优解）都可以采用贪心法。下面，我们来考虑一个经典优化问题的两种变形：