野牛程序员讲少儿编程之——背包问题！小背包，大智慧！

? 野牛程序员讲少儿编程之——背包问题！小背包，大智慧！

?? 适合孩子的算法知识也能有趣又生动！

今天来聊聊算法界的“收纳大师”——背包问题（Knapsack Problem）！

? 背包问题到底是个啥？

设想有一个背包，容量为 W 千克，
地上有一堆宝贝（物品），每个宝贝都有：

• 一个重量（重量不能超过背包容量）

• 一个价值（当然越贵越好啦）

任务是：

在不超过背包容量的前提下，把“最值钱”的宝贝装进背包！

简直是程序员版的“收纳艺术”?

? 举个例子：

背包容量：4kg
最多能带走多少价值的宝贝？

? 解法思路：动态规划出场！

关键词：每个宝贝“选”还是“不选”

咱用一个二维数组 dp[i][w] 表示：

前 i 件宝贝，在容量为 w 的背包里，最多能装多少价值。

? 状态转移方程：

if (w >= weight[i])
    dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]);
else
    dp[i][w] = dp[i-1][w];

? 不装第 i 个宝贝：价值等于前 i-1 个在 w 的值
? 装第 i 个宝贝：价值是前 i-1 个在 w - weight[i] 加上当前价值

? C++ 完整代码示例：

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

int knapsack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (w >= weights[i - 1]) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    vector<int> weights = {1, 3, 4};
    vector<int> values = {150, 200, 300};
    int W = 4;

    cout << "最多可以获得价值：" << knapsack(W, weights, values) << " 元" << endl;
    return 0;
}

输出：最多可以获得价值：350 元

? 装小熊饼干（1kg）+ 编程书（4kg太重，只能选游戏手柄）
最佳选择是：小熊饼干 + 游戏手柄 → 总重量 4kg，总价值 350 元！

? 背包问题的变种：

? 孩子能学什么？

✅ 学会在“限制”中做出“最优”选择
✅ 学习 数学建模 思维
✅ 提高空间思维能力和逻辑思维力
✅ 还挺像现实中的“做选择题”?

? 背包问题不只是算法，它教的是真正的生活智慧：

就像日常生活中：“书包不能装太多，那就得选对的书”?
程序员学背包，孩子也能学收纳、学权衡！

? 野牛程序员小总结一下：

✨ 找出“选择与否”的策略
✨ 用动态规划存结果，避免重复计算
✨ 利用二维数组 dp[i][w] 来模拟状态变化

#include <iostream>        // 引入输入输出的库，方便用 cout 打印
#include <vector>          // 引入 vector 容器，可以动态存储数组
#include <algorithm>       // 引入算法库，用来使用 max 函数
using namespace std;       // 让代码更简洁，不用每次写 std::

/**
 * 背包函数
 * @param W 背包总容量
 * @param weights 每个宝贝的重量列表
 * @param values 每个宝贝的价值列表
 * @return 最多能获得的总价值
 */
int knapsack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();  // n 是宝贝的数量，比如有3件宝贝

    // 创建一个二维数组 dp，大小是 (n+1) 行 (W+1) 列，初始值都设为 0
    // dp[i][w] 表示前 i 件宝贝，在容量 w 下，能获得的最大价值
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    // 外层循环：从第 1 个宝贝开始处理
    for (int i = 1; i <= n; i++) {
        // 内层循环：背包容量从 0 开始一直到最大 W
        for (int w = 0; w <= W; w++) {
            if (w >= weights[i - 1]) {
                // 如果当前背包还能装得下第 i 个宝贝

                // 两种选择：
                // 1. 不装这个宝贝，价值就是 dp[i-1][w]
                // 2. 装这个宝贝，价值是 dp[i-1][w - 当前宝贝重量] + 当前宝贝价值
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                // 如果装不下这个宝贝，只能沿用之前的最大价值
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // 最后返回：n 件宝贝，在容量 W 下的最大价值
    return dp[n][W];
}

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

    // 调用 knapsack 函数，求最大能装多少价值的宝贝
    cout << "最多可以获得价值：" << knapsack(W, weights, values) << " 元" << endl;

    return 0;
}