是否可以递归检查 java 数组中所有组合的最大值

Question

我得到了岩石的价格和数组中每块岩石的价值。我必须递归地（仅使用列出的 4 个变量）检查所有可能的岩石组合，以找到低于或等于岩石组合允许的最大重量的最高价格。

例如：

price = {50, 10, 30, 40}
weight = {20, 5, 10, 30}
maxWeight = 25;
index = 4;

在这种情况下，可以找到的最高价格是50，因为20的权重低于25，价值为50。这高于同样低于25的5 + 10的权重，但他们的值加起来只有 40，小于 50。

示例 2：

price = {50, 10, 30, 40}
weight = {20, 5, 10, 30}
maxWeight = 30;
index = 4;

在这种情况下，最高价格是 80。这是因为权重 20 + 10 加起来最大权重 30，它们的值加起来是 80。第二高的值是权重 20 + 5，它加起来小于最大重量，它们的值将是 60。第三高的值是 40，可以使用 5 + 10 重量或 30 重量找到。

调用这些值的方法如下所示：

public static int maxValue(weight[], price[], maxWeight, index) {

}

是否可以递归地使用此方法找到最大重量下的最佳岩石组合并提供最高价格？

如有不明之处欢迎评论

Answer 1

您的问题是众所周知的 Knapsack problem 并且没有任何已知的有效算法可以解决它。

可能您正在寻找递归解决方案：

static int naive_knapSack(int[] v, int[] w, int size, int index) {

    // no more items
    if (index >= v.length)
        return 0;

    // we cannot use the current item
    if (size < w[index])
        return naive_knapSack(v, w, size, index + 1);

    // the maximum value will be taking in account the current index OR not
    return Math.max(
            naive_knapSack(v, w, size, index + 1), // ignoring this item
            v[index] + naive_knapSack(v, w, size - w[index], index + 1) // using this item
    );

}

但是，如果背包大小适合内存（例如小于 4G），则存在具有 O(n^2) 成本的动态编程解决方案：

static int knapSack(int[] v, int[] w, int size) {
    int[][] m = new int[w.length + 1][size + 1];
    for (int i = 1; i <= w.length; i++)
        for (int j = 0; j <= size; j++)
            m[i][j] = w[i - 1] > j ? m[i - 1][j] : Math.max(m[i - 1][j], m[i - 1][j - w[i - 1]] + v[i - 1]);
    return m[w.length][size];
}

基本相同，只是记忆了递归的每个选项（只计算一次）。如果你记住之前的递归函数，你会得到相同的结果。

我们可以比较两个输出

int[] v = new int[]{50, 10, 30, 40};
int[] w = new int[]{20, 5, 10, 30};

// specific cases
System.out.println(knapSack(v, w, 25));
System.out.println(knapSack(v, w, 30));

System.out.println(naive_knapSack(v, w, 25, 0));
System.out.println(naive_knapSack(v, w, 30, 0));

结果相同（注意第一个解不是50是60）

但是，当动态规划算法是多项式时，递归算法的效率是指数级的，仅使用34项进行比较

// efficiency
int ITEMS = 34;
int[] V = IntStream.range(0, ITEMS).map(i -> ThreadLocalRandom.current().nextInt(1, 50)).toArray();
int[] W = IntStream.range(0, ITEMS).map(i -> ThreadLocalRandom.current().nextInt(50, 150)).toArray();
int itemsWeight = Arrays.stream(W).sum();
int capacity = ThreadLocalRandom.current().nextInt(itemsWeight >> 2, itemsWeight >> 1);

long t0 = System.nanoTime();
int r1 = naive_knapSack(V, W, capacity, 0);
long t1 = System.nanoTime();
int r2 = knapSack(V, W, capacity);
long t2 = System.nanoTime();

System.out.printf("r1 = %d, t1 = %f%nr2 = %d, t2 = %f%n", r1, (t1 - t0) * 1e-9, r2, (t2 - t1) * 1e-9);

我们得到

r1 = 481, t1 = 11,11 seconds
r2 = 481, t2 = 0,004 seconds

是否可以递归检查 java 数组中所有组合的最大值

Is it possible to recursively check the max value of all combinations in a java array

java

arrays

methods

recursion

loops