时间戳

首页 > 解决方案 > 硬币变化递归所有解决方案到不同的解决方案

java - 硬币变化递归所有解决方案到不同的解决方案

问题描述

我是递归和回溯的新手。我知道在继续进行动态编程之前，我需要完全熟悉这些概念。我在下面编写了一个程序，可以帮助我找到给定数量 n 和无限数量硬币的所有可能组合。但是，我希望我的程序给我不同的解决方案。我很难弄清楚如何做到这一点。

我在这里找到了一个资源：Coin Change递归地使用自上而下的方法，然后使用以下公式对其进行修改以给出不同的组合：count (s, n, total) = count (s, n, total-s[n] ) + 计数(s, n-1, 总数)

这表示我使用该值进行递归，然后递归排除该值并将硬币减 1。

我似乎无法理解这是如何工作的。我也可以肯定地说，即使在面试中当场想出这样的技术也是相当困难的。似乎有人在某个时候不得不在这样一个问题上花费大量时间来设计这样一种技术。

无论如何，任何关于如何将我的程序转换为打印不同的解决方案以及它如何工作的帮助将不胜感激。

public class Recursive {

    static int[] combo = new int[100];
    public static void main(String argv[]) {
        int n = 8;
        int[] amounts = {1, 5, 10};
        ways(n, amounts, combo, 0, 0, 0);
    }

    public static void  ways(int n, int[] amounts, int[] combo, int count, int sum, int index) {
        if(sum == n) {
            printArray(combo, index);
        }

        if(sum > n) {
            return;
        }


        for(int i=0;i<amounts.length;i++) {
            sum = sum + amounts[i];
            combo[index] = amounts[i];
            ways(n, amounts, combo, 0, sum, index + 1);
            sum = sum - amounts[i];
        }
    }

    public static void printArray(int[] combo, int index) {
        for(int i=0;i < index; i++) {
            System.out.print(combo[i] + " ");
        }
        System.out.println();
    }
}

使用纯递归穷举技术（下面的代码），数量 {1, 2, 5} 和 N = 10 的非不同有效组合的实际数量为 128。

我的问题是可以通过记忆/动态编程改进详尽的搜索。如果是这样，我该如何修改下面的算法以结合这些技术。

标签： javaalgorithmrecursioncoin-change

解决方案

简单的修改可以避免重复。

使用排序amounts数组。
循环的起始值应排除amounts.
我使用count了参数（似乎未使用）

 for(int i=count;i<amounts.length;i++) {
            sum = sum + amounts[i];
            combo[index] = amounts[i];
            ways(n, amounts, combo, i, sum, index + 1);
            sum = sum - amounts[i];
        }

推荐阅读