背包问题是数学优化中的一类问题:给定若干重量和价值已知的物品,选择其中的一部分,使总重量不超过给定容量,并使总价值尽可能大。这个名称让人联想到向承重有限的背包中装入物品。标准的 0–1背包问题规定每件物品最多只能选择一次;其他变体则允许重复选取物品、分割物品、使用多个背包,或同时施加多种资源约束。它是计算机科学中的一个重要范例,因为一些密切相关的版本可以高效求解,另一些版本却在计算上十分困难。
数学表述
对于 件物品,设物品 的重量为 ,价值为 ,背包容量为 。标准的0–1形式为
变量 表示是否选择物品 。这是整数规划的一个特例,具有一个容量约束,且决策变量均为二元变量。
重量不一定表示物理意义上的质量,也可以表示成本、存储空间占用、处理时间或其他有限资源。价值则可以表示利润、效用、优先级或预期收益。
常见的算法表述假定重量为正整数,价值为非负整数,并以二进制编码这些数值。也可以考虑有理数输入,但此时必须谨慎理解那些依赖数值大小的运行时间。重量超过容量的物品可以直接舍弃。在通常的模型中,重量为零且价值为正的物品可以直接选入。
例如,假设容量为 :
| 物品 | 重量 | 价值 | 价值重量比 |
|---|---|---|---|
| A | 10 | 60 | 6 |
| B | 20 | 100 | 5 |
| C | 30 | 120 | 4 |
按价值重量比从高到低选择物品,会选中A和B,总价值为 。最优选择则是B和C,总价值为 。这说明,对于不可分割的物品,局部看来有利的选择未必能得到最优组合。
主要变体
0–1背包、多重背包与完全背包
在0–1背包问题中,每件物品要么选取,要么不选。
在多重背包问题中,第 类物品的可用数量为给定的 ,因此
在完全背包问题中,每类物品都可以选取任意非负整数件。由于物品重量为正,有限容量内只能装入有限件物品。将物品数量拆分成若干组,就可以把多重背包实例转化为0–1背包实例,常用的方法是二进制分组。
尽管这些变体彼此相似,但其递推关系不同,或者在节省内存的实现中需要采用不同的更新顺序。
分数背包
在分数背包问题中,每件物品都可以分割:
求解时,先按 从高到低排列物品,能装下整件时就选取整件,再从下一件物品中取出恰好填满剩余容量的部分,即可得到最优解。若采用基于比较的排序,这种贪心算法的时间为 。
其正确性依赖于物品的可分割性:将一定数量、价值重量比较低的物品替换为同等重量、价值重量比较高的物品,不会降低总价值。这种交换论证不适用于不可分割的物品。
多重约束与多个背包
在多维背包问题中,每件物品都会消耗多种资源。约束形式为
例如,一个项目可能既消耗资金,又占用人员工时。此时,以容量为索引的动态规划,其状态空间大小通常取决于各项容量的乘积,因而可能大到难以处理。
在多背包问题中,需要将物品分配到多个各有容量限制的背包中,且通常每件物品最多只能分配到一个背包。这与多维背包不同:使用多个容器,不等于对同一组选取的物品同时施加多种资源限制。
其他扩展还会加入分组选择、依赖关系、物品间冲突或非线性价值等条件。这些附加条件可能显著改变可用的算法及其近似保证。
计算复杂性
优化问题要求找出总价值最大的可行选择。其判定版本则询问,是否存在一种选择,同时满足
其中 为目标价值。
对于以二进制编码的整数输入,这一判定问题具有NP完全性,而优化问题具有NP难性。给定一种选择,可以高效验证其是否满足要求,但目前尚无能在多项式时间内精确求解所有实例的算法。如果存在这样的算法,就能解决P与NP问题,证明 。
标准问题是弱NP完全的,这反映出它对数值大小的依赖。它存在一种伪多项式时间算法,其运行时间是 和 的多项式,但未必是二进制输入长度的多项式。表示 只需要 位,因此遍历从零到 的所有容量,相对于这一表示的长度而言,可能需要指数级的步骤。
与之密切相关的子集和问题询问,能否从输入的数中选出若干个,使其和恰好等于目标值 。将每件物品的重量和价值都设为对应的输入数,将容量设为 ,并要求总价值至少为 ,就可以将其表述为背包问题。
精确算法
穷举搜索与折半搜索
枚举所有子集需要考察 种可能。这种方法只有在 较小时才实用,不过剪枝可以减少某些实例中的计算量。
折半搜索算法将物品分成两组,分别枚举每组能够达到的重量—价值对。删除被支配的数对并排序后,再将两组中彼此兼容的选择组合起来。忽略多项式因子,其运行时间约为 ,但需要较大的内存。
当物品数量适中,而容量过大、不适合建立以容量为索引的表时,这种方法很有用。
按容量进行动态规划
对于整数重量,动态规划提供了一种精确求解方法。定义 为仅使用前 件物品、容量为 时能够获得的最大价值,则有
边界条件为 ,答案为 。
共有 个状态,在通常的算术计算模型下,处理每个状态只需常数次操作。因此,时间复杂度为 。存储完整表格需要 的空间;若只保留求最优值所需的信息,则可将空间复杂度降至 。
一维实现按降序更新容量:
dp[0 ... W] = 0
对于每件物品 i:
令 c 从 W 递减至 w[i]:
dp[c] = max(dp[c], dp[c - w[i]] + v[i])
降序更新可防止当前物品被重复使用。若改为按升序更新容量,就允许重复使用该物品,实现的便是相应的完全背包递推关系。
要还原所选物品,需要额外记录信息、保留表格,或使用重构过程;仅有最优值数组,并不能直接记录具体选择。
按价值进行动态规划
当价值为较小的整数而重量很大时,可以将这两个量的作用对调。设 为使用前 件物品、使总价值恰好为 所需的最小重量。不可达状态的重量设为 。
递推关系为
其中,当 时省略第二项。答案是满足 的最大 。
若 ,则基本算法的时间为 。这种表述也为通过缩放价值进行近似求解奠定了基础。
分支定界法与优化求解器
分支定界法在探索部分选择方案的同时,舍弃那些不可能改进当前最佳可行解的分支。求解分数松弛问题,可以给出某个分支所能达到的价值上界。
实用的整数规划求解器可能将这类界与预处理、割平面和专门的搜索方法结合使用。它们能够求解许多规模可观的实例,但性能高度依赖实例结构,并不能消除最坏情况下的复杂性。
近似算法
尽管精确优化具有NP难性,标准0–1背包问题仍然可以高效地进行近似求解。
一种简单的近似算法首先舍弃重量超过容量的物品,再将剩余物品按价值重量比排序。它取出排序序列中、首件会导致容量超限的物品之前的整件物品前缀,并将该前缀与价值最高的可行单件物品进行比较。两者中较好的选择,其价值至少为最优值的一半。
这一保证来自分数松弛:分数松弛的最优值,不超过上述前缀的价值加上首件无法完整装入的物品的全部价值。这两项分别不超过所比较的两个候选解的价值。
更进一步,0–1背包问题存在完全多项式时间近似方案,即完全多项式时间近似方案(FPTAS)。对于任意 ,它都能在关于输入长度和 的多项式时间内,返回一个价值至少为
的可行解。
一种标准构造方法是:舍弃不可行的物品,令 为剩余物品中的最大价值,并设置
若所有可行物品的价值都为零,该实例便可直接求解。否则,用动态规划精确求解缩放价值后的实例。每件选中物品因取整而损失的价值小于 ,因此总损失至多为
在标准算术计算模型下,一种直接实现的时间为 。更先进的方案可以改进这一界。这些保证适用于标准的单约束问题,并不会自动延伸到其扩展形式。
应用与建模局限
背包模型出现在预算分配、货物选择、项目选择、存储管理和资源受限调度等领域。它们也会作为子问题,嵌入规模更大的优化方法中。
基本模型假设各件物品的价值可以独立相加,且资源消耗已知。它不能直接刻画某些相互作用,例如两个项目只有同时选中才有价值、未来成本存在不确定性,或优先级无法用单一数值目标表示等情形。依赖关系和多种资源都需要通过明确扩展模型来处理。
背包问题与装箱问题相关,但并不相同。背包问题通常是在有限容量下选择价值较高的物品子集;装箱问题则通常要求装入所有物品,同时尽量减少容器数量。
类似背包的问题也曾用于密码学。早期方案包括基于具有特定结构的子集和实例构建的公钥系统。一些著名的早期构造后来被攻破:一般背包实例的求解难度,并不能证明某种具有特定结构的密码构造是安全的。