🧐 什么是完全背包？

0-1背包里，每个宝贝只能拿一次，像考试答题机会只有一次。

而在完全背包里，每种宝贝可以拿无限次！想拿几件就拿几件，就像吃糖果🍬，口袋能装得下，随便拿！

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

#include <iostream>        // 引入输入输出库
#include <vector>          // 引入 vector 容器
#include <algorithm>       // 引入算法库，使用 max 函数
using namespace std;

/**
 * 完全背包函数
 * @param W 背包总容量
 * @param weights 每种宝贝的重量
 * @param values 每种宝贝的价值
 * @return 能获得的最大价值
 */
int completeKnapsack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();  // 宝贝的数量

    // 创建一个一维数组 dp，大小是 W+1，初始全是0
    // dp[w] 表示容量为 w 时，背包能装下的最大价值
    vector<int> dp(W + 1, 0);

    // 外层循环：遍历所有宝贝
    for (int i = 0; i < n; i++) {
        // 内层循环：注意从小到大遍历容量
        for (int w = weights[i]; w <= W; w++) {
            // 状态转移：当前容量下，看看要不要再放一个第 i 个宝贝
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }

    // 最后返回：容量为 W 时的最大价值
    return dp[W];
}

int main() {
    // 宝贝的重量（kg）
    vector<int> weights = {1, 3, 4};
    // 宝贝的价值（元）
    vector<int> values = {150, 200, 300};
    // 背包的总容量（kg）
    int W = 4;

    // 调用 completeKnapsack 函数
    cout << "最多可以获得价值：" << completeKnapsack(W, weights, values) << " 元" << endl;

    return 0;
}

🧠 小朋友版讲解：

背包总容量：4公斤！

规则：每样东西，可以拿好多好多次！

那怎么玩？

比如：

• 4个小熊饼干 → 重量 4kg，价值 600元！🍪🍪🍪🍪

• 1个智能音响 → 重量 4kg，价值 300元！🔊

• 1个游戏手柄+1个小熊饼干 → 重量 4kg，价值 200+150=350元！🎮🍪

哪种最赚？
当然是拿 4个小熊饼干，价值高达 600元！

所以，程序跑出来就是：

最多可以获得价值：600 元

🎯 为什么完全背包内层要从小到大遍历？

• 因为每个宝贝可以选很多次！

• 如果从大到小，就会错过很多组合机会。

• 从小到大，每次更新，让小容量的结果累积影响大容量，就像滚雪球一样越来越大！

📌 记住的小知识点：

🤔 0-1背包和完全背包，到底有什么区别？