打印揹包解決方案的值

-1

我對揹包問題有以下解決方案：（wt []是權重數組，val []是值數組，n是數組大小，index是當前項目，我們是嘗試（用於遞歸）和改編是表示天氣或不項目i是包含在溶液的陣列。打印揹包解決方案的值

int knapSack(int W, int wt[], int val[], int n, int index, int arr[]) 
{ 
    if (n == index || W == 0) 
     return 0; 
    if (wt[index] > W) 
     return knapSack(W, wt, val, n, index+1); 

    int with=val[index]+knapSack(W-wt[index], wt, val, n, index+1); 
    int without=knapSack(W, wt, val, n, index+1); 

    if(with>without){ 
     arr[index]=1; 
     return with; 
    } 
    else{ 
     arr[index]=0; 
     return without; 
    } 

}

我想打印，在該遞歸的解決方案，被選擇，通過設置的項目在一個數組（res）中採取的索引爲1
據我所知，如果with>without，這意味着我選擇了當前項目或項目#index。那麼爲什麼這不會返回正確的值？
我使用遞歸算法的原因，我知道使用memoization版本可以在這裏更容易。實施例：
重量：5個6 7 10 11
值：2 4 5 6 9
W = 25
將返回5對那些在陣列水庫當項目2,3,5的解決方案爲18時（從索引1開始）。

來源

2016-12-28 Yinon Eliraz

爲什麼添加賞金？我想投票支持，因爲沒有[MCVE]（http://stackoverflow.com/help/mcve）。 – melpomene

添加了一個示例。 –

代碼的其餘部分在哪裏？ – melpomene

前提1：在你的代碼，遞歸調用knapSack沒有經過arr，這應該引起編譯錯誤，我認爲它只是一個複製/粘貼錯誤。

前提2：你提出的數據，所產生的arr值是不是所有1如你所指出的，但是01011，這仍然是不正確。

考慮你的函數的執行過程中的假設情況，with比without更大：在with計算期間arr充滿了正確的價值觀;但是然後開始計算without，這將會覆蓋arr值。

由於with大於without，返回的arr將是錯誤的，這是問題的原因。

一個簡單的解決方法是使由with計算所以它是不會被without計算覆蓋返回arr的副本，例如：

int with=val[index]+knapSack(W-wt[index], wt, val, n, index+1, arr); 

// copy the "with" arr 
int arrWith[n]; 
copyArr(arr, arrWith, n); 

int without=knapSack(W, wt, val, n, index+1, arr); 

if(with>without){ 
    // restore the "with" arr 
    copyArr(arrWith, arr, n); 

    arr[index]=1; 
    return with; 
} 
else{ 
    arr[index]=0; 
    return without; 
}

copyArr很簡單：

void copyArr(int arr[], int arrDest[], int n) { 
    int i; 
    for(i = 0; i < n; i++) { 
     arrDest[i] = arr[i]; 
    } 
}

使用此修復程序產生的值arr正確01101。

來源

2017-01-01 19:22:30

打印揹包解決方案的值

回答

相關問題