AcWing
4. 多重背包问题I
定义两维状态数组f[N][M]表示考虑前n种物品，背包容量为m时的最大价值。
可以将f[n][m]分为以下若干个集合(n, m从1开始编号，为了将0作为特殊边界)：
- 取
0个第i种物品 - 取
1个第i种物品 - ……
- 取
k个第i种物品 - ……
保证将f[n][m]分为这些集合之后不重不漏。则对于普遍的f[n][m]，其值为这些方案价值的最大值，有:
f[n][m] = max{f[n - 1][m], f[n - 1][m - v[i]] + w[i], f[n - 1][m - 2v[i]] + 2w[i], ...}
考虑边界条件，f[0][i] = 0，即当不考虑任何一种物品，背包中物品的价值为0.
类似于01背包，对空间进行优化，第二维循环(容量)从大到小，表示每种物品只有选或不选两种。
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 110, M = 110;
int v[N], w[N], s[N];
int f[M];
int main(){
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 = m; j >= v[i]; j--){
for(int k = 1; k <= s[i] && k * v[i] <= j; k++){
f[j] = max(f[j], f[j - v[i] * k] + w[i] * k);
}
}
}
cout << f[m] << endl;
return 0;
}
还有一种思路是，将每种s[i]个物品拆开，那么总物品数是s[1] + s[2] + ... + s[n]，这样就将多重背包问题转换为01背包问题。
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 110, M = 110;
int v[N], w[N], s[N];
int f[M];
int main(){
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 k = 1; k <= s[i]; k++){
for(int j = m; j >= v[i]; j--){
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
}
cout << f[m] << endl;
return 0;
}