贪心算法——找零钱

92 阅读 0 评论 61 点赞

我是靠谱客的博主整齐白猫，这篇文章主要介绍贪心算法——找零钱，现在分享给大家，希望可以做个参考。

人民币有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
我们要找的就是张数最少的那种方方案。
给出代码：
转换成单位为：分；便于计算。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}