2.4 贪心法

2.4.1 贪心法的设计思想

贪心法（greedymethod）是把一个复杂问题分解为一系列较为简单的局部最优选择，每一步选择都是对当前解的一个扩展，直到获得问题的完整解。正如其名字一样，贪心法在解决问题的策略上目光短浅，只根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。例如用贪心法求解付款问题：假设有面值为{5元、2元、1元、5角、2角、1角}的货币若干张，需要付款4元6角现金，如何付款才能使付出货币的数量最少？付款问题的贪心选择策略是，在不超过应付款金额的条件下，选择面值最大的货币。首先选出1张面值不超过4元6角的最大面值的货币，即2元；再选出1张面值不超过2元6角的最大面值的货币，即2元；再选出1张面值不超过6角的最大面值的货币，即5角；再选出1张面值不超过1角的最大面值的货币，即1角。总共付出4张货币。

显然，贪心法的关键是设计合理的贪心选择策略。在本书中，哈夫曼算法、Prim算法、Kruskal算法、Dijkstra算法等都是贪心法的应用实例。

2.4.2 算法设计实例——埃及分数

【问题】 埃及同中国一样，也是世界文明古国之一。古埃及人只用分子为1的分数，在表示一个真分数时，将其分解为若干个埃及分数之和，例如：7/8表示为1/2+1/3+1/24。设计程序把一个真分数表示为最少的埃及分数之和的形式。

【想法】 一个真分数的埃及分数表示不是唯一的，例如：7/8又可以表示为1/8+1/8+1/8+1/8+1/8+1/8+1/8。显然，把一个真分数表示为最少的埃及分数之和的形式，其贪心策略是选择真分数包含的最大埃及分数，以7/8为例，7/8＞1/2，则1/2是第一次贪心选择的结果；7/8-1/2=3/8＞1/3，则1/3是第二次贪心选择的结果；7/8-1/2-1/3=1/24，则1/24是第三次贪心选择的结果，即7/8=1/2+1/3+1/24。

接下来的问题是：如何找到真分数包含的最大埃及分数？设真分数为A/B，B除以A的整数部分为C，余数为D，则有下式成立：

B=AC+D

即

B/A=C+D/A＜C+1

则

A/B＞1/（C+1）

1/（C+1）即为真分数A/B包含的最大埃及分数。设E=C+1，由于

A/B-1/E=（AE-B）/（BE）

则真分数减去最大埃及分数后，得到真分数（AE-B）/（BE），该真分数可能存在公因子，需要化简，可以将分子和分母同时除以最大公约数。

【算法】 设函数EgyptFraction实现埃及分数问题，其算法描述如下 ：

【程序】 主函数首先接收从键盘输入的分子A和分母B，然后调用函数EgyptFraction将该真分数表示为埃及分数之和，在表示过程中需要调用函数CommonFactor求A和B的最大公约数并对A/B进行化简。程序如下：

            #include＜stdio.h＞                  //使用库函数printf和scanf
            voidEgyptFraction（intA，intB）；    //函数声明，表示埃及分数
            intCommonFactor（intm，intn）；      //函数声明，求最大公约数
                                                 //空行，以下是主函数

            intmain（）
            {
              intA，B；
              printf（＂请输入真分数的分子：＂）;//输出提示信息
              scanf（＂%d＂，&A）；
              printf（＂请输入真分数的分母：＂）;//输出提示信息
              scanf（＂%d＂，&B）；
              EgyptFraction（A，B）；            //函数调用，表示真分数A/B
              return0；                          //将0返回操作系统，表明程序正常结束
            }
                                                 //空行，以下是其他函数定义
            voidEgyptFraction（intA，intB）
            {                                    //函数定义，把真分数表示为最少的埃及分数之和
              intE，R；
              printf（＂%d/%d=＂，A，B）；       //输出真分数A/B
              do
              {
                  E=B/A+1；                      //求真分数A/B包含的最大埃及分数
                  printf（＂1/%d＂，E）；        //输出1/E
                  printf（＂+＂）；
                  A=A*E-B；                      //以下两条语句计算A/B-1/E
                  B=B*E；
                  R=CommonFactor（B，A）；       //函数调用，求A和B的最大公约数
                  if（R＞1）                     //最大公约数大于1，即A/B可以化简
                  {
                    A=A/R；B=B/R；               //将A/B化简
                  }
              }while（A＞1）；                   //当A/B不是埃及分数时执行循环
              printf（＂1/%d\n＂，B）；          //输出最后一个埃及分数1/B
              return；                           //结束函数EgyptFraction的执行
            }
            intCommonFactor（intm，intn）        //函数定义，求m和n的最大公约数
            {
              intr=m% n；
              while（r！=0）                     //当余数不为0时执行循环
              {
                  m=n；
                  n=r；
                  r=m% n；
              }
              returnn；                          //返回最大公约数n
            }