汽车加油问题（贪⼼算法）
1.问题描述：⼀辆汽车加满油后可⾏驶nkm。旅途中有若⼲加油站。设计⼀个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。
算法设计：对于给定的n和k个加油站位置，计算最少加油次数。
数据输⼊：n：表⽰汽车加满油后可⾏驶nkm
k：旅途中有k个加油站
k+1个整数：表⽰第k个加油站与第k-1个加油站之间的距离。第0个加油站表⽰出发地，汽车已加满油。第k+1个加油站表⽰⽬的地。数据输出：最少加油次数和具体在哪⼏个加油站加油。
例如： n=7  k=7
K+1个整数：1 2 3 4 5 1 6 6
最优值：4
2.相关代码：
#include<stdio.h>
#define M 100
int main(){
int stations[M];//⼋个间距
int ins; //油箱满的时候可以⾛的距离
int num;//中间加油站的数量
int i;
int all=0;//总的加油次数
汽车问题
int lv;//油箱中的油量可以⾛的距离
printf("请输⼊加油站的距离和数量\n");
scanf("%d%d",&ins,&num);
lv=ins;//油量赋初值
printf("请输⼊加油站间的距离\n");
for(i=0;i<num+1;i++){
scanf("%d",&stations[i]);
}
printf("加油站间的距离分别为：\n");
for(i=0;i<num+1;i++){
printf("%d  ",stations[i]);
}
puts("");
for(i=0;i<num+1;i++){//如果油量可以⽀撑下⼀段路，则继续⾛
if(stations[i]>ins) {
printf("汽车不可能达到终点站");
return 0;
}
if(lv>=stations[i]){
lv-=stations[i];
}
else {  //否则加满油
lv=ins-stations[i];
all++;
}
}
printf("需要加油的总的加油站数量\n");
printf("%d\n",all);//输出总的加油次数
}
3.问题分析与解题思路
如果要使⽤贪⼼算法解决问题，那么需要检查每⼀⼩段路程是否超过汽车满油量时的最⼤⽀撑路程。如果有超过的，那么汽车不可能⾛完这段路。否则，到汽车满油量时的最⼤⽀撑路程范围内的最后⼀个加油站，加油后继续⽤此⽅法前进