背包问题

背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。

也可以将背包问题描述为决定性问题，即在总重量不超过的前提下，总价值是否能达到。

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

可以用公式表示为：

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

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

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

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

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

显然，()满足：

其中，为第种物品的价格。

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

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

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

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

(, )的递推关系为：

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

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

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