1.7　贪婪算法思想

贪婪算法的思想非常简单而且算法效率很高，在一些问题的解决上有着明显的优势。贪婪算法总是做出在当前看来最好的选择。也就是说，贪婪算法并不从整体最优考虑，它所做出的选择只是局部最优选择。虽然贪婪算法不能对所有问题都得到整体最优解，但对大部分问题它还是能产生整体最优解的。在一些情况下，即使贪婪算法不能得到整体最优解，其最终结果却是最优解的近似解。

1.7.1　算法思路

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

说明　贪婪算法就是通过做局部最优（贪婪）选择来达到全局最优解。使用贪婪算法时，通常采用自顶向下的方法来求解，每一步都使用最贪婪的选择，使原问题变为一个相似的、规模更小的问题。例如，在下面的例子中所举的找零钱的操作中，每一步都选择当前所能选择的最大面额。

贪婪算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出近似解。

由贪婪算法的特点和思路可看出，该算法存在以下问题：

·不能保证最后的解是最优的；

·不能用来求最大或最小解问题；

·只能求满足某些约束条件的可行解的范围。

该算法的实现过程如下：

从问题的某一初始解出发;
while 是否达到（或近似达到）设定总目标
{
求出可行解的一个解元素;
}
由所有解元素组合成问题的一个可行解;

例如，在超市购物，收银员找零钱时，为使找回零钱的纸币张数（或硬币枚数）最少，不考虑找零钱的所有方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是使用贪婪法求解的一个典型例子。

例如，要给顾客找回总额为17元的零钱，按贪婪算法，应找1张10元、1张5元、2张1元的即可（不用再考虑其他找零的解法）。

1.7.2　实例：找零钱

下面编写代码来演示贪婪算法的C程序实现过程。

该程序实现超市收银的找零方案，输入需要找补给顾客的金额，由程序计算出该金额可由哪些面额的人民币组成。

【解题思路】

人民币有100、50、20、10、5、2、1、0.5、0.2、0.1等多种面额（单位为元）。在找零钱时，可有多种方案，例如需找零钱68.90元，至少可有以下方案：

·1张50、1张10、1张5、3张1、1张0.5、2张0.2；

·1张50、1张10、1张5、3张1、1张0.5、4张0.1；

·6张10、1张5、3张1、1张0.5、2张0.2。

如果按贪婪法来求解，则选中第1种方案，即首先从能找的最大面额开始，找1张50面额的，接着剩下的18.90元又可找1张10元面额的，还剩下8.90元……就这样逐步缩小找钱金额。

下面就是用贪婪算法编写的找零钱的C程序。

【程序1-9】用贪婪算法求找零钱方案

1    #include <stdio.h>
2    #define MAXN 9
3    int parvalue[MAXN]={10000,5000,2000,1000,500,200,100,50,20,10}; //定义人民币面额数组
4    int num[MAXN]={0};                    //定义找零钱中各对应面额人民币的数量
5    int exchange(int n)                     //声明函数
6    {
7        int i,j;                            //定义变量
8        for(i=0;i<MAXN;i++)
9            if(n>parvalue[i]) break;        //找到比n小的最大面额 
10        while(n>0 && i<MAXN)
11        {
12            if(n>=parvalue[i])
13            {
14                n-=parvalue[i];
15                num[i]++;
16            }else if(n<10 && n>=5 )
17            {
18                num[MAXN-1]++;
19                break;
20            }else i++;
21        }
22        return 0;
23    }
24    
25    int main()
26    {
27        int i;
28        float m;    
29        printf ("请输入找零的金额: " );
30        scanf("%f",&m);
31        exchange ((int)100*m);                  //调用函数计算结果
32        printf("\n%.2f元零钱的组成:\n",m); 
33        for(i=0;i<MAXN;i++)
34            if(num[i]>0)
35                printf("%6.2f:%d张\n",(float)parvalue[i]/100.0,num[i]); 
36        getch();
37        return 0;
38    }

【程序说明】

·第3行定义了人民币面额数组（以分为单位）。

·第4行定义找零钱中各对应面额人民币的数量，例如，如果10元的有2张，则设置num[2]=2（与parvalue数组中的人民币面额数据对应）。

·第5~23行为计算找零钱的子函数。

·第8~9行为从人民币面额数组中查找比找钱金额小的最大面额。

·第10~21行使用贪婪算法循环计算各面额人民币的张数。共分3种情况：一是找补金额大于指定的面额，则可用该面额，第14行减去该面额，第15行增加该面额的数量；二是找补金额小于1角且大于5分，按四舍五入原则增加一张面额为0.1元的找补数量；三是以上两种情况之外，则增加数组下标i，从更小面额的人民币中去进行找补。

·第25~38为主函数，接收用户输入金额，并调用exchange函数进行运算，最后输出结果。

第30行接收用户输入的实数金额，第31行调用函数exchange时，将用户输入的数据乘以100，转换为以分为单位进行处理。

·第32~35行判断在数组num中，如果对应面额的计数值不为空，则输出。

编程经验　在计算机中，整型数据存储的是精确的值，而浮点型数据存储的是近似值，本例为了使程序运行准确，将金额化为以分为单位进行处理，这样就不用使用小数，而直接使用整数来处理，最后在输出时，再将单位“分”转换为“元”即可。

编译执行以上程序，输入找零金额68.9，结果如图1-14a所示；再次执行程序，输入找零金额35.38，可看到生成的找零为35.40（进行了四舍五入处理），如图1-14b所示。

图1-14　【程序1-9】执行结果

上一章目录下一章