算法-加油问题.doc

《算法-加油问题.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、加油问题●问题描述：一个旅行家想驾驶汽车从城市Ａ到城市Ｂ（设出发时油箱是空的）。给定两个城市之间的距离d1、汽车油箱的容量c、每升汽油能行驶的距离d2、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i]，i=1,2,…,n。设d[1]=0

2、能少。●贪心算法：分析：(1)设在第i站，汽车油箱剩余油量为r,前面油价更便宜的最近一站为第j站，从第i站到第j站需油量m1,则在第i站应加的油量x[i]分下列三种情况计算：1)r>=m1:在第i站不加油，x[i]=0。2)r=m1：在第i站加油使车刚好行驶至第j站，x[i]=m1-r。3)c

3、油站数n，各油站距离出发点的距离数组d[1..n],(d[0]=0),汽车油箱的容量c,每升汽油能行驶的距离d2。输出：从城市Ａ到城市Ｂ所花费的最少油费min以及在各油站所加的油量x[1..n]。若问题无解，则输出NoSolution。d[n+1]=d1;p[n+1]=0//在终点设一个虚拟油站。d3=c*d2//d3为油箱加满油时可行驶的距离。//检查问题是否有解。i=1whilei<=nifd[i+1]-d[i]>d3then//无解输出“NoSolution”;　returnendifi=i+1endwhilemin=0r

4、=0//出发时油箱为空fori=1ton//在第i站：j=i+1whilep[j]>=p[i]//找站i前面油价更便宜的最近一站j。j=j+1endwhilem1=(d[j]-d[i])/d2//从第i站到第j站需油量m1。ifr>=m1thenx[i]=0//在第i站不加油可至第j站。elseifc>=m1thenx[i]=m1-r//在第i站加油使得刚好可至第j站。r=m1elsex[i]=c-r;r=c//在第i站加满油。endifendifmin=min+x[i]*p[i]//累加所用油费。r=r-(d[i+1]-d[i

5、])/d2//行驶至第i+1站。endforreturnmin,x[1..n]endCHEAPEST_TRAVEL●最坏情况下的时间复杂性：Θ(n2)