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

Question

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

例如：

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

在这种情况下，可以找到的最高价格是50，因为20的重量低于25，值是50。这比5-10的权重高，5-10的权重也低于25，但它们的值加起来只有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

你的问题是众所周知的背包问题，没有任何已知的有效算法来解决它。

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

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）

60
80
60
80

但是，当动态规划算法是多项式时，递归算法的效率是指数的，仅使用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