背包问题

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

背包问题的一个早期应用是测验编制与测验赋分，受测试者可以选择他们所需回答的问题。举个例子，受测者需要回答12道题，每道题10分，这时受测者只需要答对10道题就能得到满分100分。但是假如说每道题的赋分不同，问题的选择工作将会变得比较困难。对此，费尔曼和魏斯构建了一个系统，该系统分发给学生一张总分为125分且每道题赋分不等的考卷，学生则去尽力回答所有的问题。利用背包算法，可以算出每个学生可能获得的最高分数。^[7]

1999年石溪大学算法库的一项研究表明，在75个算法问题中，背包问题在最受欢迎的问题中排名第19，在最常用的问题中排名第三，仅次于后缀树和集装优化问题。^[8]

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

可以用公式表示为：

最大化${\displaystyle \qquad \sum _{j=1}^{n}p_{j}\,x_{j}}$ 

受限于${\displaystyle \qquad \sum _{j=1}^{n}w_{j}\,x_{j}\ \leqslant \ W,\quad \quad x_{j}\ \in \ \{0,1\}}$ 

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

最大化${\displaystyle \qquad \sum _{j=1}^{n}p_{j}\,x_{j}}$ 

受限于${\displaystyle \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同问题的输入大小并不成线性关系。原因在于问题的输入大小仅仅取决于表达输入所需的比特数。事实上，${\displaystyle \left\lfloor log_{2}W\right\rfloor +1}$ ，即表达W所需的比特数，同问题的输入长度成线性关系。

0-1背包问题

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

${\displaystyle A(j,Y)}$ 的递推关系为：

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

通过计算${\displaystyle A(n,W)}$ 即得到最终结果。

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

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

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

• 二次背包问题源代码链接 （页面存档备份，存于互联网档案馆）