汽车加油问题之贪心算法(一) 问题描述 一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站、指出若要使沿途得加油次数最少,设计一个有效得算法,指出应在那些加油站停靠加油、 给出N,并以数组得形式给出加油站得个数及相邻距离,指出若要使沿途得加油次数最少,设计一个有效得算法,指出应在那些加油站停靠加油。要求:算法执行得速度越快越好、 (二) 问题分析(前提行驶前车里加满油) 对于这个问题我们有以下几种情况:设加油次数为k,每个加油站间距离为a[i];i=0,1,2,3……n 1。始点到终点得距离小于N,则加油次数k=0; 2。始点到终点得距离大于N, A 加油站间得距离相等,即a[i]=a[j]=L=N,则加油次数最少k=n; B 加油站间得距离相等,即a[i]=a[j]=L>N,则不可能到达终点; C 加油站间得距离相等,即a[i]=a[j]=L〈N,则加油次数k=n/N(n%N==0)或k=[n/N]+1(n%N!=0); D 加油站间得距离不相等,即a[i]!=a[j],则加油次数k通过以下算法求解。 (三)算法描述 贪心算法得基本思想 该题目求加油最少次数,即求最优解得问题,可分成几个步骤,一般来说,每个步骤得最优解不一定就是整个问题得最优解,然而对于有些问题,局部贪心可以得到全局得最优解、贪心算法将问题得求解过程瞧作就是一系列选择,从问题得某一个初始解出发,向给定目标推进。推进得每一阶段不就是依据某一个固定得递推式,而就是在每一个阶段都瞧上去就是一个最优得决策(在一定得标准下)。不断地将问题实例归纳为更小得相似得子问题,并期望做出得局部最优得选择产生一个全局得最优解。 贪心算法得适用得问题 贪心算法适用得问题必须满足两个属性: (1) 贪心性质:整体得最优解可通过一系列局部最优解达到,并且每次得选择可以依赖以前做出得选择,但不能依赖于以后得选择、 (2) 最优子结构:问题得整体最优解包含着它得子问题得最优解。 贪心算法得基本步骤 (1) 分解:将原问题分解为若干相互独立得阶段。 (2) 解决:对于每一个阶段求局部得最优解。 (3) 合并:将各个阶段得解合并为原问题得解、 [问题分析] 由于汽车就是由始向终点方向开得,我们最大得麻烦就就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。 提出问题就是解决得开始。为了着手解决遇到得困难,取得最优方案。我们可以假设不到万不得已我们不加油,即除非我们油箱里得油不足以开到下一个加油站,我们才加一次油。在局部找到一个最优得解、却每加一次油我们可以瞧作就是一个新得起点,用相同得递归方法进行下去。最终将各个阶段得最优解合并为原问题得解得到我们原问题得求解。 加油站贪心算法设计(C): include<> include〈studio、h> intadd(intb[],intm,int n)ﻫ { //求一个从m到n得数列得与ﻫ int sb;ﻫ for(inti=m;i<n;i++)sb+=b[i];ﻫ return sb; } intTanxin(int a[n],int N) //a[n]表示加油站得
汽车加油问题之贪心算法 来自淘豆网www.taodocs.com转载请标明出处.