多重背包

出自《背包九讲》

问题

有$N$种物品和一个容量为$V$的背包,第$i$种物品有$m_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);
}
}
Thank you for your support!