跳转至

背包 DP

在学习本章前请确认你已经学习了动态规划部分简介

在具体讲何为 “背包 dp” 前,先来看如下的例题

「USACO07 DEC」Charm Bracelet

题意概要:有 n个物品和一个容量为 W的背包,每个物品有重量 w_{i}和价值 v_{i}两种属性,要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

在上述例题中,由于每个物体只有 2种可能的状态(取与不取),正如二进制中的 01,这类问题便被称为 “0-1 背包问题”。

0-1 背包

例题中已知条件有第 i个物品的重量 w_{i},价值 v_{i},以及背包的总容量 W

设 DP 状态 f_{i,j}为在只能放前 i个物品的情况下,容量为 j的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 i-1个物品的所有状态,那么对于第 i个物品,当其不放入背包时,背包的剩余容量不变,背包中物品的总价值也不变,故这种情况的最大价值为 f_{i-1,j};当其放入背包时,背包的剩余容量会减小 w_{i},背包中物品的总价值会增大 v_{i},故这种情况的最大价值为 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-1},故可以去掉第一维,直接用 f_{j}来表示处理到当前物品 i时背包容量为 j的最大价值 f_{i,j}

还有一点需要注意的是,很容易写出这样的错误核心代码:

1
2
3
4
for (int i = 1; i <= W; i++)
  for (int l = 0; l <= W - i; l++)
    f[l + w[i]] = max(f[l] + v[i], f[l + w[i]]);
    // 由 f[i][l + w[i]] = max(max(f[i - 1][l + w[i]],f[i - 1][l] + w[i]),f[i][l + w[i]]); 简化而来

这段代码哪里错了呢?枚举顺序错了。

仔细观察代码可以发现:对于当前处理的物品 i和当前状态 f_{i,j},在 j\geqslant w_{i}时,f_{i,j}是会被 f_{i,j-w_{i}}所影响的。这就相当于物品 i可以多次被放入背包,与题意不符。(事实上,这正是完全背包问题的解法)

为了避免这种情况发生,我们可以改变枚举的顺序,从 W枚举到 w_{i},这样就不会出现上述的错误,因为 f_{i,j}总是在 f_{i,j-w_{i}}前被更新。

因此实际核心代码为

1
2
3
4
for (int i = 1; i <= W; i++)
  for (int l = W - i; l >= 0; l--)
    f[l + i] = max(f[l] + w[i], f[l + i]);
    // 由 f[i][l + w[i]] = max(max(f[i - 1][l + w[i]],f[i - 1][l] + w[i]),f[i][l + w[i]]); 简化而来
例题代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>
const int maxn = 13010;
int n, v, w[maxn], v[maxn], f[maxn];
int main() {
    std::cin >> n >> W;
    for (int i = 1; i <= n; i++)
        std::cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i++)
        for (int l = W; l >= w[i]; l--)
            if (f[l - w[i]] + v[i] > f[l])
                f[l] = f[l - w[i]] + v[i];
    std::cout << f[W];
    return 0;
}

完全背包

完全背包模型与 0-1 背包类似,与 0-1 背包的区别仅在于一个物品可以选取无限次,而非仅能选取一次。

我们可以借鉴 0-1 背包的思路,进行状态定义:设 f_{i,j}为只能选前 i个物品时,容量为 j的背包可以达到的最大价值。

需要注意的是,虽然定义与 0-1 背包类似,但是其状态转移方程与 0-1 背包并不相同。

可以考虑一个朴素的做法:对于第 i件物品,枚举其选了多少个来转移。这样做的时间复杂度是 O(n^3)的。

尽管这样看起来很蠢,我们还是写一下 dp 方程:

f_{i,j}=\max_{k=0}^{+\infty}(f_{i-1,j-k\times w_i}+v_i\times k)

然而这样显然不够优秀,我们要对它进行优化。

可以发现,对于 f_{i,j},只要通过 f_{i,j-w_i}转移就可以了。dp 方程为:

f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)

理由是当我们这样转移时,f_{i,j-w_i}已经由 f_{i,j-2\times w_i}更新过,那么 f_{i,j-w_i}就是充分考虑了第 i件物品所选次数后得到的最优结果。换言之,我们通过局部最优子结构的性质重复使用了之前的枚举过程,优化了枚举的复杂度。

与 0-1 背包相同地,我们可以将第一维去掉来优化空间复杂度。如果理解了 0-1 背包的优化方式,就不难明白压缩后的循环是正向的(也就是上文中提到的错误优化)。

「Luogu P1616」疯狂的采药

题意概要:有 n种物品和一个容量为 W的背包,每种物品有重量 w_{i}和价值 v_{i}两种属性,要求选若干个物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

例题代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>
const int maxn = 13010;
int n, v, w[maxn], v[maxn], f[maxn];
int main() {
    std::cin >> n >> W;
    for (int i = 1; i <= n; i++)
        std::cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i++)
        for (int l = w[i]; l <= W; l++)
            if (f[l - w[i]] + v[i] > f[l])
                f[l] = f[l - w[i]] + v[i];
    std::cout << f[W];
    return 0;
}

多重背包

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品可以选 k_i次,而非 1次。

一个很朴素的想法就是:把“每种物品选 k_i次”等价转换为“有 k_i个相同的物品,每个物品选一次”。这样就转换成了一个 0-1 背包模型,套用上文所述的方法就可已解决。时间复杂度:O(nW\sum k_i),可以轻松 TLE。

虽然我们失败了,但是这个朴素的想法可以给我们的思路提供一些借鉴——我们可以把多重背包转化成 0-1 背包模型来求解。

显然,复杂度中的 O(nW)部分无法再优化了,我们只能从 O(\sum k_i)处入手。

为了表述方便,我们用 A_{i,j}代表第 i种物品拆分出的第 j个物品。

在朴素的做法中,\forall j\le k_iA_{i,j}均表示相同物品。那么我们效率低的原因主要在于我们进行了大量重复性的工作。举例来说,我们考虑了 “同时选A_{i,1},A_{i,2}” 与 “同时选 A_{i,2},A_{i,3}” 这两个完全等效的情况。这样的重复性工作我们进行了许多次。那么优化拆分方式就成为了解决问题的突破口。

我们可以通过“二进制分组”的方式使拆分方式更加优美。

具体地说就是令 A_{i,j}\left(j\in\left[0,\lfloor \log_2(k_i+1)\rfloor-1\right]\right)分别表示由 2^{j}个单个物品“捆绑”而成的大物品。特殊地,若 k_i+1不是 2的整数次幂,则需要在最后添加一个由 k_i-2^{\lfloor \log_2(k_i+1)\rfloor-1}个单个物品“捆绑”而成的大物品用于补足。

举几个例子:

  • 6=1+2+3
  • 8=1+2+4+1
  • 18=1+2+4+8+3
  • 31=1+2+4+8+16

显然,通过上述拆分方式,可以表示任意 \le k_i个物品的等效选择方式。将每种物品按照上述方式拆分后,使用 0-1 背包的方法解决即可。

时间复杂度 O(nW\sum\log k_i)

二进制分组代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    index = 0;
    for(int i = 1; i <= m; i++) {
        int c = 1, p, h, k;
        cin >> p >> h >> k;
        while(k - c > 0) {
            k -= c;
            list[++index].w = c * p;
            list[index].v = c * h;
            c *= 2;
        }
        list[++index].w = p * k; 
        list[index].v = h * k;
    }

评论