是否可以递归地检查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