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

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

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

今天来聊聊算法界的“收纳大师”——背包问题（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] 来模拟状态变化