回溯最小选项以通过递归使用 1、5 和 7 对数字求和 - JAVA

Question

我想创建一个递归函数，return 是使用数字 1、5 和 7（固定预定数字）创建特定数字的最小选项。重要的是，这仅通过完全没有循环的递归完成。

例如：

如果 n = 10 则它通过 5 + 5 给出给方案，这是 2 个数字，所以这是最小值，这就是我们将得到的（而不是 7 + 1 + 1 + 1 或 5 + 1 + 1 + 1 + 1 + 1 即 4 或 6 个更长的选项）。

如果 n = 6 那么我们得到的结果是 2（因为它是 1 + 5 的总和）。

如果 n = 5（或 7 或 1），则结果为 1（因为它仅由数字给出）。

class TEST { 

static int countMin( int S[], int m, int n ,int min) 
    { 
        if (n == 0) 
            return 1;      
        if (n < 0) 
            return 0; 
        if (m <=0 && n >= 1) 
            return 0; 
        return Math.min(min,countMin( S, m - 1, n ,min-1) + countMin( S, m, n-S[m-1],min-1 )); 
    } 

public  static int f(int n)  {
      int arr[] = {1, 5, 7};  
      return countMin(arr, arr.length, n,n);
} 

    public static void main(String[] args) 
    { 
        int n = 10;
        System.out.println("The number "+n+ " - " + f(n) + " minimum options to create");
        int n2 = 7;
        System.out.println("The number "+n2+ " - " + f(n2) + " minimum options to create"); 
        int n3 = 6;
        System.out.println("The number "+n3+ " - " + f(n3) + " minimum options to create");

    } 

}

我得到 n = 10 和 n = 5 的正确结果，但不是 n = 6 应该 return 2.

*我用过这个link：https://www.geeksforgeeks.org/coin-change-dp-7/

Answer 1

想象一棵树，其中每个节点都有一个值并且有 3 个子节点，其值分别递减 7、5 和 1

因此节点总数为 15 的子节点的值为 8、10、14

我们可以从第一个节点开始，计算每个级别，当我们找到一个值为 0 的子节点时停止。如果一个子节点的值小于 0，我们也会停止查找。

例如 10:

                10
            /    |    \
        3        5       9
      / | \    / | \   / | \
    -4 -2 2   -2 0 4   2 4 1

我们在深度 2 处找到零

private static int calculate(int total, int depth) {
    if (total == 0)
        return depth;
    else {
        int i = total - 7  >= 0 ? calculate(total - 7, depth+1) : Integer.MAX_VALUE;
        int j = total - 5  >= 0 ? calculate(total - 5, depth+1) : Integer.MAX_VALUE;
        int k = total - 1  >= 0 ? calculate(total - 1, depth+1) : Integer.MAX_VALUE;
        return Collections.min(Arrays.asList(i, j, k));
    }
}

这个

int n = 10;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");
n = 7;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");
n = 6;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");
n = 18;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");

输出这个

The number 10 - 2 minimum options to create
The number 7 - 1 minimum options to create
The number 6 - 2 minimum options to create
The number 18 - 4 minimum options to create

编辑： 同样采用时髦的 lambda 风格：

private static int calculate(int total, int depth) {
    return total == 0 ? 
        depth : 
        Stream.of(7, 5, 1)
              .map(i -> total - i  >= 0 ? calculate(total - i, depth+1) : Integer.MAX_VALUE)
              .min(Integer::compare)
              .get();
}

回溯最小选项以通过递归使用 1、5 和 7 对数字求和 - JAVA

Backtracking Min options to sum a number using 1, 5 and 7 via recursion - JAVA

java

recursion

backtracking

recursive-backtracking