贪心算法简介

        贪心思想简介：“贪心”二字指对最优解的追求，贪心算法是一种求解最优化问题的方法。它从某个初始解出发，通过在每一步选择当前状态下的最佳选择，逐步构造出全局最优解。

        贪心算法一般用于局部最优解累加即为整体最优解的情况，也就是说它并不是任何情况下都适用，需要结合经验判断能否使用。

一般贪心算法的结构如下：

分析问题——执行第一步的最优解——更新问题状态——执行第二步的最优解——持续迭代直到执行最后一步——得到最优解。

示例：现在一位商人需要打包货物上船，这些货物轻重各异，但价值相等，当货物重量超出船载重量就会沉船，请求出能装载的最多件数。

输入格式：  第一行输入总货物件数和船载重量

                    第二行输入每件货物的重量

输出格式：  输出一个整数n表示最多件数。

样例输入：

4 300
20 30 90 210

样例输出：

3

代码展示：

#include <stdio.h>
#include <stdlib.h>
//比较函数 
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() 
{
    int n, capacity;
	//输入总货物件数和船载重量
    scanf("%d %d", &n, &capacity);   
    int weights[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &weights[i]);
    }
    qsort(weights, n, sizeof(int), compare);
	//按重量大小排序，以便贪心选择 
    int count = 0,totalWeight=0;
    for (int i = 0; i < n; i++)
	{
        if (totalWeight + weights[i] <= capacity) 
		{
            totalWeight += weights[i];
            count++;
        } 
		else 
		{
            break;
        }
    } 
    printf("%d", count);
    return 0;
} 

此处使用的贪心算法是：每次装载货物的操作中，挑选当前操作下的最优解——选择重量最轻的货物装载。代码中利用qsort()函数对数组进行排序，以便我们进行最优解的选择

接下来我们看一个例题。

一个长条形花坛，一些地方已经种上了花，花不能种在相邻的地上，不然就会因为争夺水源而死去。
现在用一个整数数组表示花坛，0表示没种花，1表示种花了，求出最多还能种几朵花。

样例输入

7
1 0 0 0 1 1 0

样例输出

1

代码示例：

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int flowerbed[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &flowerbed[i]);
    }
    int count = 0;
    int i=0;
    while(i<n)
    {
    	if(flowerbed[i]==1)
		{
			i+=2;
		 }
		else if(flowerbed[i]==0&&flowerbed[i+1]==1)
		{
			i+=3;
		}
		else if(flowerbed[i]==0&&flowerbed[i-1]==1&&i>0)
		{
			i+=1;
		}
		else
		{
			i+=2;
			count++;
		}
	}
    printf("%d\n", count);
    return 0;
}

题解：

本题采用的贪心策略为尽可能地在每一步可以种花的地方种花，即追求局部最优解，如此循环过整个数组花坛之后得到整体最优解。在循环体中采用了不同的递增数来规避无意义的循环。如已检测到flowerbed[i]==1，那么flowerbed[i+1]必然不可能种花，故直接+2。