揹包 - 如何識別使用哪些重量？

我有一個代碼，它給出了我可以通過用最佳權重集填充揹包而獲得的最大值。揹包 - 如何識別使用哪些重量？

int arr[5] = {0, 0, 0, 0, 0}; 
int Weight[5] = {2, 5, 8, 7, 9}; 
int Value[5] = {4, 5, 7, 9, 8}; 
const int n = 5; 
const int maxCapacity = 20; 

int maximum(int a, int b) 
{ 
    return a > b ? a : b; 
} 

int knapsack(int capacity, int i) 
{ 
    if (i > n-1) return 0; 

    if (capacity < Weight[i]) 
    { 
     return knapsack(capacity, i+1); 
    } 
    else 
    { 
     return maximum (knapsack(capacity, i+1), 
         knapsack(capacity - Weight[i], i+1) + Value[i]); 
    } 
} 

int main (void) 
{ 
    cout<<knapsack(maxCapacity,0)<<endl; 
    return 0; 
}

我需要通過打印來擴展此解決方案，所有權重都用於找到最佳解決方案。爲此，我計劃使用初始化爲0的數組arr。每當使用一個權重時，我將arr中相應的位置標記爲1，否則它將保持爲0.

我想到的第一件事是更改最大值）功能如下所示

int maximum(int a, int b, int i) 
{ 
    if (a > b) 
    { 
     if (arr[i] == 1) arr[i] = 0; 
     return a; 
    } 
    else 
    { 
     if (arr[i] == 0) arr[i] = 1; 
     return b; 
    } 
}

但即使這種解決方案失敗的權重和值的某種組合。關於如何前進的任何建議？

來源

2012-09-27 bibbsey

您可以發佈一個失敗的示例組合，它通常非常具有說明性。 –

PS：如果你使用C++ 11，你應該考慮用'std :: array '替換這些數組，這樣更方便。 – akappa

@BartekBanachewicz：示例數組已經在代碼中硬編碼。在這種情況下，將使用權重-2,7,9，並且arr [5]的最終值是{1,1,0,1,1}，因爲它應該是{1,0,0,1,1} – bibbsey

的問題是，你不知道它的兩個選項一個是通過這個命令

return maximum (knapsack(capacity, i+1), 
       knapsack(capacity - Weight[i], i+1) + Value[i]);

我想你可以使用兩個變量來存儲值，如果權重選擇（的價值選擇該變量更大），您可以將其添加到數組中。希望解決您的問題。

來源

2012-10-29 07:11:42

揹包 - 如何識別使用哪些重量？

回答

相關問題