EEPW论坛

   贪心算法是指在解决问题时，总是选择出就当前情况看来，最好的方案。换个说法就是，贪心算法不是对整体来考虑最优解，而是考虑在某种情况下的局部最优解。

   贪心算法的基本思路是从问题的某一个初始解出发，然后一步一步，每一步都要确保该解在某种意义上是这一步的最优解。每一步只考虑一个满足局部最优的数据。最后直到枚举完所有数据，或者不能再添加算法为止。

   贪心算法的一般解题步骤为：
   1、建立数学模型来面熟问题；

   2、将求解的问题按照要求分解成若干个子问题；

   3、求出每一个子问题的局部最优解；

   4、把每一个子问题的解合成原来问题的一个解。

   其实贪心算法在日常生活中也很常见，每一个人也都经历过。比如，在一堆面值不等的钞票中，选取N次，每次只能选取一张钞票，最多可以得到多少价值的钞票？很显然，每一次选取，自然而然地，就会尽可能选取面值最大的那一张钞票，这里就运用到了贪心算法。这里将‘最多可以得到多少价值的钞票’这个总问题分解成‘每一次尽可能选取面值最大的那一张钞票’，最后将每一个子问题的最优解合成原来问题的解。

   举个简单的例子，我们所熟知的选择排序，其实选择的就是贪心算法的策略。

算法如下：

#include<stdio.h>
int main()
{
    int a[10] = { 0 };
    int i, j, temp = 0;
    printf("请输入要比较的值：");
    for (i = 0; i < 10; i++)           //遍历数组给入值
    {
        scanf_s("%d", &a[i]);
    }
    for (i = 0; i < 10 - 1; i++)
    {
        for (j = i + 1; j < 10; j++)
        {
            if (a[i] > a[j])
            {
                temp = a[i];     //交换变量
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    for (i = 0; i < 10; i++)        //遍历数组输出
    {
        printf("%d\n", a[i]);
    }
    return 0;
}

它每次从未完成排序的数据中选取最小值，并把最小值放在未完成排序数据的起始位置，直到所有数据完成排序，程序结束。

今天的分享就到这里！