简介
背包问题 (英语:Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中,背包的空间有限,但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中,决策者必须分别从一组不可分割的项目或任务中进行选择,而这些项目又有时间或预算的限制。
背包问题历史悠久,甚至可以追溯到1897年。“背包问题” 一词最早出现于数学家托比阿斯·丹齐格的早期研究中,他研究的问题是如何打包行李,要求最大化所选行李的价值且不能超载。
背包问题出现在现实世界很多领域的决策过程中,诸如寻找节约原料的生产方式、选择投资项目及投资组合、选择证券化的资产以及为默克尔-赫尔曼和其他背包密码系统生成密钥。
背包问题中基础的大致分为一下几类:
0-1背包
解释
例题中已知条件有第 i i i 个物品的重量 w i w_i w i ,价值 v i v_i v i ,以及背包的总容量 W W W 。
设 DP 状态 f i , j f_{ i , j } f i , j 为在只能放前 i i i 个物品的情况下,容量为 j j j 的背包所能达到的最大总价值。
考虑转移。假设当前已经处理好了前 i − 1 i-1 i − 1 个物品的所有状态,那么对于第 i 个物品,当其不放入
背包时,背包的剩余容量不变,背包中物品的总价值也不变,故这种情况的最大价值为 f i − 1 , j f_{i-1, j} f i − 1 , j ;当
其放入背包时,背包的剩余容量会减小 w i w_i w i ,背包中物品的总价值会增大 v i v_i v i ,故这种情况的最大价
值为 f i − 1 , j − w i + v i f_{i-1,j-w_{i}} + v_i f i − 1 , j − w i + v i 。由此可以得出状态转移方程:
f i , j = m a x ( f i − 1 , j , f i − 1 , j − w i + v i ) f_{i,j}= max(f_{i-1,j},f_{i-1,j-w_{i}}+ v_i)
f i , j = ma x ( f i − 1 , j , f i − 1 , j − w i + v i )
这里如果直接采用二维数组对状态进行记录,会出现 MLE。可以考虑改用滚动数组的形式来优
化。(将二维数组优化写成一维数组)
由于对 f i f_i f i 有影响的只有 f i − 1 f_{i-1} f i − 1 ,可以去掉第一维,直接用 f i f_i f i 来表示处理到当前物品时背包容量为 i i i
的最大价值,得出以下方程:
f j = m a x ( f j , f j − w i + v i ) f_j=max(f_j, f_{j-w_{i}} + v_i)
f j = ma x ( f j , f j − w i + v i )
核心代码:
1 2 3 4 5 6 7 for (int i = 1 ; i <= n; i++) { for (int j = W; j >= w[i]; j--) { f[j] = max (f[j], f[j - w[i]] + v[i]); } }
需要注意的是,第二个循环的枚举的顺序是从 W W W 枚举到 w i w_i w i 。为什么呢?
如果从 w i w_i w i 枚举到 W W W 在 j > w i j>w_i j > w i 时,f i , j f_{i,j} f i , j 是会被 f i , j − w i f_{i,j-w_{i}} f i , j − w i 所影响的,如果前面 f i , j − w i f_{i,j-w_{i}} f i , j − w i 放入物品 i i i 是价值更大,我们会将其放入并更新,在后面 f i , j f_{i,j} f i , j 时如果再次选择放入会用到 f i , j f_{i,j} f i , j 这就相当于物品 i i i 可以多次被放入背包,与题意不符。(事实上,这正是完全背包问题的解法)。
如果二维 DP 不会爆 MLE 我们也可以用二维 DP 来处理,此时第二个循环的枚举顺序不影响结果,因为对于任意的 f i , j f_{i,j} f i , j 并不会修改 f i − 1 , j f_{i-1,j} f i − 1 , j 或者 f i − 1 , j − w i f_{i-1,j-w_{i}} f i − 1 , j − w i 的结果。代码如下:
1 2 3 4 5 6 7 for (int i = 1 ; i <= n; i++) { for (int j = W; j >= w[i]; j--) { f[i][j] = max (f[i - 1 ][j], f[i - 1 ][j - w[i]] + v[i]); } }
完全背包
解释
完全背包模型与 0-1背包 类似,与 0-1背包 的区别仅在于一个物品可以选取无限次.。
我们可以借鉴 0-1背包的思路,进行状态定义:设 f i , j f_{i,j} f i , j 为只能选前 i i i 个物品时,容量为 j j j 的背包可
以达到的最大价值。
可以考虑一个朴素的做法:对于第 i i i 件物品,枚举其选了多少个来转移。这样做的时间复杂度是
O ( n 3 ) O(n^3) O ( n 3 ) 的。状态转移方程如下:
f i , j = max k = 0 + ∞ ( f i − 1 , j − k ∗ w i + v i ∗ k ) f_{i,j} = \max_{k=0}^{+\infty}(f_{i-1,j-k*w_{i}}+v_{i}*k)
f i , j = k = 0 max + ∞ ( f i − 1 , j − k ∗ w i + v i ∗ k )
考虑做一个简单的优化。可以发现,对于 f i , j f_{i,j} f i , j ,只要通过 f i , j − w i + v i f_{i,j-w_{i}}+v_{i} f i , j − w i + v i 转移就可以了。当我们这样转移时,f i , j − w i f_{i,j-w_{i}} f i , j − w i 已经由 f i , j − 2 ∗ w i f_{i,j-2*w_{i}} f i , j − 2 ∗ w i 更新过,那么 f i , j − w i f_{i,j-w_{i}} f i , j − w i 就是充分考虑了第i件物品
所选次数后得到的最优结果。换言之,我们通过局部最优子结构的性质重复使用了之前的枚举过
程,优化了枚举的复杂度。因此状态转移方程为:
f i , j = m a x ( f i − 1 , j , f i − 1 , j − w i + v i ) f_{i,j}= max(f_{i-1,j}, f_{i-1,j-w_{i}}+ v_i)
f i , j = ma x ( f i − 1 , j , f i − 1 , j − w i + v i )
与 0-1背包相同,我们可以将第一维去掉来优化空间复杂度。
核心代码:
1 2 3 4 5 6 7 for (int i = 1 ; i <= n; i++) { for (int j = w[i]; j >= W; j--) { f[j] = max (f[j], f[j - w[i]] + v[i]); } }
多重背包
解释
多重背包是 0-1背包的一个变式。与 0-1背包的区别在于每种物品有 k i k_i k i 个,而非一个。
一个很朴素的想法就是:我们把 k i k_i k i 个相同的物品看成 k i k_i k i 个重量价值相同但是不同的物品,即对 ∑ i = 1 n k i \sum_{i=1}^{n} k_{i} ∑ i = 1 n k i 个物品做 0-1背包。
时间复杂度 O ( W ∑ i = 1 n k i ) O(W \sum_{i=1}^{n} k_{i}) O ( W ∑ i = 1 n k i ) 。
核心代码:
1 2 3 4 5 6 7 8 9 10 11 for (int i = 1 ; i <= n; i++) { for (int weight = W; weight >= w[i]; weight--) { for (int k = 1 ; k * w[i] <= weight && k <= cnt[i]; k++) { dp[weight] = max (dp[weight], dp[weight - k * w[i]] + k * v[i]); } } }
二进制分组优化
显然,复杂度中的 O ( n W ) O(nW) O ( nW ) 部分无法再优化了,我们只能从 O ( ∑ i = 1 n k i ) O(\sum_{i=1}^{n} k_{i}) O ( ∑ i = 1 n k i ) 处入手。
为了表述方便,我们用 A i , j A_{i,j} A i , j 代表第 i i i 种物品拆分出的第 j j j 个物品。
在朴素的做法中,∀ j ≤ k i \forall j \le ki ∀ j ≤ ki ,A i , j A_{i,j} A i , j 均表示相同物品。那么我们效率低的原因主要在于我们进行了大量的重复性的工作。举例来说,我们考虑了同时选 A i , 1 A_{i,1} A i , 1 ,A i , 2 A_{i,2} A i , 2 与同时选 A i , 2 A_{i,2} A i , 2 ,A i , 3 A_{i,3} A i , 3 这两个完全等效的情况。这样的重复性工作我们进行了许多次。那么优化拆分方式就成为了解决问题的突破口。
我们可以通过二进制分组 的方式使拆分方式更加优美。
具体地说就是令 A i , j , ( j ∈ [ 0 , ⌊ l o g 2 ( k i + 1 ) ⌋ − 1 ] ) A_{i,j},(j\in [0,\lfloor log_2(k_i+ 1) \rfloor - 1]) A i , j , ( j ∈ [ 0 , ⌊ l o g 2 ( k i + 1 )⌋ − 1 ]) 分别表示由 2 j 2^j 2 j 个单个物品捆绑而成的大物
品。特殊地,若 k i + 1 ki+1 ki + 1 不是 2 2 2 的整数次幂,则需要在最后添加一个由 k i − 2 ⌊ l o g 2 ( k i + 1 ) ⌋ − 1 k_i-2^{\lfloor log_2(k_i+ 1) \rfloor - 1} k i − 2 ⌊ l o g 2 ( k i + 1 )⌋ − 1 个单个物品捆绑而成的大物品用于补足。
例如:
8=1+2+4+1
18=1+2+4+8+3
31=1+2+4+8+16
显然,通过上述拆分方式,可以表示任意 ≤ k i \le k_i ≤ k i 个物品的等效选择方式。将每种物品按照上述方式
拆分后,使用 0-1背包的方法解决即可。
时间复杂度 O ( W ∑ i = 1 n l o g 2 k i ) O(W\sum_{i=1}^{n} log_2k_{i}) O ( W ∑ i = 1 n l o g 2 k i ) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 index = 0 ;for (int i = 1 ; i <= m; i++) { int c = 1 , p, h, k; cin >> p >> h >> k; while (k > c) { k -= c; list[++index].w = c * p; list[index].v = c * h; c *= 2 ; } list[++index].w = p * k; list[index].v = h * k; }
分组背包
解释
有 i i i 件物品和一个大小为 m m m 的背包,第 i i i 个物品的价值为 v i v_i v i ,体积为 w i w_i w i 。同时,每个物品只属于一个组,同组内最多只能选择一个物品,求背包能装载物品的最大总价值。
其实是从在所有物品中选择一件变成了从当前组中选择一件,于是就对每一组进行一次 0-1 背包就可以了,再说一说如何进行存储。我们可以将t表示第k组的第i件物品的编号是多少,再用 c n t cnt c n t 表示第 k k k 组物品有多少个。
核心代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 for (int k = 1 ; k <= ts; k++) { for (int i = m; i >= 0 ; i--) { for (int j = 1 ; j <= cnt[k]; j++) { if (i >= w[t[k][j]]) { dp[i] = max (dp[i],dp[i - w[t[k][j]]] + c[t[k][j]]); } } } }
混合背包
解释
混合背包是 0-1背包、完全背包以及多重背包的组合,会出现其中的几种背包。有些可以无限取,有些物品只可以取有限次。
把不同情况分开:
能无限选 → 按完全背包处理。
选择次数有限 → 按多重(0-1)背包处理。
分情况分别解决,最后合并即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 for (int i = 1 ; i <= n; i++) { if (是 0 - 1 背包) { } else if (是完全背包) { } else if (是多重背包) { } }
前言 · 背包问题九讲 · 看云 (kancloud.cn)