0

编写一个使用递归回溯的方法 makeChange，使用便士（1 美分）、镍（5 美分）、10 美分（10 美分）和 25 美分（25 美分）找出给定金额找零的所有方法。

例如，当找 37 美分时，您可以使用：

  • 1 季度
  • 1 毛钱和 2 便士
  • 3 角钱和 7 便士
  • 或其他组合。

您的方法应该接受一个参数：要更改的美分数量。

您的方法的输出应该是每种类型硬币的所有组合的序列，加起来等于该数量，每行一个。

例如，如果客户端代码包含以下调用：

System.out.println(" P  N  D  Q");
System.out.println("------------");
makeChange(28);

生成的整体输出应如下所示：

 P  N  D  Q
------------ [3, 0, 0, 1] [3, 1, 2, 0] [3, 3, 1, 0] [3, 5, 0, 0] [8, 0, 2, 0] [8, 2, 1, 0] [8, 4, 0, 0] [13, 1, 1, 0] [13, 3, 0, 0] [18, 0, 1, 0] [18, 2, 0, 0] [23, 1, 0, 0] [28, 0, 0, 0]

解决这个问题的一个关键见解是查看硬币的每种面额（便士、镍等）并尝试该硬币的所有可能数字（1 便士、2 便士、...、28 便士）来看看是什么可以从该选择开始进行组合。例如，在上面的输出中，首先显示所有以 3 便士开头的组合，然后显示所有以 8 便士开头的组合，依此类推。

由于回溯涉及探索一组选择，因此您应该在代码中以某种方式表示硬币面额。我们建议保留所有硬币面额值的列表以供处理。当您处理各种硬币值时，您可以修改此列表的内容。下面的模板是一个起点（您可以将其复制/粘贴到代码文本框中以开始使用）：

public static void makeChange(int amount) {
    List coinValues = new LinkedList();
    coinValues.add(1);    // penny
    coinValues.add(5);    // nickel
    coinValues.add(10);   // dime
    coinValues.add(25);   // quarter

// ... your code goes here ...

您可以假设传递给您的方法的更改量是非负的，但它可能超过 100。

所以这是我的代码：

public static void makeChange(int amount){
    int[] acc = new int[4];
    makeChange(amount, acc);
}

private static void makeChange(int amount, int[] acc){
    if(amount == 0){
        System.out.print("[" + acc[0]);
        for(int i = 1; i < 4; i++){
            System.out.print(", " + acc[i]);
        }
        System.out.print("]");
        System.out.println();
    }
    if(amount > 0){
        acc[0]++;
        makeChange(amount - 1, acc);
        acc[0]--;
        acc[1]++;
        makeChange(amount - 5, acc);
        acc[1]--;
        acc[2]++;
        makeChange(amount - 10, acc);
        acc[2]--;
        acc[3]++;
        makeChange(amount - 25, acc);
        acc[3]--;
    }
}

及其调用 makeChange(28) 的输出：

[28, 0, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 0, 1, 0]
[13, 1, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 0, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 0, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 0, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]

...（有数百行输出）

有人能告诉我为什么会产生重复的输出吗？非常感谢！

4

1 回答 1

0

简而言之，您通过不同的途径获得了相同的解决方案。现在编写代码的方式顺序很重要。

简单的案例来理解：

假设我们想要改变 6。现在1 + 5 = 5 + 1。

所以你将有 [1,1,0,0] 两次在解决方案中。

方式一：你先减1，再减5，减到0。

方式2：你先减5，再减1，减到0。

要获得唯一的解决方案，请使用HashSet或TreeSet存储解决方案ArrayList（但不是数组），而不是在基本条件下打印。最后一起打印所有解决方案。

另一种方法是您可以添加第三个参数，指示您最后使用的硬币。您将使用面额>=为最后使用的硬币的硬币。这确保了解决方案是独一无二的。

于 2017-07-05T22:01:51.790 回答