0/1揹包澄清和優化

我正在讀關於0-1揹包問題維基百科。我只想澄清一些事情。我有兩個問題： http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem 0/1揹包澄清和優化

我遇到了這個僞代碼：

// Input: 
// Values (stored in array v) 
// Weights (stored in array w) 
// Number of distinct items (n) 
// Knapsack capacity (W) 
for w from 0 to W do 
    m[0, w] := 0 
end for 
for i from 1 to n do 
    for j from 0 to W do 
    if j >= w[i] then 
     m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i]) 
    else 
     m[i, j] := m[i-1, j] 
    end if 
    end for 
end for

專門針對這部分：

if j >= w[i] then 
     m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

1）糾正我，如果我錯了，但不應該」它是：

 m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i], m[i,j-w[i]] + v[i])

？

或者如果沒有，可以有人解釋我爲什麼沒有必要？

...

2）我也有一個問題，如果說我想優化這個有點。通過項目的所有權重（即，存儲在數組w中的值的GCD）的GCD遞增「j從0到W」的循環是否明智？（當我即將實現它時，我現在正在考慮採用代碼方式）。

來源

2013-05-17 skyjlv

1）當您添加m[i,j-w[i]] + v[i]時，您允許多次選擇相同的項目i，因此它不再是0/1揹包 - 它成爲一個揹包問題，每個項目的數量不受限制。

2）是的，但是這通常GCD歸結爲1真實情況，因此不值得費心一般情況下，除非你事先知道你的數據會從中受益。（在這種情況下，你預期的要由GCD您的所有數據劃分，並保持原來的算法在時間遞增1，然後乘以GCD的最終結果。這將節省你的內存爲好，但你的揹包容量也必須能被GCD整除）

來源

2013-05-17 22:43:23

0/1揹包澄清和優化

回答

相關問題