🎒 野牛程序员讲少儿编程之——多重背包问题（C++版）

🧐 什么是多重背包？

前面学的：

• 0-1背包：每种物品只能拿一次。

• 完全背包：每种物品可以拿无限次。

那多重背包呢？
👉 就是每种物品可以拿有限次数！
比如，小熊饼干店限购，每人最多买5包，不能全搬走哦！🍪🍪🍪🍪🍪

一句话总结：
每种物品的数量是有限制的！

📚 看C++代码（附超详细注释）

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

/**
 * 多重背包函数
 * @param W 背包总容量
 * @param weights 每种宝贝的重量
 * @param values 每种宝贝的价值
 * @param counts 每种宝贝的数量限制
 * @return 能获得的最大价值
 */
int multipleKnapsack(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++) {
        // 遍历当前宝贝可以拿的次数
        for (int k = 1; k <= counts[i]; k++) {
            // 必须倒着遍历容量，避免重复使用
            for (int w = W; w >= weights[i]; w--) {
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
    }

    return dp[W];
}

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

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

    return 0;
}

🧠 小朋友版讲解

背包容量：4kg！🎒
规则：每种宝贝有限制！

怎么选最赚？

• 2包小熊饼干（1kg+1kg）= 2kg，价值300元！🍪🍪

• 1个游戏手柄（3kg）= 3kg，价值200元！🎮

• 1个智能音响（4kg）= 4kg，价值300元！🔊

那最聪明的玩法是？
👉 直接装1个智能音响，装满4kg，赚300元！

所以程序输出是：

最多可以获得价值：300 元

🎯 多重背包的难点在哪里？

小朋友要记得：

• 不是能拿就一直拿！每种宝贝有数量上限。

• 所以要多层循环：每种物品 → 每件物品 → 每个背包容量。

• 避免重复计算，容量要从大到小倒着遍历。

📢 小总结（很重要！）

🔔 小诀窍：
有次数限制的，就是多重背包！

✨ 小剧场 🎭

如果小熊饼干无限量供应，那是完全背包；
如果每人限购2包，那就是多重背包；
如果只能买1次机会，那就是0-1背包！

是不是超级形象！