编辑代码

import java.util.*;

public class Exp4_CoinChange {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请给出组成的面额集合(用空格分隔):");
        String[] inputs = scanner.nextLine().split(" ");
        int[] denominations = Arrays.stream(inputs).mapToInt(Integer::parseInt).toArray();
        
        System.out.print("请给出要找的零钱数: ");
        int changeAmount = scanner.nextInt();
        
        // Timing dynamic programming solution
        long startTimeDP = System.nanoTime();
        int resultDP = calculateMinCoinsDP(denominations, changeAmount);
        long endTimeDP = System.nanoTime();
        
        // Timing greedy solution
        List<Integer> coinsUsed = new ArrayList<>();
        long startTimeGreedy = System.nanoTime();
        int resultGreedy = calculateMinCoinsGreedy(denominations, changeAmount, coinsUsed);
        long endTimeGreedy = System.nanoTime();

        // Output results
        System.out.println("动态规划:最少钞票数为: " + resultDP + ", 用时(纳秒): " + (endTimeDP - startTimeDP));
        System.out.println("贪心算法:最少钞票数为: " + resultGreedy + ", 用时(纳秒): " + (endTimeGreedy - startTimeGreedy));
        System.out.println("贪心算法是否为最优解? " + (resultDP == resultGreedy));
        System.out.println("贪心算法的解为: " + coinsUsed);
    }

    // Dynamic programming solution to find minimum number of coins
    public static int calculateMinCoinsDP(int[] denominations, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int coin : denominations) {
            for (int j = coin; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }

    // Greedy solution to find minimum number of coins
    public static int calculateMinCoinsGreedy(int[] denominations, int amount, List<Integer> coinsUsed) {
        Arrays.sort(denominations);
        int count = 0;
        for (int i = denominations.length - 1; i >= 0; i--) {
            while (amount >= denominations[i]) {
                amount -= denominations[i];
                coinsUsed.add(denominations[i]);
                count++;
            }
        }

        if (amount != 0) { // Check if change could not be made exactly.
            coinsUsed.clear();
            return -1; // Return -1 indicating no solution was found.
        }
        return count;
    }
}