一、 问题分析

多重背包的本质是在 0-1 背包的基础上增加了数量限制。其状态转移方程为： 其中 。

两种算法优化：

1. 二进制拆分优化 (Binary Splitting)
  • 数学原理：任何正整数 都可以唯一地表示为若干个 2 的幂次项之和与一个余项之和。例如 。通过这种拆分，我们可以将 个物品组合成 组“捆绑包”。
  • 实现简单，且能将多重背包转化为 0-1 背包。其理论上限为 。
2. 单调队列优化 (Monotonic Queue Optimization)
  • 数学原理：观察状态转移方程，对于固定的余数 ，状态转移仅在 这一序列中进行。通过变量替换，可以将原方程改写为滑动窗口最值问题。
  • 理论最优：其复杂度为 ，与 无关，在 极大时具有绝对优势。

二、 代码实现

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

array<ll, 3005> dp;
array<ll, 3005> g;

void solve() {
    int n, m;
    cin >> n >> m;

    dp.fill(0);
    ll base = 0;

    deque<int> dq;

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

        if (w == 0) {
            base += (ll)v * s;
            continue;
        }

        g = dp;

        // 遍历余数 r，将背包容量划分为 w 个等差序列
        for (int r = 0; r < w; r++) {
            dq.clear();

            // 序列中的第 k 个元素对应容量 j = r + k * w
            for (int k = 0; r + k * w <= m; k++) {
                int j = r + k * w;

                // 计算当前状态的特征值，用于单调队列比较
                // 目标：维护 g[r + t*w] - t*v 的单调递减队列
                ll curVal = g[j] - (ll)k * v;

                // 1. 维护队列单调性：如果当前值比队尾更优，弹出队尾
                while (!dq.empty()) {
                    ll backVal = g[r + dq.back() * w] - (ll)dq.back() * v;
                    if (backVal <= curVal) {
                        dq.pop_back();
                    } else {
                        break;
                    }
                }
                dq.push_back(k);

                // 2. 维护窗口大小：如果队首下标超出数量限制 s，弹出队首
                if (dq.front() < k - s) {
                    dq.pop_front();
                }

                // 3. 更新当前状态 dp[j]
                // 方程：dp[k*w+r] = max(g[t*w+r] + (k-t)*v)
                int best_t = dq.front();
                dp[j] = g[r + best_t* w] + (ll)(k - best_t) * v;
            }
        }
    }
    cout << dp[m] + base << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

三、 复杂度分析

算法 时间复杂度 空间复杂度 评价
朴素 DP 无法通过，在本题中 会导致超时。
二进制拆分 复杂度稍高。
单调队列 最优解。复杂度与物体数量 无关。

Trade-offs (权衡)：

  • 二进制拆分的优势在于代码逻辑复用（复用 0-1 背包逻辑），但如果 进一步增大或 变得更苛刻，则会失效。
  • 单调队列虽然增加了实现复杂度（需要维护 Deque），但它将多重背包问题在时间曲线上拉平到了与完全背包/0-1 背包同级的效率。