背包問題

背包問題的一個例子：應該選擇哪些盒子，才能使價格儘可能地大，而保持重量小於或等於15 kg？當然這只是一維的限制條件，還存在多維限制條件的背包問題，比如空間和重量均可設限

背包問題（英語：Knapsack problem）是一種組合優化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包中，背包的空間有限，但我們需要最大化背包內所裝物品的價值。背包問題通常出現在資源分配中，決策者必須分別從一組不可分割的項目或任務中進行選擇，而這些項目又有時間或預算的限制。

背包問題歷史悠久，甚至可以追溯到1897年。「背包問題」一詞最早出現於數學家托比阿斯·丹齊格的早期研究中，他研究的問題是如何打包行李，要求最大化所選行李的價值且不能超載。

應用

背包問題出現在現實世界很多領域的決策過程中，諸如尋找節約原料的生產方式、選擇投資項目及投資組合、選擇證券化的資產以及為默克爾-赫爾曼和其他背包密碼系統生成密鑰。

背包問題的一個早期應用是測驗編製與測驗賦分，受測試者可以選擇他們所需回答的問題。舉個例子，受測者需要回答12道題，每道題10分，這時受測者只需要答對10道題就能得到滿分100分。但是假如說每道題的賦分不同，問題的選擇工作將會變得比較困難。對此，費爾曼和魏斯構建了一個系統，該系統分發給學生一張總分為125分且每道題賦分不等的考卷，學生則去盡力回答所有的問題。利用背包算法，可以算出每個學生可能獲得的最高分數。

1999年石溪大學算法庫的一項研究表明，在75個算法問題中，背包問題在最受歡迎的問題中排名第19，在最常用的問題中排名第三，僅次於後綴樹和集裝優化問題。

定義

我們有n種物品，物品j的重量為w_j，價格為p_j。
我們假定所有物品的重量和價格都是非負的。背包所能承受的最大重量為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最多只能選擇b_j個，則問題稱為有界背包問題。
可以用公式表示為：

最大化$\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背包問題進行求解。

計算複雜度

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

• 利用動態規劃，背包問題存在一個偽多項式時間算法
• 把上面算法作為子程序，背包問題存在完全逼近多項式時間方案
• 作為NP完全問題，背包問題沒有一種既準確又快速（多項式時間）的算法

動態規劃解法

無界背包問題

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

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

顯然，A(Y)滿足：

• A(0) = 0
• A(Y) = max { A(Y - 1), { p_j + A(Y - w_j) | w_j ≤ Y } }

其中，p_j為第j種物品的價格。

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

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

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

0-1背包問題

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

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

• $A(0,Y)=0$
• 如果$w_{j}>Y$，則$A(j,Y)=A(j-1,Y)$
• 如果$w_{j}\leq Y$，則$A(j,Y)=\max \lbrace A(j-1,Y),p_{j}+A(j-1,Y-w_{j})\rbrace$

通過計算$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$

外部連結

• 二次背包問題源代碼鏈接 （頁面存檔備份，存於網際網路檔案館）