算法-加油问题_第1页
算法-加油问题_第2页
算法-加油问题_第3页
算法-加油问题_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

加油问题 问题描述：一个旅行家想驾驶汽车从城市到城市（设出发时油箱是空的）。给定两个城市之间的距离d1、汽车油箱的容量c、每升汽油能行驶的距离d2、沿途油站数n、油站i离出发点的距离di以及该站每升汽油的价格pi，i=1, 2,n。设d1=0d2 =m1: 在第i站不加油，xi=0。2) r=m1：在第i站加油使车刚好行驶至第j站，xi=m1-r。3) cm1：在第i站加满油，xi=c-r。(2) 为了使汽车到终点时刚好油用完，在终点设一个虚拟油站n+1, 油价pn+1=0。(3) 注意问题可能无解，应判断。算法 CHEAPEST_TRAVEL输入：城市A、B间的距离d1，沿途油站数n，各油站距离出发点的距离数组d1.n, (d0=0), 汽车油箱的容量c, 每升汽油能行驶的距离d2。输出：从城市到城市所花费的最少油费min以及在各油站所加的油量x1.n。若问题无解，则输出No Solution。 dn+1=d1; pn+1=0 /在终点设一个虚拟油站。 d3=c*d2 /d3为油箱加满油时可行驶的距离。/检查问题是否有解。i=1while id3 then /无解输出“No Solution”; returnend ifi=i+1 end while min=0r=0 /出发时油箱为空 for i=1 to n/在第i站：j=i+1while pj=pi /找站i前面油价更便宜的最近一站j。j=j+1end while m1=(dj-di)/d2 /从第i站到第j站需油量m1。if r=m1 then xi=0 /在第i站不加油可至第j站。else if c=m1 then xi=m1-r /在第i站加油使得刚好可至第j 站。r=m1 else xi=c-r ; r=c / 在第i站加满油。end ifend ifmin=min+xi*pi /累加所用油费。 r=r-(di+1-di)/d2 /行驶至第i+1站。 end for return min
人人文库> 全部分类> 应用文书 > 事务文书

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论