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