背包問題
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/f/fd/Knapsack.svg/250px-Knapsack.svg.png)
背包問題(英語:Knapsack problem)是一種組合最佳化的NP完全問題。問題可以描述為:給定一組物品,每種物品都有自己的重量和價格,在限定的總重量內,我們如何選擇,才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包中,背包的空間有限,但我們需要最大化背包內所裝物品的價值。背包問題通常出現在資源分配中,決策者必須分別從一組不可分割的專案或任務中進行選擇,而這些專案又有時間或預算的限制。
背包問題歷史悠久,甚至可以追溯到1897年。[1]「背包問題」一詞最早出現於數學家托比阿斯·丹齊格的早期研究中,[2]他研究的問題是如何打包行李,要求最大化所選行李的價值且不能超載。
應用
背包問題出現在現實世界很多領域的決策過程中,諸如尋找節約原料的生產方式[3]、選擇投資專案及投資組合[4]、選擇證券化的資產[5]以及為默克爾-赫爾曼[6]和其他背包密碼系統生成金鑰。
背包問題的一個早期應用是測驗編製與測驗賦分,受測試者可以選擇他們所需回答的問題。舉個例子,受測者需要回答12道題,每道題10分,這時受測者只需要答對10道題就能得到滿分100分。但是假如說每道題的賦分不同,問題的選擇工作將會變得比較困難。對此,費爾曼和魏斯構建了一個系統,該系統分發給學生一張總分為125分且每道題賦分不等的考卷,學生則去盡力回答所有的問題。利用背包演算法,可以算出每個學生可能獲得的最高分數。[7]
1999年石溪大學演算法庫的一項研究表明,在75個演算法問題中,背包問題在最受歡迎的問題中排名第19,在最常用的問題中排名第三,僅次於字尾樹和集裝最佳化問題。[8]
定義
我們有n種物品,物品j的重量為wj,價格為pj。
我們假定所有物品的重量和價格都是非負的。背包所能承受的最大重量為W。
如果限定每種物品只能選擇0個或1個,則問題稱為0-1背包問題。
可以用公式表示為:
- 最大化
- 受限於
如果限定物品j最多只能選擇bj個,則問題稱為有界背包問題。
可以用公式表示為:
- 最大化
- 受限於
如果不限定每種物品的數量,則問題稱為無界背包問題。
各類複雜的背包問題總可以變換為簡單的0-1背包問題進行求解。
計算複雜度
在電腦科學領域,人們對背包問題感興趣的原因在於:
- 利用動態規劃,背包問題存在一個偽多項式時間演算法
- 把上面演算法作為子程式,背包問題存在完全逼近多項式時間方案
- 作為NP完全問題,背包問題沒有一種既準確又快速(多項式時間)的演算法
動態規劃解法
無界背包問題
如果重量w1, ..., wn和W都是非負數,那麼用動態規劃,可以用偽多項式時間解決背包問題。下面描述了無界背包問題的解法。
簡便起見,我們假定重量都是正數(wj > 0)。在總重量不超過W的前提下,我們希望總價格最高。對於Y ≤ W,我們將在總重量不超過Y的前提下,總價格所能達到的最高值定義為A(Y)。A(W)即為問題的答案。
顯然,A(Y)滿足:
- A(0) = 0
- A(Y) = max { A(Y - 1), { pj + A(Y - wj) | wj ≤ Y } }
其中,pj為第j種物品的價格。
關於第二個公式的一個解釋:總重量為Y時背包的最高價值可能有兩種情況,第一種是該重量無法被完全填滿,這對應於表達式A(Y - 1)。第二種是剛好填滿,這對應於一個包含一系列剛好填滿的可能性的集合,其中的可能性是指當最後放進包中的物品恰好是重量為wj的物品時背包填滿並達到最高價值。而這時的背包價值等於重量為wj物品的價值pj和當沒有放入該物品時背包的最高價值之和。故歸納為表達式pj + A(Y - wj)。最後把所有上述情況中背包價值的最大值求出就得到了A(Y)的值。
如果總重量為0,總價值也為0。然後依次計算A(0), A(1), ..., A(W),並把每一步驟的結果存入表中供後續步驟使用,完成這些步驟後A(W)即為最終結果。由於每次計算A(Y)都需要檢查n種物品,並且需要計算W個A(Y)值,因此動態規劃解法的時間複雜度為O(nW)。如果把w1, ..., wn, W都除以它們的最大公因數,演算法的時間將得到很大的提升。
儘管背包問題的時間複雜度為O(nW),但它仍然是一個NP完全問題。這是因為W同問題的輸入大小並不成線性關係。原因在於問題的輸入大小僅僅取決於表達輸入所需的位元數。事實上,,即表達W所需的位元數,同問題的輸入長度成線性關係。
0-1背包問題
類似的方法可以解決0-1背包問題,演算法同樣需要偽多項式時間。我們同樣假定和都是正整數。我們將在總重量不超過的前提下,前種物品的總價格所能達到的最高值定義為。
的遞推關係為:
- 如果,則
- 如果,則
通過計算即得到最終結果。
為提高演算法效能,我們把先前計算的結果存入表中。因此演算法需要的時間和空間都為,通過對演算法的改進,空間的消耗可以降至。
二次背包問題
推廣的背包問題有二次背包問題、多維背包問題、多目標背包問題等。
二次背包問題是背包問題的一種推廣形式:
最大化 | |||
受限於 | |||
for all |
參考文獻
- ^ Mathews, G. B. On the partition of numbers (PDF). Proceedings of the London Mathematical Society. 1897-06-25, 28: 486–490 [2022-05-05]. doi:10.1112/plms/s1-28.1.486. (原始內容 (PDF)存檔於2012-05-26).
- ^ Dantzig, Tobias. Number : the language of science The Masterpiece Science. New York: Plume Book. 2007. ISBN 9780452288119.
- ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David. Knapsack problems. Berlin: Springer. 2004: 449 [2022-05-05]. ISBN 978-3-540-40286-2.
- ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David. Knapsack problems. Berlin: Springer. 2004: 461 [2022-05-05]. ISBN 978-3-540-40286-2.
- ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David. Knapsack problems. Berlin: Springer. 2004: 465 [2022-05-05]. ISBN 978-3-540-40286-2.
- ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David. Knapsack problems. Berlin: Springer. 2004: 472 [2022-05-05]. ISBN 978-3-540-40286-2.
- ^ Feuerman, Martin; Weiss, Harvey. A Mathematical Programming Model for Test Construction and Scoring. Management Science. April 1973, 19 (8): 961–966. JSTOR 2629127. doi:10.1287/mnsc.19.8.961.
- ^ Skiena, S. S. Who is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithm Repository. ACM SIGACT News. September 1999, 30 (3): 65–74. CiteSeerX 10.1.1.41.8357
. ISSN 0163-5700. S2CID 15619060. doi:10.1145/333623.333627.
外部連結
- 二次背包問題原始碼連結 (頁面存檔備份,存於互聯網檔案館)