钱币找零问题java实现

钱币找零问题在我们的日常生活中非常普遍。

假设纸币金额为1元、5元、10元、20元、50元、100元，123元应该尽可能兑换少的纸币。

很显然，每一步尽可能用面值大的纸币即可，123元应该兑换1张100、1张20元和3张1元的。

算法思路很简单，只需要尽可能从最大的面值往下一直减即可。

具体java实现如下所示：

package com.test.smallchangealgorithm;

public class SplitChangeMoneyTest {

    static void splitChange(int money) {
        if (money <= 0) {
            System.out.println("money is invalid, money=" + money);
            return;
        }

        int[] prices = {100, 50, 20, 10, 5, 1};
        int[] notes = new int[prices.length];
        int change = money;
        while (change > 0) {
            for (int i = 0; i < prices.length; i++) {
                int count = 0;
                while (change - prices[i] >= 0) {
                    change = change - prices[i];
                    count++;
                }
                notes[i] = count;
            }
        }

        System.out.println("总额=" + money + ", 找零：");
        for (int num = 0; num < prices.length; num++) {
            System.out.print(notes[num] + "张" + prices[num] + "元  \n");
        }
    }

    public static void main(String[] args) {
        int money = 1680;
        SplitChangeMoneyTest.splitChange(money);
    }

}

运行结果如下所示：

总额=1680, 找零：
16张100元  
1张50元  
1张20元  
1张10元  
0张5元  
0张1元