背包问题:修订间差异

维基百科,自由的百科全书
删除的内容 添加的内容
第7行: 第7行:
背包问题历史悠久,甚至可以追溯到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 = 25 June 1897 | url = http://plms.oxfordjournals.org/content/s1-28/1/486.full.pdf |doi = 10.1112/plms/s1-28.1.486}}</ref>“背包问题”一词最早出现于数学家托拜厄斯·丹齐格的早期研究中,<ref>Dantzig, Tobias. Numbers: The Language of Science, 1930.</ref>他所研究的问题是如何打包行李,要求最大化所选行李的价值且不能超载。
背包问题历史悠久,甚至可以追溯到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 = 25 June 1897 | url = http://plms.oxfordjournals.org/content/s1-28/1/486.full.pdf |doi = 10.1112/plms/s1-28.1.486}}</ref>“背包问题”一词最早出现于数学家托拜厄斯·丹齐格的早期研究中,<ref>Dantzig, Tobias. Numbers: The Language of Science, 1930.</ref>他所研究的问题是如何打包行李,要求最大化所选行李的价值且不能超载。
==应用==
==应用==
背包问题出现在现实世界很多领域的决策过程中,诸如寻找节约原料的生产方式<ref>Kellerer, Pferschy, and Pisinger 2004, p. 449</ref>、选择投资项目及投资组合<ref>Kellerer, Pferschy, and Pisinger 2004, p. 461</ref>、选择[[资产证券化|证券化]]的资产<ref>Kellerer, Pferschy, and Pisinger 2004, p. 465</ref>以及为默克尔-赫尔曼<ref>Kellerer, Pferschy, and Pisinger 2004, p. 472</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=5 May 2022}}</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=5 May 2022}}</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=5 May 2022}}</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=5 May 2022}}</ref>和其他背包密码系统生成密钥。


==定义==
==定义==

2022年5月5日 (四) 10:48的版本

背包问题的一个例子:应该选择哪些盒子,才能使价格尽可能地大,而保持重量小于或等于15 kg?当然这只是一维的限制条件,还存在多维限制条件的背包问题,比如空间和重量均可设限

背包问题(Knapsack problem)是一种组合优化NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中,背包的空间有限,但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中,决策者必须分别从一组不可分割的项目或任务中进行选择,而这些项目又有时间或预算的限制。

背包问题历史悠久,甚至可以追溯到1897年。[1]“背包问题”一词最早出现于数学家托拜厄斯·丹齐格的早期研究中,[2]他所研究的问题是如何打包行李,要求最大化所选行李的价值且不能超载。

应用

背包问题出现在现实世界很多领域的决策过程中,诸如寻找节约原料的生产方式[3]、选择投资项目及投资组合[4]、选择证券化的资产[5]以及为默克尔-赫尔曼[6]和其他背包密码系统生成密钥。

定义

我们有n种物品,物品j的重量为wj,价格为pj
我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W
如果限定每种物品只能选择0个或1个,则问题称为0-1背包问题

可以用公式表示为:

最大化
受限于

如果限定物品j最多只能选择bj个,则问题称为有界背包问题
可以用公式表示为:

最大化
受限于

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

计算复杂度

在计算机科学领域,人们对背包问题感兴趣的原因在于:

动态规划解法

无界背包问题

如果重量w1, ..., wnW都是非负数,那么用动态规划,可以用伪多项式时间解决背包问题。下面描述了无界背包问题的解法。

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

显然,A(Y)满足:

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

其中,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种物品,并且需要计算WA(Y)值,因此动态规划解法的时间复杂度为O(nW)。如果把w1, ..., wn, W都除以它们的最大公因数,算法的时间将得到很大的提升。

尽管背包问题的时间复杂度为O(nW),但它仍然是一个NP完全问题。这是因为W同问题的输入大小并不成线性关系。原因在于问题的输入大小仅仅取决于表达输入所需的比特数。事实上,,即表达W所需的比特数,同问题的输入长度成线性关系。

0-1背包问题

类似的方法可以解决0-1背包问题,算法同样需要伪多项式时间。我们同样假定都是正整数。我们将在总重量不超过的前提下,前种物品的总价格所能达到的最高值定义为

的递推关系为:

  • 如果,则
  • 如果,则

通过计算即得到最终结果。

为提高算法性能,我们把先前计算的结果存入表中。因此算法需要的时间和空间都为,通过对算法的改进,空间的消耗可以降至

二次背包问题

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

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

最大化
受限于
for all

参考文献

  1. ^ Mathews, G. B. On the partition of numbers (PDF). Proceedings of the London Mathematical Society. 25 June 1897, 28: 486–490. doi:10.1112/plms/s1-28.1.486. 
  2. ^ Dantzig, Tobias. Numbers: The Language of Science, 1930.
  3. ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David. Knapsack problems. Berlin: Springer. 2004: 449 [5 May 2022]. ISBN 978-3-540-40286-2. 
  4. ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David. Knapsack problems. Berlin: Springer. 2004: 461 [5 May 2022]. ISBN 978-3-540-40286-2. 
  5. ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David. Knapsack problems. Berlin: Springer. 2004: 465 [5 May 2022]. ISBN 978-3-540-40286-2. 
  6. ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David. Knapsack problems. Berlin: Springer. 2004: 472 [5 May 2022]. ISBN 978-3-540-40286-2. 

外部链接