這2個揹包算法是一樣的嗎？ （他們總是輸出相同的東西）

Question

在我的代碼中，假設C是容量，N是項目的數量，w [j]是項目j的權重，v [j]是項目j的值，它是否和0-1揹包算法一樣？我一直在一些數據集上嘗試我的代碼，而且似乎是這樣。我不知道這樣做的原因是因爲我們被教導0-1揹包算法是2維的，而這是一維：

for (int j = 0; j < N; j++) { 
    if (C-w[j] < 0) continue; 
    for (int i = C-w[j]; i >= 0; --i) { //loop backwards to prevent double counting 
     dp[i + w[j]] = max(dp[i + w[j]], dp[i] + v[j]); //looping fwd is for the unbounded problem 
    } 
} 
printf("max value without double counting (loop backwards) %d\n", dp[C]); 

這是我實現0-1揹包算法：（具有相同變量）

for (int i = 0; i < N; i++) { 
    for (int j = 0; j <= C; j++) { 
     if (j - w[i] < 0) dp2[i][j] = i==0?0:dp2[i-1][j]; 
     else dp2[i][j] = max(i==0?0:dp2[i-1][j], dp2[i-1][j-w[i]] + v[i]); 
    } 
} 
printf("0-1 knapsack: %d\n", dp2[N-1][C]); 

Answer 1

是的，您的算法會得到相同的結果。此增強經典0-1揹包是合理流行：Wikipedia解釋它如下：

此外，如果我們只使用1維陣列米[W]以存儲當前的最優值，並越過該數組i + 1次，每次從m [W]改寫爲m [1]，只有O（W）空間得到相同的結果。

請注意，他們特別提到你的後向循環。