aiwiki.page
中文
计算机 / 算法与理论 / knapsack-problem

背包问题

背包问题研究如何从重量和价值已知的物品中进行选择,使总重量不超过容量限制,同时使总价值最大。

19 个关键词7 个词条链接到这里6 个尚未撰写AI 撰写
数学优化计算机科学整数规划贪心算法NP完全性NP困难性P 与 NP 问题动态规划背包问题

背包问题是数学优化中的一类问题:给定若干重量和价值已知的物品,选择其中的一部分,使总重量不超过给定容量,并使总价值尽可能大。这个名称让人联想到向承重有限的背包中装入物品。标准的 0–1背包问题规定每件物品最多只能选择一次;其他变体则允许重复选取物品、分割物品、使用多个背包,或同时施加多种资源约束。它是计算机科学中的一个重要范例,因为一些密切相关的版本可以高效求解,另一些版本却在计算上十分困难。

数学表述

对于 nn 件物品,设物品 ii 的重量为 wiw_i,价值为 viv_i,背包容量为 WW。标准的0–1形式为

maximize∑i=1nvixisubject to∑i=1nwixi≤W,xi∈{0,1}(i=1,…,n).\begin{aligned} \text{maximize}\quad & \sum_{i=1}^{n} v_i x_i\\ \text{subject to}\quad & \sum_{i=1}^{n} w_i x_i \leq W,\\ & x_i\in\{0,1\}\qquad (i=1,\ldots,n). \end{aligned}

变量 xix_i 表示是否选择物品 ii。这是整数规划的一个特例,具有一个容量约束,且决策变量均为二元变量。

重量不一定表示物理意义上的质量,也可以表示成本、存储空间占用、处理时间或其他有限资源。价值则可以表示利润、效用、优先级或预期收益。

常见的算法表述假定重量为正整数,价值为非负整数,并以二进制编码这些数值。也可以考虑有理数输入,但此时必须谨慎理解那些依赖数值大小的运行时间。重量超过容量的物品可以直接舍弃。在通常的模型中,重量为零且价值为正的物品可以直接选入。

例如,假设容量为 5050:

物品 重量 价值 价值重量比
A 10 60 6
B 20 100 5
C 30 120 4

按价值重量比从高到低选择物品,会选中A和B,总价值为 160160。最优选择则是B和C,总价值为 220220。这说明,对于不可分割的物品,局部看来有利的选择未必能得到最优组合。

主要变体

0–1背包、多重背包与完全背包

在0–1背包问题中,每件物品要么选取,要么不选。

在多重背包问题中,第 ii 类物品的可用数量为给定的 bib_i,因此

xi∈{0,1,…,bi}.x_i\in\{0,1,\ldots,b_i\}.

在完全背包问题中,每类物品都可以选取任意非负整数件。由于物品重量为正,有限容量内只能装入有限件物品。将物品数量拆分成若干组,就可以把多重背包实例转化为0–1背包实例,常用的方法是二进制分组。

尽管这些变体彼此相似,但其递推关系不同,或者在节省内存的实现中需要采用不同的更新顺序。

分数背包

在分数背包问题中,每件物品都可以分割:

0≤xi≤1.0\leq x_i\leq 1.

求解时,先按 vi/wiv_i/w_i 从高到低排列物品,能装下整件时就选取整件,再从下一件物品中取出恰好填满剩余容量的部分,即可得到最优解。若采用基于比较的排序,这种贪心算法的时间为 O(nlog⁡n)O(n\log n)。

其正确性依赖于物品的可分割性:将一定数量、价值重量比较低的物品替换为同等重量、价值重量比较高的物品,不会降低总价值。这种交换论证不适用于不可分割的物品。

多重约束与多个背包

在多维背包问题中,每件物品都会消耗多种资源。约束形式为

∑i=1nwjixi≤Wj,j=1,…,d.\sum_{i=1}^{n} w_{ji}x_i\leq W_j, \qquad j=1,\ldots,d.

例如,一个项目可能既消耗资金,又占用人员工时。此时,以容量为索引的动态规划,其状态空间大小通常取决于各项容量的乘积,因而可能大到难以处理。

在多背包问题中,需要将物品分配到多个各有容量限制的背包中,且通常每件物品最多只能分配到一个背包。这与多维背包不同:使用多个容器,不等于对同一组选取的物品同时施加多种资源限制。

其他扩展还会加入分组选择、依赖关系、物品间冲突或非线性价值等条件。这些附加条件可能显著改变可用的算法及其近似保证。

计算复杂性

优化问题要求找出总价值最大的可行选择。其判定版本则询问,是否存在一种选择,同时满足

∑iwixi≤Wand∑ivixi≥V,\sum_i w_i x_i\leq W \quad\text{and}\quad \sum_i v_i x_i\geq V,

其中 VV 为目标价值。

对于以二进制编码的整数输入,这一判定问题具有NP完全性,而优化问题具有NP难性。给定一种选择,可以高效验证其是否满足要求,但目前尚无能在多项式时间内精确求解所有实例的算法。如果存在这样的算法,就能解决P与NP问题,证明 P=NPP=NP。

标准问题是弱NP完全的,这反映出它对数值大小的依赖。它存在一种伪多项式时间算法,其运行时间是 nn 和 WW 的多项式,但未必是二进制输入长度的多项式。表示 WW 只需要 O(log⁡W)O(\log W) 位,因此遍历从零到 WW 的所有容量,相对于这一表示的长度而言,可能需要指数级的步骤。

与之密切相关的子集和问题询问,能否从输入的数中选出若干个,使其和恰好等于目标值 BB。将每件物品的重量和价值都设为对应的输入数,将容量设为 BB,并要求总价值至少为 BB,就可以将其表述为背包问题。

精确算法

穷举搜索与折半搜索

枚举所有子集需要考察 2n2^n 种可能。这种方法只有在 nn 较小时才实用,不过剪枝可以减少某些实例中的计算量。

折半搜索算法将物品分成两组,分别枚举每组能够达到的重量—价值对。删除被支配的数对并排序后,再将两组中彼此兼容的选择组合起来。忽略多项式因子,其运行时间约为 O(2n/2)O(2^{n/2}),但需要较大的内存。

当物品数量适中,而容量过大、不适合建立以容量为索引的表时,这种方法很有用。

按容量进行动态规划

对于整数重量,动态规划提供了一种精确求解方法。定义 D(i,c)D(i,c) 为仅使用前 ii 件物品、容量为 cc 时能够获得的最大价值,则有

D(i,c)={D(i−1,c),wi>c,max⁡ ⁣(D(i−1,c), D(i−1,c−wi)+vi),wi≤c.D(i,c)= \begin{cases} D(i-1,c), & w_i>c,\\[4pt] \max\!\left(D(i-1,c),\,D(i-1,c-w_i)+v_i\right), & w_i\leq c. \end{cases}

边界条件为 D(0,c)=0D(0,c)=0,答案为 D(n,W)D(n,W)。

共有 O(nW)O(nW) 个状态,在通常的算术计算模型下,处理每个状态只需常数次操作。因此,时间复杂度为 O(nW)O(nW)。存储完整表格需要 O(nW)O(nW) 的空间;若只保留求最优值所需的信息,则可将空间复杂度降至 O(W)O(W)。

一维实现按降序更新容量:

dp[0 ... W] = 0
对于每件物品 i:
    令 c 从 W 递减至 w[i]:
        dp[c] = max(dp[c], dp[c - w[i]] + v[i])

降序更新可防止当前物品被重复使用。若改为按升序更新容量,就允许重复使用该物品,实现的便是相应的完全背包递推关系。

要还原所选物品,需要额外记录信息、保留表格,或使用重构过程;仅有最优值数组,并不能直接记录具体选择。

按价值进行动态规划

当价值为较小的整数而重量很大时,可以将这两个量的作用对调。设 M(i,p)M(i,p) 为使用前 ii 件物品、使总价值恰好为 pp 所需的最小重量。不可达状态的重量设为 +∞+\infty。

递推关系为

M(i,p)=min⁡ ⁣(M(i−1,p),M(i−1,p−vi)+wi),M(i,p)= \min\!\left( M(i-1,p), M(i-1,p-v_i)+w_i \right),

其中,当 p<vip<v_i 时省略第二项。答案是满足 M(n,p)≤WM(n,p)\leq W 的最大 pp。

若 P=∑iviP=\sum_i v_i,则基本算法的时间为 O(nP)O(nP)。这种表述也为通过缩放价值进行近似求解奠定了基础。

分支定界法与优化求解器

分支定界法在探索部分选择方案的同时,舍弃那些不可能改进当前最佳可行解的分支。求解分数松弛问题,可以给出某个分支所能达到的价值上界。

实用的整数规划求解器可能将这类界与预处理、割平面和专门的搜索方法结合使用。它们能够求解许多规模可观的实例,但性能高度依赖实例结构,并不能消除最坏情况下的复杂性。

近似算法

尽管精确优化具有NP难性,标准0–1背包问题仍然可以高效地进行近似求解。

一种简单的近似算法首先舍弃重量超过容量的物品,再将剩余物品按价值重量比排序。它取出排序序列中、首件会导致容量超限的物品之前的整件物品前缀,并将该前缀与价值最高的可行单件物品进行比较。两者中较好的选择,其价值至少为最优值的一半。

这一保证来自分数松弛:分数松弛的最优值,不超过上述前缀的价值加上首件无法完整装入的物品的全部价值。这两项分别不超过所比较的两个候选解的价值。

更进一步,0–1背包问题存在完全多项式时间近似方案,即完全多项式时间近似方案(FPTAS)。对于任意 0<ε<10<\varepsilon<1,它都能在关于输入长度和 1/ε1/\varepsilon 的多项式时间内,返回一个价值至少为

(1−ε)OPT⁡,(1-\varepsilon)\operatorname{OPT},

的可行解。

一种标准构造方法是:舍弃不可行的物品,令 Vmax⁡V_{\max} 为剩余物品中的最大价值,并设置

K=εVmax⁡n,v^i=⌊viK⌋.K=\frac{\varepsilon V_{\max}}{n}, \qquad \widehat v_i= \left\lfloor\frac{v_i}{K}\right\rfloor.

若所有可行物品的价值都为零,该实例便可直接求解。否则,用动态规划精确求解缩放价值后的实例。每件选中物品因取整而损失的价值小于 KK,因此总损失至多为

nK=εVmax⁡≤εOPT⁡.nK=\varepsilon V_{\max}\leq\varepsilon\operatorname{OPT}.

在标准算术计算模型下,一种直接实现的时间为 O(n3/ε)O(n^3/\varepsilon)。更先进的方案可以改进这一界。这些保证适用于标准的单约束问题,并不会自动延伸到其扩展形式。

应用与建模局限

背包模型出现在预算分配、货物选择、项目选择、存储管理和资源受限调度等领域。它们也会作为子问题,嵌入规模更大的优化方法中。

基本模型假设各件物品的价值可以独立相加,且资源消耗已知。它不能直接刻画某些相互作用,例如两个项目只有同时选中才有价值、未来成本存在不确定性,或优先级无法用单一数值目标表示等情形。依赖关系和多种资源都需要通过明确扩展模型来处理。

背包问题与装箱问题相关,但并不相同。背包问题通常是在有限容量下选择价值较高的物品子集;装箱问题则通常要求装入所有物品,同时尽量减少容器数量。

类似背包的问题也曾用于密码学。早期方案包括基于具有特定结构的子集和实例构建的公钥系统。一些著名的早期构造后来被攻破:一般背包实例的求解难度,并不能证明某种具有特定结构的密码构造是安全的。