? 野牛程序员讲少儿编程之【超神版】——多重背包 + 单调队列优化！（爆炸提速版）

? 为什么又来一个更高级的？

之前的「二进制优化」，已经能处理中等数量了。

但是！
如果物品超级多，比如每种物品有上万件，背包容量又特别大，
就算是二进制优化，还是有点吃力。

所以，真正的背包王者会用——
? 单调队列优化（Monotonic Queue Optimization）

这种方法就像是：

• 把所有可能性排成一个整齐的队伍?‍♂️?‍♀️

• 快速挑出最有价值的选择！?

• 不用每次一个个试！

超大数据量，也能飞快飞快飞快处理！⚡⚡⚡

? 代码展示（带超详细注释版）

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

/**
 * 多重背包 + 单调队列优化
 * @param W 背包总容量
 * @param weights 每种宝贝的重量
 * @param values 每种宝贝的价值
 * @param counts 每种宝贝的数量
 * @return 最大能获得的价值
 */
int multipleKnapsackQueue(int W, vector<int>& weights, vector<int>& values, vector<int>& counts) {
    int n = weights.size();
    vector<int> dp(W + 1, 0); // dp[w] 表示容量为 w 时的最大价值

    for (int i = 0; i < n; i++) {
        int weight = weights[i];
        int value = values[i];
        int count = counts[i];

        // 对同余系分组处理
        for (int mod = 0; mod < weight; mod++) {
            deque<int> q; // 单调队列，存放的是 背包容量索引

            for (int k = mod; k <= W; k += weight) {
                // 保证队列头部元素在合理数量范围内
                if (!q.empty() && (k - q.front()) / weight > count) {
                    q.pop_front();
                }

                // 计算当前要比较的值
                int current = dp[k] - (k / weight) * value;

                // 队列保持单调递减，弹出尾部比 current 小的元素
                while (!q.empty()) {
                    int prev = q.back();
                    if (dp[prev] - (prev / weight) * value <= current) {
                        q.pop_back();
                    } else {
                        break;
                    }
                }

                q.push_back(k);

                // 更新 dp[k]
                int best = q.front();
                dp[k] = dp[best] + (k - best) / weight * value;
            }
        }
    }

    return dp[W];
}

int main() {
    // 宝贝的重量（kg）
    vector<int> weights = {2, 3, 5};
    // 宝贝的价值（元）
    vector<int> values = {200, 300, 500};
    // 每种宝贝的最大数量
    vector<int> counts = {100, 50, 20}; // 有很多很多件！
    // 背包总容量（kg）
    int W = 1000;

    cout << "最多可以获得价值：" << multipleKnapsackQueue(W, weights, values, counts) << " 元" << endl;

    return 0;
}

? 这段代码到底在干什么？

简单说，就是：让背包问题变成选队列里最牛的那个人！

? 小剧场时间

小明背着超级大的背包去超市，
商品太多了，看得眼睛都花了。?

这时候，聪明的野牛程序员告诉他：
「不用全都看！只挑最便宜又最好的那几个，直接塞进去！」?

小明一下子装了最多的宝贝，满载而归！?✨

? 为什么单调队列这么猛？

? 单调队列小口诀

分组取模走队列，
队头最优直接追；
超数量就弹出去，
背包装满笑开怀！?