揹包分支定界

Question

我具有以下數據：

item weight value value/weight 
1  5  40  8 
2  2  10  5 
3  6  30  5 
4  1  12  12 
5  2  18  9 

容量是10 如何使用計算上限節點0繼續？ 我計算上限爲節點0如下：

ub = v + [W-w] * [v/w] 
ub = 0 + [10] * [8] = 80 

或者我需要在降低其價值/重量的順序爲12,9,8,5,5對項目進行排序？然後計算上限？ 或者我正確地做，沒有排序，計算上限並繼續下一個項目？

在沒有排序的方法中，我不會獲得節點0的最大上限，我認爲是這樣。

ub = 0 + [10] * [12] = 120 // if sorted 

感謝您的幫助。

Answer 1

節點零的上界是分數揹包的貪婪解。 只需取最高值/重量比的元素，並繼續插入，直到沒有剩餘空間或完全插入。並重復這個過程。