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

输入格式
第一行两个整数，N，V
，用空格隔开，分别表示物品种数和背包容积。

接下来有 N
行，每行三个整数 vi,wi,si
，用空格隔开，分别表示第 i
种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N≤1000

0<V≤2000

0<vi,wi,si≤2000

输入格式
第一行两个整数，N，V
，用空格隔开，分别表示物品种数和背包容积。

接下来有 N
行，每行三个整数 vi,wi,si
，用空格隔开，分别表示第 i
种物品的体积、价值和数量。

样例

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

算法1

C++ 代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using PII = pair<int,int>;

void solve(){
    int n,v;
    cin >> n >> v;
    vector<int> cap(n + 1,0),val(n + 1,0),num(n + 1,0);
    for(int i = 1; i <= n; i++){
        cin >> cap[i] >> val[i] >> num[i];
    }
    vector<vector<int>> dp(n + 1,vector<int> (v + 1,0));

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= v; j++){
            dp[i][j] = dp[i - 1][j];
            for(int k = 1; k <= num[i]; k++){
                if(k * cap[i] <= j){
                    dp[i][j] = max(dp[i][j],dp[i - 1][j - k * cap[i]] + k * val[i]);
                }else{
                    break;
                }
            }
        }
    }
    cout << dp[n][v];
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    int T = 1;
    // cin >> T;
    while(T--){
        solve();
    }

    return 0;
}

算法2

(二进制优化)

二进制优化的原理

假设我们有一种物品，最多可以选择s个。传统方法需要枚举选择0个、1个、2个…直到s个，时间复杂度为O(s)。

但利用二进制的思想，我们可以将s个物品打包成若干个”新物品”：

• 1个物品的包
• 2个物品的包
• 4个物品的包
• 8个物品的包
• …
• 2^k个物品的包（其中2^k ≤ s < 2^(k+1)）
• 剩余的物品包（如果有的话）
  这样，我们最多只需要log₂s + 1个包，就可以表示从0到s的任意数量的物品选择

C++ 代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using PII = pair<int,int>;

void solve(){
    int n,v;
    cin >> n >> v;
    vector<int> dp(v + 1,0);

    for(int i = 1; i <= n; i++){
        int cap,val,cnt;
        cin >> cap >> val >> cnt;
        for(int k = 1; k <= cnt; k *= 2){
            int new_cap = k * cap;
            int new_val = k * val;
            cnt -= k;
            for(int j = v; j >= new_cap; j--){
                dp[j] = max(dp[j],dp[j - new_cap] + new_val);
            }
        }
        if(cnt > 0){
            int new_cap = cnt * cap;
            int new_val = cnt * val;
            for(int j = v; j >= new_cap; j--){
                dp[j] = max(dp[j],dp[j - new_cap] + new_val);
            }
        }
    }

    cout << dp[v];
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    int T = 1;
    // cin >> T;
    while(T--){
        solve();
    }

    return 0;
}