import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class ChangeMakingProblem {
public static Map<Integer, Integer> minCoins(int[] coins, int K) {
Arrays.sort(coins);
Map<Integer, Integer> result = new HashMap<>();
for (int i = coins.length - 1; i >= 0; i--) {
int count = K / coins[i];
if (count > 0) {
result.put(coins[i], count);
K = K - count * coins[i];
}
}
return result;
}
public static void main(String[] args) {
int[] coins = {1, 2, 5, 10, 20, 50, 100, 500, 1000};
int K = 93;
Map<Integer, Integer> change = minCoins(coins, K);
System.out.println("找零方案为:");
for (Map.Entry<Integer, Integer> entry : change.entrySet()) {
System.out.println(entry.getKey() + " 元硬币 " + entry.getValue() + " 个");
}
}
}