在揹包裏找到物品

我想在C＃中遞歸地解決揹包問題。這是我的代碼：在揹包裏找到物品

public int f(int n, int remain) 
{ 
    if (n < 0) return 0; 
    if (w[n] > remain) 
    { 
     // Thread.VolatileWrite(ref check[n], 0); 
     check[n] = 0; 
     return f(n - 1, remain); 
    } 
    else 
    { 
     int a = f(n - 1, remain); 
     int b = p[n] + f(n - 1, remain - w[n]); 
     if (a >= b) 
     { 
      // Thread.VolatileWrite(ref check[n], 0); 
      check[n] = 0; 
      return a; 
     } 
     else 
     { 
      // Thread.VolatileWrite(ref check[n], 1); 
      check[n] = 1; 
      return b; 
     } 
    } 
}

w是持有權重和p是包含價格的數組的數組。 n是物品的數量，remain是最大重量。我的問題是check數組。我已經使用這個數組來存儲將會在包中的物品，但它並不總是有效，有時候解決方案是正確的，有時候不是。我已經嘗試了一切，但無法弄清楚。我該如何解決這個問題？

來源

2015-04-19 ali najimi

請包括特定輸入的量，實際結果與期望的結果不同。 f'的返回值是多少？找到的解決方案的重量？ – Codor

返回值應該是正確的。注意修改遞歸內的校驗數組。嘗試每次複製數組，並將其返回到一個元組中。這不是最優的，但你可以更好地看到它 – rpax

@codor w是一個由wights組成的數組，p是一個由價格組成的數組... n是項目的數量並且是最大的懷疑 –

檢查數組的使用是錯誤的，因爲它表示最後一次賦值，並且它不一定是所選的那個。

下面是一個反例解釋爲什麼它不起作用。

假設：

weights = [1,2] 
values = [2,1] 
w = 2

現在，讓我們檢查會發生什麼：

f(1,2): 
    f(0,2): 
     f(-1,2) = 0 
     a = 0 
     f(-1,1) = 0 
     b = 2 + 0 = 2 
     b>a -> check[0] = 1 
    return f(0,2) = 2 
    a = 2 
    f(0,0): 
     w[0] > 0: check[0] = 0 
     return f(-1,0) = 0 
    return f(0,0) = 0 
    b = 1 + 0 = 1 
    a > b: check[1] = 0 
return f(1,2) = 2

因此，解決這個問題的最佳解決方案是2（艇員選拔的第二個元素），但您的解決方案選擇了沒有元素（check = [0,0]）

發生這種情況是因爲更改check是全局變量，而不是調用環境的本地變量，特別是 - d等級不取決於你在更高等級上的選擇。

來處理它，您可以：

讓你列表不是全球性的，每次遞歸調用將有一個列表的自己的實例。「父母」電話將不僅選擇要採用的值，而且根據該選擇 - 父母也將選擇其將使用的列表，並且在將其「父親」選擇附加到它之前，將其轉發給其父母。
切換到DP solution，或模仿DP溶液，然後使用所創建找出該選擇哪些元素如我在此線程中描述的表：How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?

來源

2015-04-19 21:30:16 amit

很好的答案。我喜歡那些不是代碼_答案的家庭作業問題的答案，教導如何思考和解決問題。感謝您使本網站更好。 – rpax

@amit對不起，要求代碼......但多一點提示不會傷害第一個解決方案你建議 –

修復它....謝謝你的提示 –

在揹包裏找到物品

回答

相關問題