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();
long startTimeDP = System.nanoTime();
int resultDP = calculateMinCoinsDP(denominations, changeAmount);
long endTimeDP = System.nanoTime();
List<Integer> coinsUsed = new ArrayList<>();
long startTimeGreedy = System.nanoTime();
int resultGreedy = calculateMinCoinsGreedy(denominations, changeAmount, coinsUsed);
long endTimeGreedy = System.nanoTime();
System.out.println("动态规划:最少钞票数为: " + resultDP + ", 用时(纳秒): " + (endTimeDP - startTimeDP));
System.out.println("贪心算法:最少钞票数为: " + resultGreedy + ", 用时(纳秒): " + (endTimeGreedy - startTimeGreedy));
System.out.println("贪心算法是否为最优解? " + (resultDP == resultGreedy));
System.out.println("贪心算法的解为: " + coinsUsed);
}
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];
}
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) {
coinsUsed.clear();
return -1;
}
return count;
}
}