我得到了巖石的價格和陣列中每塊巖石的價值。我必須遞回地（僅使用列出的 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) {
}
是否可以遞回地使用這種方法來找到最大重量下的最佳巖石組合并提供最高價格？
如果您有任何困惑，請發表評論。
uj5u.com熱心網友回復：
你的問題是眾所周知的背包問題，沒有任何已知的有效演算法來解決它。
可能您正在尋找遞回解決方案：
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
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/324823.html
上一篇：從位元組陣列中獲取正確格式的字串
下一篇：如何從此陣列中獲取所需的資料