贪心算法汽车加油问题,贪心算法基本思想： 贪心算法总是做出在当前看来是最好的选择，并不会从总体去最优考虑。虽然贪心算法不会对所有问题找到最优，但是有时候会得到最优解的近似解。,贪心算法的基本要素： 1，贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。（是贪心算法和动态规划的主要区别） 2，最优子结构：当一个问题包含其子问题的最优解是称此问题具有最优子结构性质。,问题描述,一辆汽车加满油之后可以行驶n KM ,旅途中有若干个加油站，设计一个算法指出在哪些加油站停靠加油可以是沿途加油次数最少。（给定n和k个加油站位置）,7 1 2 3 4 5 1 6 6,问题分析,1,2,3,4,5,1,6,6,假设Xi表示i-1到i号加油站之间的距离，每一次都是加满油再出发，根据贪心算法的选择性质为了要使加油次数最少就会选择离加满油的点远一点的加油站加油。另外当加满油之后，都要是此后的过程中使加油次数最少，同样，在第二次加满油之后也要使此后的加油次数最少。每一次汽车中剩下的油不能再行驶到下一站就在该站加油，每一次加满油之后与起点具有相同的条件，过程也是相同的。所以说加油次数最少也具有最优子结构的性质。,贪心策略：最远加油站优先。,起点,终点,第一次遍历，主要是看Xi是否大于n，若大于n是到达不了重点的，错误。 第二次遍历，给定s表示加满油之后行驶的距离，如果sn,说明需要加油， 加油次数sum+，s=xi。,int greedy(vectorx, int n) int sum=0;k=x.size(); for(int i=0;in) return -1; for(int i=0,s=0;in) sum+; s=xi; return sum; ,sum=4;,Thank you !,