编辑代码

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() + " 个");
        }
    }
}