背包

发表于 | 分类于 | | 阅读次数:
字数统计: 753 | 阅读时长 ≈ 3

简介

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

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

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

0-1背包

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

设$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_{j}$代替原先的$f_{i - 1, j}$，得出：

代码如下：

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背包的区别在于：
每种物品可以选取无限次，而非只能选取一次。

完全背包的状态转移方程和上面一样：

但是循环要改成顺序的：

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]);
    }
}

例题

0%