? 野牛程序员讲少儿编程之——多重背包【高级版】！（二进制优化）

? 为什么要高级版？

在上一个普通版多重背包中，
每件物品拿多少次，是一个一个慢慢试的，
效率不太高，像在超市排长队结账一样慢。?

高级版用“二进制优化”技巧，直接加速！
像开了VIP快速通道，速度飞快！?️?

? 什么是二进制优化？

假设某个物品有 13件可以选。

如果一个一个拿，循环13次，累到吐。

二进制优化的思路是：

• 先拿1件（1个）

• 再拿2件（2个）

• 再拿4件（4个）

• 再拿6件（因为1+2+4=7，13-7=6，还剩6件可以直接拿）

这样最多循环 log₂(件数) 次！超级省时间！

? 高级版代码（附超详细注释）

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

/**
 * 多重背包高级版（使用二进制优化）
 * @param W 背包总容量
 * @param weights 每种宝贝的重量
 * @param values 每种宝贝的价值
 * @param counts 每种宝贝的数量限制
 * @return 最大能获得的价值
 */
int multipleKnapsackBinary(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];

        int k = 1;
        while (count > 0) {
            int actual = min(k, count); // 本次真正取的数量
            int new_weight = weight * actual;
            int new_value = value * actual;

            // 0-1背包方式，大到小更新
            for (int w = W; w >= new_weight; w--) {
                dp[w] = max(dp[w], dp[w - new_weight] + new_value);
            }

            count -= actual;
            k *= 2; // 继续下一次，倍增
        }
    }

    return dp[W];
}

int main() {
    // 宝贝的重量（kg）
    vector<int> weights = {1, 3, 4};
    // 宝贝的价值（元）
    vector<int> values = {150, 200, 300};
    // 每种宝贝的最大数量
    vector<int> counts = {5, 2, 1};  // 小熊饼干最多5包，游戏手柄2个，音响1个
    // 背包总容量（kg）
    int W = 10;

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

    return 0;
}

? 核心思路解释

✨ 举个小例子

假设：
小熊饼干：5包可以拿

普通方式 → 试1包、2包、3包、4包、5包，慢死了！
高级方式：

• 第一次拿1包 （2⁰）

• 第二次拿2包（2¹）

• 第三次拿2包（剩余）

只需要3次！速度翻倍！

? 高级版 vs 普通版

? 小总结

? 小剧场

「小熊饼干最多5包，怎么办？」
——「二进制拆分！1包+2包+2包，搞定！不用每次慢慢加！」??

二进制优化，就是把拿物品这件事变成了玩魔法数字游戏，轻轻松松赢下背包王国的战斗！?