多重背包
状态定义
(f[i,j]) 表示从前 (i) 类物品中选，且总容量不超过 (j) 的物品的最大价值
对于每一类物品 (i) 一共有 (s_{i} + 1) 种选法（(0,1,2,3,...,s_i)） ，选 (0) 个，选 (1) 个，选 (2) 个，(dots) ，选 (s_i) 个
我们在所有选法中求个最大值，就是状态定义的 (f[i,j]) ，（省略 (s_i,v_i,w_i) 的下角标 (i) ，重新定义一下待求的转移方程）
(f[i,j] = max(f[i - 1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,...,f[i-1,j-sv]+sw))
其中(f[i-1,j]) 从定义出发，表示从前 (i - 1) 类物品中选，且总容量不超过 (j) 的物品的最大价值
即(f[i-1,j]) 不包含第 (i) 类物品，对应选 (0) 个物品 (i)
(f[i-1,j-v] + w) ，表示从前 (i - 1) 类物品中选，且总容量不超过 (j-v) 的物品的最大价值
然后我们再把当前的物品 (w_i) 加入，就对应了，选 (1) 个物品 (i)
按照定义，依次类推，一直到物品 (i) 的上限 (s_i) 就不能选了
一般化，每次放入 (k) 个物品 (i) 时，总容量 (j) 都要先减去 (kv) 的体积，不然就放不下 (k) 个物品了，即 (f[i-1,j-kv] + kw)
| 最大价值 | 选 0 个物品 i | 选 1 个物品 i | 选 2 个物品 i | ... | 选 s 个物品 i |
|---|---|---|---|---|---|
| (f[i,j]) | (f[i-1,j]) | (f[i-1,j-v]+w) | (f[i-1,j-2v]+2w) | (dots) | (f[i-1,j-sv]+sw) |
以上就是多重背包的基本思路
https://www.acwing.com/problem/content/4/
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N],s[N],v[N],w[N];
int main() {
int n,m;
cin >> n >> m;
for(int i = 1;i <= n; ++i) cin >> v[i] >> w[i] >> s[i];
// 枚举物品
for(int i = 1;i <= n; ++i) {
// 枚举体积
for(int j = 0;j <= m; ++j) {
// 枚举选择的个数
for(int k = 0;k <= s[i] && k * v[i] <= j; ++k) {
f[i][j] = max(f[i][j],f[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
二进制优化
假设第 (k) 组物品一共有 (15) 个，按普通方法，需要枚举 (16) 次（(0,1,2,dots,15)），才能得到最大值
我们需要利用二进制，来优化这个枚举次数，思考 (15) 的二进制表示 (0000 1111) ，只需要用 (2^0,2^1,2^2,2^3) 就可以组合成 (0sim 15) 的数
也就是用二进制表示下的 (1) 来组合即可，最终枚举次数可以优化到 (log 15)
二进制枚举的原理 https://blog.csdn.net/sugarbliss/article/details/81099340
根据以上思想，我们可以把枚举这一步按二进制来优化，也就是二进制打包
把 (15) 个物品打包成 (1,2,4,8) 这四种物品，通过枚举这四类的组合，就可以得到原先需要枚举 (16) 才能得到的最大值
我们把所有物品都打包成二进制，物品的总数会变成 (N（i < N）)
(f[i,j]) 的结果就从这些二进制包里面进行选择，表示从前 (i) 类二进制包中选，且总容量不超过 (j) 的二进制包的最大价值
且对于每个二进制包来说，只有选 或者 不选两种情况，那么这个选择过程就变成了 (01) 背包
（原先是对于每个物品来说，可以选择 (0sim s_i) 种 ）
https://www.acwing.com/problem/content/description/5/
#include <bits/stdc++.h>
using namespace std;
const int N = 20100, M = 2010;
int w[N],v[N],cnt,f[M];
int main() {
int N,V;
cin >> N >> V;
for(int i = 1;i <= N; ++i) {
int a,b,c,k = 1;
// 体积，重量，个数
cin >> a >> b >> c;
// 按二进制拆分
while(k <= c) {
cnt ++;
v[cnt] = a * k;
w[cnt] = b * k;
c -= k;
k <<= 1;
}
if(c > 0) {
cnt ++;
v[cnt] = a * c;
w[cnt] = b * c;
}
}
// 更新 N 为拆分的二进制包裹
N = cnt;
// 01背包滚动优化
for(int i = 1;i <= N; ++i) {
for(int j = V;j >= v[i]; --j) {
f[j] = max(f[j],f[j - v[i]] + w[i]);
}
}
cout << f[V] << endl;
return 0;
}
单调队列优化
再看表达式
(f[i,j]=max (f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,dots,f[i-1][j-sv]+sw))
取 (j=j-v) 来替换上述式子得
(f[i,j-v]=max (f[i-1,j-v],f[i-1,j-2v]+w,f[i-1,j-3v]+2w,dots,f[i-1][j-(s+1)v]+sw))
取 (j=j-2v) 来替换上述式子得
(f[i,j-2v]=max (f[i-1,j-2v],f[i-1,j-3v]+w,f[i-1,j-4v]+2w,dots,f[i-1][j-(s+2)v]+sw))
取 (j=j-3v) 来替换上述式子得
(f[i,j-3v]=max (f[i-1,j-3v],f[i-1,j-4v]+w,f[i-1,j-5v]+2w,dots,f[i-1][j-(s+3)v]+sw))
观察式子发现，
求 (f[i,j] 只需要f[i-1,j] sim f[i-1,j-sv]+sw) 一共 (s + 1) 项
求 (f[i,j-v]) 只需要 (f[i-1,j-v] sim f[i-1,j-(s+1)v]+sw) 一共 (s+1) 项
考虑滑动窗口
图一
红色窗口向右移动，得到图二
少了 (f[i-1,j]) 多了一项(f[i-1,j-(s+1)v]+sw) ，同时，图二红框中的每一项，都比图一红框中的每一项少个 (w)
继续移动，注意，红框中始终有 (s+1) 项，省略号中有些项没有写出来
图三，同样比图二少个 (w) 并且，少一项 (f[i-1,j-v]) 多一项 (f[i-1,j-(s+2)v]+sw)
找到规律之后，可以使用单调队列来模拟这种滑动窗口，来迭代求 (f[i,j])
单调队列 https://blog.csdn.net/roufoo/article/details/78443281
因此，可以使用单调队列来优化多重背包，同时，我们发现，每次只会使用上一层的 (f[i,j]) 信息，所以可以使用两个一维数组来优化空间
https://www.acwing.com/problem/content/6/
#include <bits/stdc++.h>
using namespace std;
const int N = 20010;
int f[N],g[N],q[N];
// q 是队列，存的是 下标 k 的倍数
// 要取窗口内的最大值，所用队列为单调递减队列
int main() {
int n,m;
cin >> n >> m;
for(int i = 0;i < n; ++i) {
int v,w,s;
cin >> v >> w >> s;
memcpy(g,f,sizeof f);
for(int j = 0;j < v; j ++) {
int hh = 0,tt = -1;
// 单调队列
for(int k = j;k <= m; k += v) {
// 队头是否划出窗口，如果出去了，就弹出队列
// 队列维护的是一个不超过 s 个数的集合
// k-s*v为窗口左侧的位置，q[head]为队首元素（是坐标）
if(hh <= tt && q[hh] < k - s * v) hh ++;
while(hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt --;
// g 是上一层的值
// 判断队尾元素是否还有效
// 比较队尾元素对应的f值和当前下标k对应的f值
// 新入队列
q[ ++tt] = k;
// 若队列中有元素，取队首元素，是最大值，更新dp
f[k] = g[q[hh]] + (k - q[hh]) / v * w;
}
}
}
cout << f[m] << endl;
return 0;
}
代码注释参考