C/C++程序设计常用算法——贪婪法

文档声明：
以下资料均属于本人在学习过程中产出的学习笔记，如果错误或者遗漏之处，请多多指正。并且该文档在后期会随着学习的深入不断补充完善。

---

资料仅供学习交流使用。
作者：Aliven888

1、简述

  程序设计的关键就是算法，算法简单来说就是程序设计时问题解题步骤或者数据数据的流程。这里我们将介绍以下几种常用的算法：迭代法、穷举法、递推法、递归发、回溯法、贪婪法、查找算法、排序算法。

本章节主要介绍贪婪法。

2、贪婪法

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

优点：

  算法简单，求解速度快。

注意事项：

1. 该算法得到的解并一定是最优解。

代码实例：

//题目：我们拿100元去超市买东西，店主在找零钱时，可选金额有：50元、20元、10元、5元、1元
//  问：店主怎样才能使找零的张数最少？

//分析：使用贪婪算法的原理来解决这个问题时，为了使找的零钱最少，我们可以优先从大面值的金额开始，
//然后依次递减去考虑小面值的金额。

//编程：
void fun(int money)   //入参表示待找零的金额
{
    int iSmallMoneyTable[5] = {50, 20, 10, 5, 1};   //面额表
    int iIndex = 0;  //面值表索引
    int iCurrentMoney = 0; //当前累计金额
    int iHasMoney = money;  //当前还需金额
    int iAllPage = 0;  //当前累计张数

    int iChangeTable[20] = { 0 };  //记录找零
    int iChangeIndex = 0;  //找零的索引 

    while (iIndex < 5)  //金额遍历完，退出
    {
        if (iHasMoney >= iSmallMoneyTable[iIndex])
        {
            iChangeTable[iChangeIndex] = iSmallMoneyTable[iIndex];
            ++iChangeIndex;

            //修改当前还需金额
            iHasMoney = iHasMoney - iSmallMoneyTable[iIndex];
            ++iAllPage;
        }
        else
        {
            ++iIndex;
        }

        //还需找零金额为0时，完成找零，退出循环
        if (iHasMoney <= 0)
        {
            break;
        }
    }

    //打印找零结果
    cout << "本次找零 " << iAllPage << " 张" << endl << money <<" = ";

    for(int i = 0; i < iChangeIndex; ++i)
    {
        if(i == (iChangeIndex - 1))
        {
            cout << iChangeTable[i] << endl;
        }
        else
        {
            cout << iChangeTable[i] << " + ";
        }
    }
}

int main()
{
    fun(98);
    return 0;
}

运行结果：

运行结果