贪心算法——找零钱

人民币有100、50、10、5、2、1、0.5、0.2、0.1等多种面额（单位为：元）。例如需补零钱68.9元，至少有以下方案：
1.1张50、1张10、1张5、3张1、1张0.5、2张0.2；
2..1张50、1张10、1张5、3张1、1张0.5、4张0.1；
3.6张10、1张5、3张1、1张0.5、2张0.2
我们要找的就是张数最少的那种方方案。
给出代码：
转换成单位为：分；便于计算。

#define MAXN 9
int parvalue[MAXN] = { 10000,5000,1000,500,200,100,50,20,10 };
int num[MAXN] = { 0 };

int exchange(int n)
{
    int i, j;
    for (i=0;i<MAXN;i++)
    {
        if (n > parvalue[i])
            break;//找到比n小的最大面额
    }
    while (n>0 && i<MAXN)
    {
        if (n>= parvalue[i])
        {
            n -= parvalue[i];
            num[i]++;
        }else if (n<10 && n>=5)
        {
            num[MAXN - 1]++;
            break;
        }
        else i++;
    }
    return 0;
}

最后

以上就是整齐白猫为你收集整理的贪心算法——找零钱的全部内容，希望文章能够帮你解决贪心算法——找零钱所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。