钱币找零问题在我们的日常生活中非常普遍。
假设纸币金额为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元
