|
|
##[$AcWing$ $5$. 多重背包问题 II](https://www.acwing.com/problem/content/description/5/)
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
有 $N$ 种物品和一个容量是 $V$ 的背包。
|
|
|
|
|
|
第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。
|
|
|
|
|
|
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出**最大价值**。
|
|
|
|
|
|
**输入格式**
|
|
|
第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。
|
|
|
|
|
|
接下来有 $N$ 行，每行三个整数 $v_i,w_i,s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。
|
|
|
|
|
|
**输出格式**
|
|
|
输出一个整数，表示最大价值。
|
|
|
|
|
|
**数据范围**
|
|
|
$0<N≤1000$
|
|
|
$0<V≤2000$
|
|
|
$0<v_i,w_i,s_i≤2000$
|
|
|
|
|
|
**提示**：
|
|
|
本题考查多重背包的二进制优化方法。
|
|
|
|
|
|
**输入样例**
|
|
|
```cpp {.line-numbers}
|
|
|
4 5
|
|
|
1 2 3
|
|
|
2 4 1
|
|
|
3 4 3
|
|
|
4 5 2
|
|
|
```
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
10
|
|
|
```
|
|
|
|
|
|
### 二、与 多重背包问题 $I$ 的区别
|
|
|
区别在于数据范围变大了：现在是三个循环数据上限分别是$1000$(物品种数),$2000$(背包容积),第$i$种物品的体积、价值和数量的上限也是$2000$,原来的每个数字上限都是$100$！
|
|
|
|
|
|
解法$I$使用的是三重循环，计算次数就是 $1000 * 2000 * 2000=4000000000=4 * 1e9 =40$亿次
|
|
|
|
|
|
$C++$一秒可以算$1e8$次，就是$1$亿次，$40$亿肯定会超时!
|
|
|
|
|
|
### 三、二进制优化
|
|
|
|
|
|
**$Q$:怎么来优化呢？**
|
|
|
答：我们先来思考一下为什么方法一的速度慢,因为三层循环:
|
|
|
① 第一层遍历每个物品
|
|
|
② 第二层遍历每个可用的空间
|
|
|
③ 第三层枚举当前物品使用了几个
|
|
|
|
|
|
**$Q$:我们最终的目标是什么?**
|
|
|
答：每个物品选择了几个才是最优的，价值最大的。
|
|
|
|
|
|
**办法**
|
|
|
**用二进制思想把所有可能的组合都表示出来，转化为$01$背包问题！**
|
|
|
|
|
|
假如$A$物品，有$10$个，你最后要几个不一定，可能是$0$个，$1$个,$2$个，....，$10$个。
|
|
|
|
|
|
我们可以这样打包：
|
|
|
|
|
|
|
|
|
|
|
|
上面这样的转化，就是把一个个尝试，转化为了成批说事，比如上面圆圈里的$4$，理解为$i$物品$4$个打成一包,体积是原来的$4$倍，价值也是原来的$4$倍。这个打包完成的新物品，你可以选择，也可以不选择，当你最终方案中$i$物品要了$5$个时，这个打包$4$就被选中了，当你最终方案中$i$物品要了$2$个时，这个打包$4$就被放弃了。
|
|
|
|
|
|
打包，就是成批讨论，避免了一个个讨论，组团，按$yxc$的说法就是集合，不管怎么样吧，二进制打包法将极大加快计算速度！理由：比如$INT\_MAX$,其实就是$2^{31}$,也就是划分成了最多$31$个包，能不快吗！就是打包费点劲。
|
|
|
|
|
|
### 三、一维实现代码 <font color='red' size=4><b>【推荐】</b></font>
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 1010; // 个数上限
|
|
|
const int M = 2010; // 体积上限
|
|
|
int n, m, idx;
|
|
|
int f[M];
|
|
|
|
|
|
/*
|
|
|
Q:为什么是N*12?
|
|
|
A:本题中v_i<=2000,因为c数组是装的打包后的物品集合，每类物品按二进制思想，2000最多可以打log2(2000)+1个包，即 10.96578+1=12个足够,
|
|
|
同时，共N类物品，所以最大值是N*12。
|
|
|
|
|
|
如果题目要求v_i<=INT_MAX,那么就是log2(INT_MAX)=31,开31个足够,因为31是准确的数字，不需要再上取整。
|
|
|
为保险起见，可以不用计算数组上限，直接N*32搞定！
|
|
|
*/
|
|
|
struct Node {
|
|
|
int w, v;
|
|
|
} c[N * 12];
|
|
|
|
|
|
int main() {
|
|
|
cin >> n >> m;
|
|
|
|
|
|
// 多重背包的经典二进制打包办法
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
int v, w, s;
|
|
|
cin >> v >> w >> s;
|
|
|
for (int j = 1; j <= s; j *= 2) { // 1,2,4,8,16,32,64,128,...打包
|
|
|
c[++idx] = {j * w, j * v};
|
|
|
s -= j;
|
|
|
}
|
|
|
// 不够下一个2^n时，独立成包
|
|
|
if (s) c[++idx] = {s * w, s * v};
|
|
|
}
|
|
|
// 按01背包跑
|
|
|
for (int i = 1; i <= idx; i++)
|
|
|
for (int j = m; j >= c[i].v; j--) // 倒序
|
|
|
f[j] = max(f[j], f[j - c[i].v] + c[i].w);
|
|
|
// 输出
|
|
|
printf("%d\n", f[m]);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 四、二维+滚动数组代码
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 1010; // 个数上限
|
|
|
const int M = 2010; // 体积上限
|
|
|
int n, m, idx;
|
|
|
// 无法使用二维数组，原因是因为分拆后N*31*M=31*1010*2010太大了，MLE了
|
|
|
// 所以，需要使用滚动数组进行优化一下，思想还是二维的
|
|
|
int f[2][M];
|
|
|
|
|
|
struct Node {
|
|
|
int w, v;
|
|
|
} c[N * 31];
|
|
|
|
|
|
int main() {
|
|
|
cin >> n >> m;
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
int v, w, s;
|
|
|
cin >> v >> w >> s;
|
|
|
for (int j = 1; j <= s; j *= 2) { // 1,2,4,8,16,32,64,128,...打包
|
|
|
c[++idx] = {j * w, j * v};
|
|
|
s -= j;
|
|
|
}
|
|
|
// 不够下一个2^n时，独立成包
|
|
|
if (s) c[++idx] = {s * w, s * v};
|
|
|
}
|
|
|
|
|
|
// 按01背包跑就可以啦
|
|
|
for (int i = 1; i <= idx; i++)
|
|
|
for (int j = 1; j <= m; j++) {
|
|
|
f[i & 1][j] = f[i - 1 & 1][j];
|
|
|
if (j >= c[i].v)
|
|
|
f[i & 1][j] = max(f[i & 1][j], f[i - 1 & 1][j - c[i].v] + c[i].w);
|
|
|
}
|
|
|
|
|
|
// 输出
|
|
|
printf("%d\n", f[idx & 1][m]);
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
