多重背包问题

每种物品有一个固定取数的上限

• 有 N 种物品和一个容量是 V 的背包。
• 第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
• 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
• 输出最大价值。

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：
10

数据范围

0<N,V≤100
0<vi,wi,si≤100

---

f[i] 表示总体积是 i 的情况下的最大价值；

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int n, m;
int f[N];

int main(){
    cin >> n >> m;
    for (int i = 0; i<n; i++){
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = m; j >= 0; j--){
            for (int k =1; k<=s && k * v<= j; k++){ // 01背包问题加一层循环
                f[j] = max(f[j], f[j - k *v] + k* w);
            }
        }
    }

    cout << f[m] << endl;
    return 0;
}

多重背包的二进制优化

数据范围

0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

如果上面数据范围仍按照三维循环去求解，时间复杂度将会达到 2e9，会 TLE

优化方法：通过把物品件数拆为二进制份，转化为 01 背包问题求解

二进制拆分算法：

• 比如 10 个物品，我们可以拆成 1，2，4 和 3（10-1-2-4得到），则1，2，4，3可以组合得到 1 到 10 的所有数字，
• 如何证明? 证明：s 分为两部分 1,2,4,8,...,2^k和 s - 2^k,前半部分，我们可以通过二进制表示证明 1 到 2^k 都可取，剩下部分s - 2^k的取值范围在[0,2^k)之间，我们可以想象把后半部分移到前面，前半部分移到后面，可以得到后半部分的任意取值也都可以得到

#include <bits/stdc++.h>
using namespace std;

const int N = 2010;
int n, m;
int f[N] = {0};

struct Good {
    int v, w;
};

int main(){
    cin >> n >> m;
    vector<Good> goods;
    for (int i = 0; i< n; i++){
        int v, w, s;
        cin >> v >> w >> s;
        for (int k = 1; k <= s; k *= 2){
            s -= k;
            goods.push_back({v*k, w*k}); // 将多重背包打包成了经过二进制拆分的包裹
        }
        if (s > 0) goods.push_back({v*s, w*s});
    }
    for (auto good: goods){
        for (int j = m; j >= good.v; j--){
            f[j] = max(f[j], f[j - good.v] + good.w);
        }
    }

    cout << f[m] << endl;
    return 0;
}