贪心算法解硬币找零问题

浏览数：22 / 时间：2015年06月08日

假如有一种货币，它有面值为1分、2分、5分和1角的硬币，最少需要多少个硬币来找出K分钱的零钱？

按照贪心算法的思想，需要不断地使用面值最大的硬币。如果要找零的值小于最大的硬币值，则尝试第二大的硬币，依次类推。

代码如下：

#include <iostream>
using namespace std;

#define ONE 1
#define TWO 2
#define FIVE 5
#define TEN 10

int main()
{
    int money;
    int one=0,two=0,five=0,ten=0;
    cout<<"输入要找零的钱（以分为单位）：";
    cin>>money;
    
    //尝试每一种硬币
    while (money>=TEN)
    {
        ten++;
        money-=TEN;
    }
    while (money>=FIVE)
    {
        five++;
        money-=FIVE;
    }
    while (money>=TWO)
    {
        two++;
        money-=TWO;
    }
    while (money>=ONE)
    {
        one++;
        money-=ONE;
    }
    
    //输出结果
    cout<<"1角硬币数："<<ten<<endl;
    cout<<"5分硬币数："<<five<<endl;
    cout<<"2分硬币数："<<two<<endl;
    cout<<"1分硬币数："<<one<<endl;
    
    return 0;
}

虽然贪心算法不是对所有问题都能得到整体的最优解，但是实际应用中的许多问题都可以使用贪心算法得到最优解。有时即使使用贪心算法不能得到问题的最优解，但最终结果也是较优的解

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

贪心算法解硬币找零问题