背包問題

維基百科,自由的百科全書
前往: 導覽搜尋
背包問題的一個例子:應該選擇哪些盒子,才能使價格儘可能地大,而保持重量小於或等於15 kg?

背包問題(Knapsack problem)是一種組合優化NP完全問題。問題可以描述為:給定一組物品,每種物品都有自己的重量和價格,在限定的總重量內,我們如何選擇,才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包中。

相似問題經常出現在商業、組合數學計算複雜性理論密碼學應用數學等領域中。

也可以將背包問題描述為決定性問題,即在總重量不超過W的前提下,總價值是否能達到V

定義[編輯]

我們有n種物品,物品j的重量為wj,價格為pj。我們假定所有物品的重量和價格都是非負的。背包所能承受的最大重量為W

如果限定每種物品只能選擇0個或1個,則問題稱為0-1背包問題。可以用公式表示為:

最大化 \qquad \sum_{j=1}^n p_j\,x_j
受限於 \qquad \sum_{j=1}^n w_j\,x_j \ \leqslant \ W, \quad \quad x_j \ \in \ \{0,1\}

如果限定物品j最多只能選擇bj個,則問題稱為有界背包問題。可以用公式表示為:

最大化 \qquad \sum_{j=1}^n p_j\,x_j
受限於 \qquad \sum_{j=1}^n w_j\,x_j \ \leqslant \ W, \quad \quad x_j \ \in \ \{0,1,\ldots,b_j\}

如果不限定每種物品的數量,則問題稱為無界背包問題
各類複雜的背包問題總可以變換為簡單的0-1背包問題進行求解。

計算複雜度[編輯]

在計算機科學領域,人們對背包問題感興趣的原因在於:

動態規劃解法[編輯]

無界背包問題[編輯]

如果重量w1, ..., wnW都是非負的整數,那麼用動態規劃,可以用偽多項式時間解決背包問題。下面描述了無界背包問題的解法。

簡便起見,我們假定重量都是正整數(wj > 0)。在總重量不超過W的前提下,我們希望總價格最高。對於YW,我們將在總重量不超過Y的前提下,總價格所能達到的最高值定義為A(Y)。A(W)即為問題的答案。

顯然,A(Y)滿足:

  • A(0) = 0
  • A(Y) = max { A(Y - 1), max { pj + A(Y - wj) | wjY } }

其中,pj為第j種物品的價格。

關於第二個公式的一個解釋:總重量為Y時背包的最高價值可能有兩種情況,第一種是該重量無法被完全填滿,這對應於表達式A(Y - 1)。第二種是剛好填滿,這對應於一個包含一系列剛好填滿的可能性的集合,其中的可能性是指當最後放進包中的物品恰好是重量為wj的物品時背包填滿並達到最高價值。而這時的背包價值等於重量為wj物品的價值和當沒有放入該物品時背包的最高價值之和。故歸納為表達式pj + A(Y - wj)。最後把所有上述情況中背包價值的最大值求出就得到了A(Y)的值。

如果總重量為0,總價值也為0。然後依次計算A(0), A(1), ..., A(W),並把每一步驟的結果存入表中供後續步驟使用,完成這些步驟後A(W)即為最終結果。由於每次計算A(Y)都需要檢查n種物品,並且需要計算WA(Y)值,因此動態規劃解法的時間複雜度為O(nW)。如果把w1, ..., wn, W都除以它們的最大公因數,演算法的時間將得到很大的提升。

儘管背包問題的時間複雜度為O(nW),但它仍然是一個NP完全問題。這是因為W同問題的輸入大小並不成線性關係。原因在於問題的輸入大小僅僅取決於表達輸入所需的比特數。事實上,log W,即表達W所需的比特數,同問題的輸入長度成線性關係。

0-1背包問題[編輯]

類似的方法可以解決0-1背包問題,演算法同樣需要偽多項式時間。我們同樣假定w1, ..., wnW都是正整數。我們將在總重量不超過Y的前提下,前j種物品的總價格所能達到的最高值定義為A(j, Y)。

A(j, Y)的遞推關係為:

  • A(0, Y) = 0
  • A(j, 0) = 0
  • 如果wj > Y, A(j, Y) = A(j - 1, Y)
  • 如果wjY, A(j, Y) = max { A(j - 1, Y), pj + A(j - 1, Y - wj) }

通過計算A(n, W)即得到最終結果。為提高演算法性能,我們把先前計算的結果存入表中。因此演算法需要的時間和空間都為O(nW),通過對演算法的改進,空間的消耗可以降至O(W)。

二次背包問題[編輯]

推廣的背包問題有二次背包問題多維背包問題多目標背包問題等。

二次背包問題是背包問題的一種推廣形式:

最大化 \sum_{j=1}^n p_j x_j+\sum_{i=1}^{n-1}\sum_{j=i+1}^n p_{ij} x_i x_j
受限於 \sum_{j=1}^n w_j x_j \leq W,
 x_j \in \{0,1\} for all 1 \leq j \leq n

外部連結[編輯]