题解 | 【模板】多重背包

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 二进制拆分函数 - 使用 long long 避免溢出
vector<pair<long long, long long>> binarySplit(int weight, int value,
int count) {
    vector<pair<long long, long long>> items;  // 存放拆分后的各组物品

    int k = 1;  // 当前要打包的件数：1,2,4,8,...

    while (k <= count) {
        // 把k件物品打包成一组 - 强制转为long long避免溢出
        items.push_back({(long long)k * weight, (long long)k * value});

        // 减去已处理的件数
        count -= k;

        // 准备下一次打包更多件
        k = k * 2;
    }

    // 处理剩余不够2的幂次的件数
    if (count > 0) {
        items.push_back({(long long)count * weight, (long long)count * value});
    }

    return items;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n, m;
        cin >> n >> m;

        vector<long long> dp(m + 1, 0);
        long long baseValue = 0;  // 体积为0的物品的总价值 - 改为long long

        for (int i = 0; i < n; i++) {
            int w, v, s;
            cin >> w >> v >> s;

            // 特殊情况：体积为0
            if (w == 0) {
                baseValue += (long long)s * v;  // 强制转为long long
                continue;
            }

            // 1. 二进制拆分
            auto items = binarySplit(w, v, s);

            // 2. 对每组做0-1背包
            for (auto& item : items) {
                long long weight = item.first;   // 改为long long
                long long value = item.second;   // 改为long long

                // 0-1背包（逆序）
                for (int j = m; j >= weight; j--) {
                    dp[j] = max(dp[j], dp[j - weight] + value);
                }
            }
        }

        // 最终结果 = 背包能装的最大价值 + 体积为0的物品的总价值
        cout << dp[m] + baseValue << endl;
    }

    return 0;
}