C语言经典贪心算法之加油站问题（详解）

ゝ一纸荒年。 2023-01-11 01:27 322阅读 0赞

### 文章目录 ###

*   *  一、贪心算法
     *  二、加油站问题

## 一、贪心算法 ##

贪心算法暗示一种不追求最优解，只希望找到较为满意解的方法。贪心算法省去了为找最优解要穷尽所有可能而必须耗费大量时间，因此它一般可以快速得到较为满意的答案。贪心算法常常以当前情况为基础做最优选择，而不考虑各种的整体情况，所以贪心算法不需要回溯。

## 二、加油站问题 ##

**1、问题**  
一辆汽车加满油后可以行驶n千米，旅途中有若干个加油站（加油站是已经确定好的），为了使沿途加油次数最少，设计一个算法，输出最好的加油方案。  
例如：假设沿途有9个加油站，总路程为100千米，加满油后汽车行驶的最远距离为20千米。

**2、C语言解决**

#include <stdio.h>
    #define S 100 //S是全程长度
    void main()
    { 
    	int i, j, n, k=0, total, dist;
    	int x[]= { 10, 20, 35, 40, 50, 65, 75, 85, 100};  //加油站距离起点的位置
    	int a[10];  //选择加油点的位置 
    	n= sizeof(x)/sizeof(x[0]);   //沿途加油站的个数
    	printf("请输入最远行车距离（15<=n<100）：");
    	scanf("%d",&dist);
    	total= dist;  //总行驶的里程 
    	j= 1;  //选择的加油站个数 
    	while(total<S)  //如果汽车未走完全程
    	{ 
    		for(i=k; i<n; i++)
    		{ 
    			if(x[i]>total)  //如果距离下一个加油站太远
    			{ 
    				a[j]= x[i-1];  //则在当前加油站加油
    				j++;
    				total= x[i-1]+dist;  //计算加完油能行驶的最远距离
    				k= i;
    				break; 
    			 } 
    		}
    	} 
    	for(i=1; i<j; i++)  //输出加油点 
    		printf("%4d",a[i]); 
    }

![01][]  
![02][]

《The Function and Algorithm of Program Language C/C++》

[01]: /images/20221119/dcf443e608cd42aaad08651047c96e77.png
[02]: /images/20221119/179345829a864aada05e67e5c7409ceb.png