🎯 第1讲：认识背包问题

背包问题就像逛超市，手里只有一个小背包，容量有限，要在一堆宝贝中挑选，装进最多价值的东西！

常见的背包问题有这些：

• 01背包：每种宝贝只能选一次

• 完全背包：每种宝贝可以无限选

• 多重背包：每种宝贝选的次数有限制

背包问题=选宝贝游戏！🎒🎁

🎯 第2讲：01背包问题

• 有N个宝贝，每个宝贝有重量weight[i]和价值value[i]

• 背包容量是W

• 每种宝贝最多选一次

状态定义：
dp[i][j] = 从前i个宝贝中选，总重量不超过j，能获得的最大价值。

状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]);

可以理解成：
👉 不选第i件 or 选第i件，看谁更优！

✅ 优化技巧：可以压缩成一维数组，从大到小逆序更新！

🎯 第3讲：完全背包问题

区别来了：

• 宝贝可以拿好多次！

公式变化了：

dp[i][j] = max(dp[i-1][j], dp[i][j - weight[i]] + value[i]);

注意：
✅ 完全背包一维优化时，要从小到大正序遍历，因为一个宝贝可以用很多次！

🎯 第4讲：多重背包问题

再升级：

• 每种宝贝有个数量限制，比如count[i]次

经典做法：

• 把物品按照数量拆成多个01背包！

• 比如5件，拆成 1件，2件，2件（用二进制表示）

✅ 二进制优化：用更少的物品数量表示总数，减少循环次数！

🎯 第5讲：多重背包的单调队列优化

刚讲过！

如果数量特别大，拆成很多物品太慢了！
👉 用单调队列优化，快！快！快！

单调队列就是：

• 把物品分成同余分组

• 每组用一个队列维护最优选项

• 快速更新 dp 数组！

适合处理超大数据量的多重背包。

🎯 第6讲：混合背包问题

有些宝贝只能选一次，有些可以选无限次，有些有限制数量。

这就叫混合背包！

做法：

• 根据宝贝类别，分别按照01背包、完全背包、多重背包处理。

• 每种处理方法套一遍。

要动动小脑筋分类哦！🧠✨

🎯 第7讲：背包问题中的优化技巧

经典的优化小技巧包括：

• 滚动数组：节省空间，从二维压成一维。

• 状态压缩：让时间和空间都飞起来！

• 合理遍历顺序：01背包倒序，完全背包顺序。

• 单调队列优化：处理大规模数据神器！

🎯 第8讲：背包问题的变种

背包还能变出好多花样！

• 体积也有限制：不仅是重量，体积也要算

• 附加条件：必须选多少件，必须达到多少价值……

• 多维背包：不仅限制重量，还限制体积、时间等等

玩背包，花样超级多！

🎯 第9讲：背包问题和生活中的联系

生活中处处是背包问题！

比如：

• 打游戏时装备有限，需要合理配置（属性最大化）

• 旅行打包行李，挑最重要的东西装进行李箱

• 超市购物预算有限，买性价比最高的商品

学好背包，不只是比赛用，还能变成聪明的生活小达人！

🛒 小结图标版