多重背包问题

样题：

 数据范围比较小时（小于1000）：

 类似于01背包，加个循环即可

#include <bits/stdc++.h>
using namespace std;const int N = 1010;
int f[N],w[N],v[N],s[N];int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,V; cin >> n >> V;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];for(int i = 1; i <= n; i++){for(int j = V; j >= v[i]; j--){for(int k = 0; k <= s[i]; k++){if(j >= k * v[i])f[j] = max(f[j],f[j - k * v[i]] + k * w[i]);}}}cout << f[V];return 0;
}

 数据范围比较大时：

进行二进制优化

二进制优化的基本原理

二进制优化的核心思想是将每个物品的数量S拆分为若干个数量为2^k的物品（其中k为非负整数），这样可以用较少的物品来表示原始物品的所有可能数量。这种方法的好处在于：

• 减少物品数量：将一个物品拆分为log(S)个物品，从而减少需要处理的物品总数。
• 覆盖所有组合：通过组合这些二进制拆分的物品，可以表示原始物品的任意数量选择。

具体拆分方法

假设有一个物品，其数量限制为S，拆分过程如下：

1. 找到最大的k使得2^k ≤ S。
2. 将该物品拆分为数量为2^0, 2^1, 2^2, ..., 2^k的多个子物品。
3. 如果S不能被2^(k+1) - 1整除，则将剩余的S - (2^0 + 2^1 + ... + 2^k)作为最后一个子物品。

例如，若S = 13：

• 拆分为1, 2, 4, 6（因为1 + 2 + 4 + 6 = 13）。

#include <bits/stdc++.h>
using namespace std;
// N * logS 是新的N的值
const int N = 25000,M = 2010;
int f[N],w[N],v[N],s[N];int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,V,cnt = 0; cin >> n >> V;for(int i = 1; i <= n; i++){for(int j = V; j >= v[i]; j--){// 表示体积，价值，可选择个数int a,b,s; cin >> a >> b >> s;// 进行二进制拆分，从而将一个多重背包问题转化为多个01背包问题int k = 1;while(k <= s){cnt ++;v[cnt] = a * k;w[cnt] = b * k;s -= k;k *= 2;}if(s > 0){cnt ++;v[cnt] = a * s;w[cnt] = b * s;}}}n = cnt;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];return 0;
}