背包问题

总结自《背包九讲》

01背包

有 $N$ 种物品,每种物品只有一件,第 $i$ 件物品的体积是 $c_i$,价值是 $w_i$。你现在有一个容量为 $V$ 的背包,求解将这些物品装入背包可获得的最大价值。

思想

$dp[i][j]$: 表示前 $i$ 件物品中选若干件,放入容量为 $j$ 的背包中,可获得的最大价值。

考虑第i件物品放或不放,那么转移就是:

$$dp[i][j] = Max(dp[i-1][j], dp[i-1][j-c_i] + w_i)$$

优化1

因为我们发现当前状态只和上一个状态相关,因此第一维实际上只要存 $2$ 个数即可。

优化2

我们通过转移的顺序发现,如果我们倒过来进行转移,只需要一维即可。

初始化问题

如果是恰好装满, 那么 $dp[0][i]$ 都要初始化为 $0$, 而其他都要初始化为负无穷。

如果是不必装满,那么 $dp[0][i]$ 要初始化为 $0$, 其他的会在转移的时候计算,不需要初始化。

变形

容量和价值换一换,$dp[i][j]$:表示前i件物品,价值为j的最小容量。

一样做。

可达性背包

问 $N$ 种物品,每种物品只有一件,你有一个容量为 $V$ 的背包,问可以组成的价值的种类数。

需要用 $bitset$ 优化。

$bitset$ 中的每一位表示这个价值是否能达到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bitset<maxn> bt[2][maxn];

for (int j = 0; j <= V; j++) {
bt[0][j].reset();
bt[1][j].reset();
}
for (int i = 1; i <= N; i++) {
int id = i & 1;
for (int j = 0; j <= V; j++) {
if (j < c[i])
bt[id][j] = bt[id ^ 1][j];
else
bt[id][j] |= bt[id ^ 1][j - c[i]].set(w[i]);
}
}
cout << bt[N & 1][V].count() << endl;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 恰好装满
clr(dp,0xc0); // 初始化负无穷
clr(dp[0],0);
for (int i = 1; i <= N; i++) {
for (int j = c[i]; j <= V; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
}
}
// 不必装满
clr(dp[0], 0);
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
if (j < c[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
}
}

// 优化1
clr(dp[0], 0);
for (int i = 1; i <= N; i++) {
int id = i & 1;
for (int j = 0; j <= V; j++) {
if (j < c[i])
dp[id][j] = dp[id ^ 1][j];
else
dp[id][j] = max(dp[id ^ 1][j], dp[id ^ 1][j - c[i]] + w[i]);
}
}
cout << dp[N & 1][V] << endl;

// 优化2
clr(dp, 0);
for (int i = 1; i <= N; i++) {
for (int j = V; j >= c[i]; j++) {
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
}
}
cout << dp[V] << endl;

完全背包

有 $N$ 种物品和一个容量为 $V$ 的背包,每种物品都有无限个。第 $i$ 种物品的的体积是 $c_i$,价值是 $w_i$。

求解将这些物品装入背包可获得的最大价值。

思想

它和01背包类似,但又不完全相同。

$dp[i][j]$ 表示前 $i$ 个物品,装入容量为 $j$ 的背包可获得的最大价值。

它的转移可能是由 $dp[i-1][j - k \times c_i] + k \times w_i$ 转移过来的, 如果去枚举 $k$ ,那么复杂度必定爆炸。

换一种转移:$dp[i][j] = max(dp[i][j-c_i] + w_i, dp[i-1][j])$

观察转移式,我们可以继续优化:$dp[j] = Max(dp[j], dp[j-c_i]+w_i)$

代码

1
2
3
4
5
6
clr(dp, 0);
for (int i = 1; i <= N; i++) {
for (int j = c[i]; j <= V; j++) {
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
}
}

多重背包

有 $N$ 种物品和一个容量为 $V$ 的背包,第 $i$ 种物品有 $m_i$ 件可用,第 $i$ 种物品的体积是 $c_i$,价值是 $w_i$。

求背包能装下的最大价值。

思想

通过拆分每种物品,使其变成 $01$ 背包。

假如某种物品有 $k$ 件, 那么可以拆分成: $2^0, 2^1, 2^2… 2^t, k - 2^t$ 这么多种新的物品。

然后做 $01$ 背包即可。

复杂度 $O(NVlog(M))$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int _N = 0;
for (int i = 1; i <= N; i++) { // 拆分
for (int j = 0;; j++) {
if (m[i] > (1 << j)) {
m[i] -= (1 << j);
_c[_N] = (1 << j) * c[i];
_w[_N] = (1 << j) * w[i];
_N++;
} else
break;
}
_c[_N] = m[i] * c[i];
_w[_N] = m[i] * w[i];
_N++;
}
clr(dp, 0);
for (int i = 1; i < _N; i++) { // 01背包
for (int j = V; j >= _c[i]; j++) {
dp[j] = max(dp[j], dp[j - _c[i]] + _w[i]);
}
}

可行性问题

若问题变为:是否能填满容量为 $V$ 的背包。 则就变成了可行性问题,是可以 $O(VN)$ 解出的。

$dp[i][j]$ 表示前 $i$ 种物品,填满容量为 $j$ 的背包后,第 $i$ 种物品的剩余数量

$dp[i][j] = -1$ 表示不可行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
clr(dp[0], -1);
dp[0][0] = 0;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
if (dp[i - 1][j] >= 0)
dp[i][j] = m[i];
else
dp[i][j] = -1;
}
for (int j = 0; j <= V - c[i]; j++) {
if (dp[i][j] > 0)
dp[i][j + c[i]] = max(dp[i][j + c[i]], dp[i][j] - 1);
}
}

混合背包

有 $N$ 种物品和一个容量为 $V$ 的背包, 每种物品,有的只有一件,有的有多件,有的有无限件。

求能装下的最大价值。

思想

多重背包可以通过拆分变成 $01$ 背包,那么最后问题实际上就是 $01$ 背包和无限背包的混合。

1
2
3
4
5
6
7
for i = 1 : n
if i 为01背包
for j = V : c[i]
dp[j] = max(dp[j], dp[j-c[i]] + w[i]);
if i 为无限背包
for j = c[i] : V
dp[j] = max(dp[j], dp[j-c[i]] + w[i]);

分组背包

有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的体积是 $c_i$,价值是 $w_i$。这些物品被划分为 $K$ 组,每组中的物品互相冲突,最多选一件

求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。

思想

$dp[i][j]$:表示用前 $i$ 组的物品填容量为 $j$ 的背包,能得到的的最大价值。

那么对于每组来说,就有选一件或者不选两种决策。

时间复杂度 $O(VN)$

1
2
3
4
5
for k = 1 : K
for j = V : 0
for item in k
if(j >= c[item])
dp[j] = max(dp[j], dp[j - c[item]] + w[item]);

依赖背包

每个物品都有依赖关系,如果 $i$ 依赖于 $j$,那么要买 $i$ 物品,必须先买 $j$ 物品。

限制条件: 每个物品最多只能依赖一件物品;没有循环依赖。

称每个有依赖的为附件,没有依赖的为主件。

思想

先考虑简化版,即每个附件都没有附件。

那么对于每个主件所在的物品集合里,我们可以先跑一次01背包,得到每个费用可得到的最大价值。然后把每个$(cost, val), c_i \leq cost \leq V $ 看作一个新的物品。这样问题就转化成了分组背包。

再考虑普通版,即每个附件也可能存在附件。

解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。
唯一不同的是,由于附件可能还有附件,就不能将每个附件都看作一个一般的 01 背包中的物品
了。
若这个附件也有附件集合,则它必定要被先转化为物品组,
然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。

事实上,这是一种树形动态规划,其特点是,在用动态规划求每个父节点的属性之前,需要对它的各个儿子的属性进行一次动态规划式的求值。