贪心算法解决找零钱问题（Java实现）

人民币的面额有 100 元、50 元、10 元、5 元、2 元、1 元等。在找零钱时，可以有多种方案。例如，零钱 146 元的找零方案如下：

100+20+20+5+1
100+20+10+10+5+1
100+20+10+10+2+2+2
100+10+10+10+10+1+1+1+1+1+1
…

输出找零钱的一个可行方案。

购物找零钱时，为使找回的零钱的硬币数最少，不要求找零钱的所有方案，而是从最大面额的币种开始，按递减的顺序考虑各面额，先尽量用大面额，当不足大面额时，才去考虑下一个较小面额，这就是贪心算法。

利用贪心算法，选择的是第 1 种方案，首先选择一张最大面额的人民币，即 100 元面额的，然后在剩下的 46 元中选择面额最大的，即 20 元。以此类推，每次的选择都是局部最优解。

算法实现如下：

import java.util.Scanner;

public class ExchangeMoney {
    float r[];
    static int N = 50;
    ExchangeMoney() {
        r = new float[N];
    }
    public static void main(String args[]) {
        float rmb[] = {100, 50, 20, 10, 5, 2, 1, 0.5f, 0.2f, 0.1f};
        int n = rmb.length, k, i;
        float change, r[] = new float[N];
        System.out.print("请输入要找的零钱数:");
        Scanner sc = new Scanner(System.in);
        change = sc.nextFloat();
        for (i = 0; i < n; i++) {
            if (change >= rmb[i]) {
                break;
            }
        }
        ExchangeMoney EM = new ExchangeMoney();
        k = EM.GetExchangeMoney(change, rmb, 0, n - i, r, 0);
        if (k <= 0)
            System.out.printf("找不开!\n");
        else {
            System.out.printf("找零钱的方案:%.2f=", change);
            if (r[0] > 1.0)
                System.out.printf("%.0f", r[0]);
            else
                System.out.printf("%.2f", r[0]);
            for (i = 1; i < k; i++) {
                if (r[i] >= 1.0)
                    System.out.printf("+%.0f", r[i]);
                else
                    System.out.printf("+%.2f", r[i]);
            }
            System.out.print("\n");
        }
    }
    int GetExchangeMoney(float n, float a[], int i, int c, float r[], int j) {
        int m;
        if (n == 0.0) // 能分解，分解完成
            return 0;
        if (c == 0) // 不能分解
            return -1;
        if (n < a[i])
            return GetExchangeMoney(n, a, i + 1, c - 1, r, j); // 继续寻找合适的面额
        else {
            r[j] = a[i]; // 将零钱保存到 r 中
            m = GetExchangeMoney(n - a[i], a, i, c, r, j + 1); // 继续分解剩下的零钱
            if (m >= 0)
                return m + 1; // 返回找零的零钱张数
            return -1;
        }
    }
}

程序运行结果如下:

请输入要找的零钱数：168.5
找零钱的方案：168.50=100+50+10+5+2+1+0.50

存放人民币的各种面额大小。代码如下：

float rmb[]={100, 50, 20, 10, 5, 2, 1, 0.5f, 0.2f, 0.1f};

找到第 1 个小于 change 的人民币面额。代码如下：

for (i = 0; i < n; i++) {
    if (change >= rmb[i])
        break;
}

调用 GetExchangeMoney() 函数并返回找回零钱的张数。代码如下：

ExchangeMoney EM=new ExchangeMoney();
k=EM.GetExchageMoney(change,rmb,0,n-i,r,0);

若返回小于或等于 0 的数，则表示找不开零钱；否则，输出找零钱的方案。代码如下：

if (k <= 0)
    System.out.printf("找不开！\n");
else {
    System.out.printf("找零钱的方案:%.2f=", change);
    if (r[0] >= 1.0)
        System.out.printf("%.0f", r[0]);
    else
        System.out.printf("%.2f", r[0]);
    for (i = 1; i < k; i++) {
        if (r[i] >= 1.0)
            System.out.printf("+%.0f", r[i]);
        else
            System.out.printf("+%.2f", r[i]);
    }
    System.out.println();
}

若找零钱成功，则返回 0。代码如下：

if(n==0.0)       //能分解，分解完成
    return 0;

若没有找到合适的找零钱方案，则返回 -1。代码如下：

if(c==0)         //不能分解
    return -1;

继续寻找较小的面额。代码如下：

if(n<a[i])       //继续寻找合适的面额
    return GetExchangeMoney(n,a,i+1,c-1,r,j);  //继续寻找合适的面额

将零钱的面额存放到数组 r 中，并继续分解剩下的零钱。代码如下：

r[j]=a[i];      //将零钱保存到 r 中
m=GetExchangeMoney(n-a[i],a,i,c,r,j+1);   //继续分解剩下的零钱
if(m>=0)        //返回找零的零钱张数
    return m+1;
return -1;

贪心算法解决找零钱问题（Java实现）

相关文章