欢迎来到天天文库
浏览记录
ID:55412054
大小:15.50 KB
页数:4页
时间:2020-05-12
《算法-加油问题.doc》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、加油问题●问题描述:一个旅行家想驾驶汽车从城市A到城市B(设出发时油箱是空的)。给定两个城市之间的距离d1、汽车油箱的容量c、每升汽油能行驶的距离d2、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i],i=1,2,…,n。设d[1]=02、能少。●贪心算法:分析:(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)c3、油站数n,各油站距离出发点的距离数组d[1..n],(d[0]=0),汽车油箱的容量c,每升汽油能行驶的距离d2。输出:从城市A到城市B所花费的最少油费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=0r4、=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[i5、])/d2//行驶至第i+1站。endforreturnmin,x[1..n]endCHEAPEST_TRAVEL●最坏情况下的时间复杂性:Θ(n2)
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)c3、油站数n,各油站距离出发点的距离数组d[1..n],(d[0]=0),汽车油箱的容量c,每升汽油能行驶的距离d2。输出:从城市A到城市B所花费的最少油费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=0r4、=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[i5、])/d2//行驶至第i+1站。endforreturnmin,x[1..n]endCHEAPEST_TRAVEL●最坏情况下的时间复杂性:Θ(n2)
3、油站数n,各油站距离出发点的距离数组d[1..n],(d[0]=0),汽车油箱的容量c,每升汽油能行驶的距离d2。输出:从城市A到城市B所花费的最少油费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)
此文档下载收益归作者所有