查看“︁背包问题”︁的源代码

{{NoteTA
|G1 = IT
}}
[[File:Knapsack.svg|缩略图|250x250像素|背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？当然这只是一维的限制条件，还存在多维限制条件的背包问题，比如空间和重量均可设限]]
'''背包问题'''（{{lang-en|Knapsack problem}}）是一种[[组合优化]]的[[NP完全]]问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中，决策者必须分别从一组不可分割的项目或任务中进行选择，而这些项目又有时间或预算的限制。

背包问题历史悠久，甚至可以追溯到1897年。<ref>{{cite journal | title = On the partition of numbers | author = Mathews, G. B. | journal = Proceedings of the London Mathematical Society | volume = 28 | pages = 486&ndash;490 | date = 1897-06-25 | url = http://plms.oxfordjournals.org/content/s1-28/1/486.full.pdf | doi = 10.1112/plms/s1-28.1.486 | access-date = 2022-05-05 | archive-date = 2012-05-26 | archive-url = https://web.archive.org/web/20120526165606/http://plms.oxfordjournals.org/content/s1-28/1/486.full.pdf }}</ref>“背包问题”一词最早出现于数学家[[托比阿斯·丹齊格]]的早期研究中，<ref>{{cite book |last1=Dantzig |first1=Tobias |title=Number : the language of science |url=https://archive.org/details/numberlanguageof0000dant_r6m8 |date=2007 |publisher=Plume Book |location=New York |isbn=9780452288119 |edition=The Masterpiece Science}}</ref>他研究的问题是如何打包行李，要求最大化所选行李的价值且不能超载。

==应用==
背包问题出现在现实世界很多领域的决策过程中，诸如寻找节约原料的生产方式<ref>{{cite book |last1=Kellerer |first1=Hans |last2=Pferschy |first2=Ulrich |last3=Pisinger |first3=David |title=Knapsack problems |date=2004 |publisher=Springer |location=Berlin |isbn=978-3-540-40286-2 |page=449 |url=https://books.google.com.tw/books/about/Knapsack_Problems.html?id=u5DB7gck08YC&redir_esc=y |access-date=2022-05-05}}</ref>、选择投资项目及投资组合<ref>{{cite book |last1=Kellerer |first1=Hans |last2=Pferschy |first2=Ulrich |last3=Pisinger |first3=David |title=Knapsack problems |date=2004 |publisher=Springer |location=Berlin |isbn=978-3-540-40286-2 |page=461 |url=https://books.google.com.tw/books/about/Knapsack_Problems.html?id=u5DB7gck08YC&redir_esc=y |access-date=2022-05-05}}</ref>、选择[[资产证券化|证券化]]的资产<ref>{{cite book |last1=Kellerer |first1=Hans |last2=Pferschy |first2=Ulrich |last3=Pisinger |first3=David |title=Knapsack problems |date=2004 |publisher=Springer |location=Berlin |isbn=978-3-540-40286-2 |page=465 |url=https://books.google.com.tw/books/about/Knapsack_Problems.html?id=u5DB7gck08YC&redir_esc=y |access-date=2022-05-05}}</ref>以及为默克尔-赫尔曼<ref>{{cite book |last1=Kellerer |first1=Hans |last2=Pferschy |first2=Ulrich |last3=Pisinger |first3=David |title=Knapsack problems |date=2004 |publisher=Springer |location=Berlin |isbn=978-3-540-40286-2 |page=472 |url=https://books.google.com.tw/books/about/Knapsack_Problems.html?id=u5DB7gck08YC&redir_esc=y |access-date=2022-05-05}}</ref>和其他背包密码系统生成密钥。

背包問題的一個早期應用是測驗編製與測驗賦分，受測試者可以選擇他們所需回答的問題。举个例子，受测者需要回答12道题，每道题10分，这时受测者只需要答对10道题就能得到满分100分。但是假如说每道题的赋分不同，问题的选择工作将会变得比较困难。对此，费尔曼和魏斯构建了一个系统，该系统分发给学生一张总分为125分且每道题赋分不等的考卷，学生则去尽力回答所有的问题。利用背包算法，可以算出每个学生可能获得的最高分数。<ref>{{cite journal | title = A Mathematical Programming Model for Test Construction and Scoring | url = https://archive.org/details/sim_management-science_1973-04_19_8/page/961 | journal = Management Science | volume = 19 | issue = 8 |date = April 1973|pages = 961–966 |author1=Feuerman, Martin |author2=Weiss, Harvey | jstor = 2629127 | doi=10.1287/mnsc.19.8.961}}</ref>

1999年[[石溪大学]]算法库的一项研究表明，在75个算法问题中，背包问题在最受欢迎的问题中排名第19，在最常用的问题中排名第三，仅次于[[后缀树]]和[[集装优化|集装优化问题]]。<ref>{{cite journal | title = Who is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithm Repository | author = Skiena, S. S. |journal = ACM SIGACT News | volume = 30 | issue=3 |date = September 1999| pages= 65&ndash;74  |issn=0163-5700 | doi=10.1145/333623.333627| citeseerx = 10.1.1.41.8357 | s2cid = 15619060 }}</ref>

==定义==

我们有''n''种物品，物品''j''的重量为''w<sub>j</sub>''，价格为''p<sub>j</sub>''。<br />
我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为''W''。<br />
如果限定每种物品只能选择0个或1个，则问题称为'''0-1背包问题'''。<br /><br />
可以用公式表示为：
:最大化<math>\qquad \sum_{j=1}^n p_j\,x_j</math>
:受限于<math>\qquad \sum_{j=1}^n w_j\,x_j \ \leqslant \ W, \quad \quad x_j \ \in \ \{0,1\}</math>

如果限定物品''j''最多只能选择''b<sub>j</sub>''个，则问题称为'''有界背包问题'''。<br />
可以用公式表示为：
:最大化<math>\qquad \sum_{j=1}^n p_j\,x_j</math>
:受限于<math>\qquad \sum_{j=1}^n w_j\,x_j \ \leqslant \ W, \quad \quad x_j \ \in \ \{0,1,\ldots,b_j\}</math>

如果不限定每种物品的数量，则问题称为'''无界背包问题'''。<br />
各类复杂的背包问题总可以变换为简单的0-1背包问题进行求解。

==计算复杂度==
在计算机科学领域，人们对背包问题感兴趣的原因在于：
* 利用[[动态规划]]，背包问题存在一个[[伪多项式时间]]算法
* 把上面算法作为子程序，背包问题存在[[完全逼近多项式时间方案]]
* 作为[[NP完全]]问题，背包问题没有一种既准确又快速（多项式时间）的算法

==动态规划解法==

===无界背包问题===

如果重量''w<sub>1</sub>'', ..., ''w<sub>n</sub>''和''W''都是非负数，那么用[[动态规划]]，可以用[[伪多项式时间]]解决背包问题。下面描述了无界背包问题的解法。

简便起见，我们假定重量都是正数（w<sub>j</sub> > 0）。在总重量不超过''W''的前提下，我们希望总价格最高。对于''Y'' ≤ ''W''，我们将在总重量不超过''Y''的前提下，总价格所能达到的最高值定义为''A''(''Y'')。''A''(''W'')即为问题的答案。

显然，''A''(''Y'')满足：
* ''A''(0) = 0
* ''A''(''Y'') = max { ''A''(''Y - 1''), { ''p<sub>j</sub>'' + ''A''(''Y'' - ''w<sub>j</sub>'') | ''w<sub>j</sub>'' ≤ ''Y'' } }
其中，''p<sub>j</sub>''为第''j''种物品的价格。

关于第二个公式的一个解释：总重量为''Y''时背包的最高价值可能有两种情况，第一种是该重量无法被完全填满，这对应于表达式''A''(''Y - 1'')。第二种是刚好填满，这对应于一个包含一系列刚好填满的可能性的集合，其中的可能性是指当最后放进包中的物品恰好是重量为''w<sub>j</sub>''的物品时背包填满并达到最高价值。而这时的背包价值等于重量为''w<sub>j</sub>''物品的价值''p<sub>j</sub>''和当没有放入该物品时背包的最高价值之和。故归纳为表达式''p<sub>j</sub>'' + ''A''(''Y'' - ''w<sub>j</sub>'')。最后把所有上述情况中背包价值的最大值求出就得到了''A''(''Y'')的值。

如果总重量为0，总价值也为0。然后依次计算''A''(0), ''A''(1), ..., ''A''(''W'')，并把每一步骤的结果存入表中供后续步骤使用，完成这些步骤后''A''(''W'')即为最终结果。由于每次计算''A''(''Y'')都需要检查''n''种物品，并且需要计算''W''个''A''(''Y'')值，因此动态规划解法的时间复杂度为O(''nW'')。如果把''w<sub>1</sub>'', ..., ''w<sub>n</sub>'', ''W''都除以它们的[[最大公因数]]，算法的时间将得到很大的提升。

尽管背包问题的时间复杂度为O(''nW'')，但它仍然是一个NP完全问题。这是因为''W''同问题的''输入大小''并不成线性关系。原因在于问题的输入大小仅仅取决于表达输入所需的比特数。事实上，<math>\left\lfloor log_{2} W\right\rfloor + 1</math>，即表达''W''所需的比特数，同问题的输入长度成线性关系。

===0-1背包问题===
类似的方法可以解决0-1背包问题，算法同样需要[[伪多项式时间]]。我们同样假定<math>w_1, w_2, \dots, w_n</math>和<math>W</math>都是正整数。我们将在总重量不超过<math>Y</math>的前提下，前<math>j</math>种物品的总价格所能达到的最高值定义为<math>A(j, Y)</math>。

<math>A(j, Y)</math>的递推关系为：
* <math>A(0, Y) = 0</math>
* 如果<math>w_j > Y</math>，则<math>A(j, Y) = A(j-1, Y)</math>
* 如果<math>w_j \le Y</math>，则<math>A(j, Y) = \max \lbrace A(j-1, Y), p_j + A(j-1, Y-w_j) \rbrace</math>

通过计算<math>A(n, W)</math>即得到最终结果。

为提高算法性能，我们把先前计算的结果存入表中。因此算法需要的时间和空间都为<math>O(n W)</math>，通过对算法的改进，空间的消耗可以降至<math>O(W)</math>。

==二次背包问题==

推广的背包问题有二次背包问题、[[多维背包问题]]、[[多目标背包问题]]等。

'''二次背包问题'''是背包问题的一种推广形式：

{|
|colspan="2"|最大化<math>\sum_{j=1}^n p_j x_j+\sum_{i=1}^{n-1}\sum_{j=i+1}^n p_{ij} x_i x_j</math>
|
|-
|受限于
|<math>\sum_{j=1}^n w_j x_j \leq W,</math>
|
|-
|
|<math> x_j \in \{0,1\}</math>
|for all <math>1 \leq j \leq n</math>
|
|}

==参考文献==
{{reflist}}
==外部链接==
*[http://www.adaptivebox.net/CILib/code/qkpcodes_link.html 二次背包问题源代码链接] {{Wayback|url=http://www.adaptivebox.net/CILib/code/qkpcodes_link.html |date=20150214020941 }}

[[Category:數學最佳化]]
[[Category:運籌學]]
[[Category:NP完全问题]]
[[Category:計算複雜性理論]]
[[Category:组合数学]]
[[Category:組合優化]]