动态规划硬币找零问题 - 打印使用的硬币 Java

Question

所以我弄清楚了硬币找零的问题，我了解它是如何工作的，但我似乎无法弄清楚如何打印出每枚硬币使用了多少。例如，数量为 12，硬币数组为 1、5 和 10，我希望输出如下所示：

Penny.    Nickel.    Dime
12.       0.         0
7.        1.         0
2.        2.         0
2.        0.         1

我将如何打印出来？我目前的代码是：

public class codingChallenge {
public static void main(String[] args) {
    int [] coinsArray = {1, 5, 10};
    System.out.println(change(12, coinsArray));
}

public static int change(int amount, int[] coins){
    int[] combinations = new int[amount + 1];

    combinations[0] = 1;

    for(int coin : coins){
        for(int i = 1; i < combinations.length; i++){
            if(i >= coin){
                combinations[i] += combinations[i - coin];
                System.out.println(coin);
            }
        }
        System.out.println();
    }

    return combinations[amount];
}

}

非常感谢任何帮助。谢谢！

Answer 1

假设您有 collection 个类似于以下的硬币排列

Collection<List<Integer>> permutations = List.of(
        List.of(12, 0, 0),
        List.of(7, 1, 0),
        List.of(2, 2, 0),
        List.of(2, 0, 1)
);

然后您可以通过调用 printPermutations:

将其转换为 table

private static final String HEADER = "Penny     Nickel     Dime";
private static final String COIN_FORMAT = "%-10d";

private static void printPermutations(Collection<List<Integer>> permutations) {
    System.out.println(HEADER);
    String output = permutations.stream()
            .map(CoinChange::format)
            .collect(Collectors.joining("\n"));

    System.out.println(output);
}

private static String format(List<Integer> permutation) {
    return permutation.stream()
            .map(i -> String.format(COIN_FORMAT, i))
            .collect(Collectors.joining());
}

这显然假设排列包括您 header 中相同硬币的值。您可以引入 Coin class 或枚举并使用 Map<Coin, Integer> 而不是 List<Integer> 以使解决方案更灵活一些，但概念将保持不变。

动态规划硬币找零问题 - 打印使用的硬币 Java

Dynamic Programming Coin Change Problem - Print Coins Used Java

java

dynamic-programming

coin-change