背包

发表于 分类于 阅读次数： Disqus： 本文字数： 735 阅读时长 ≈ 3 分钟

简介

背包问题是动态规划中基础但重要的一种问题，其内容可以描述为：

有\(n\)种物品和一个容量为\(W\)的背包，每种物品都有重量\(w_i\)和价值\(v_i\)两种属性，在所选物品不超过容量\(W\)的情况下，选择若干件物品放入背包使得总价值最大。

推荐阅读dd大佬的背包问题九讲。

0-1背包

这是最基础的背包问题，它的特点是：每种物品只有\(1\)件，我们只能选择放或不放。

设\(f_{i, j}\)表示只考虑前\(i\)件物品放入容量为\(j\)的背包的最大价值，可以得到状态转移方程： \[f_{i, j} = \max(f_{i - 1, j}, f_{i - 1, j - w_{i}} + v_{i})\] 已经放入了\(i - 1\)件物品之后，对于第\(i\)个物品，可以选择放或不放：
如果不放，那么背包剩余容量不变，总价值也不会变，因此总价值为\(f_{i - 1, j}\)；
如果放，那么背包的剩余容量会减小\(w_{i}\)，而总价值增加新放进去的\(v_{i}\)，因此总价值为\(f_{i - 1, j - w_{i}} + v_{i}\)。

考虑优化，我们可以去掉第一维，用新的\(f_{j}\)代替原先的\(f_{i - 1, j}\)，得出： \[f_{i} = \max(f_{i}, f_{i - w_{i}} + v_{i})\] 代码如下： 

1
2
3
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]);
注意，j的循环是逆序的。

例题

完全背包

完全背包和0-1背包的区别在于：每种物品可以选取无限次，而非只能选取一次。

完全背包的状态转移方程和上面一样： \[f_{i} = \max(f_{i}, f_{i - w_{i}} + v_{i})\] 但是循环要改成顺序的： 

1
2
3
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背包类似，它们的区别是：多重背包问题中每种物品可以选取\(k_{i}\)次。

对于多重背包问题，我们可以对每种物品的数量进行二进制拆分，当作是由\(2^{n}\)个单个物品捆绑成的大物品，然后用0-1背包的方法解决。例如：

  • \(7 = 1 + 2 + 4\)
  • \(13 = 1 + 2 + 4 + 6\)
  • \(16 = 1 + 2 + 4 + 8 + 1\)
  • \(31 = 1 + 2 + 4 + 8 + 16\)

代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for (int i = 1; i <= n; ++i) {
    int vi, wi, ki;
    scanf("%d %d %d", &vi, &wi, &ki);
    for (int j = 1; j <= ki; j <<= 1) {
        v[++tot] = j * vi;
        w[tot] = j * wi;
        ki -= j;
    }
    if (ki) {
        v[++tot] = ki * vi;
        w[tot] = ki * wi;
    }
}

for (int i = 1; i <= tot; ++i) {
    for (int j = W; j >= w[i]; --j) {
        f[j] = max(f[j], f[j - w[i]] + v[i]);
    }
}

例题