汽车加油问题之贪心算法.doc

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