知识点小结
背包问题是动态规划的经典模型，核心是在有限容量下选择物品，使总价值最大。三种背包的区别仅在于每件物品的数量限制，由此决定了遍历顺序和状态转移方式。
背包类型 物品数量限制 遍历顺序 核心思想 01背包 每件只能选 0 或 1 次 容量逆序遍历 保证每件物品只被选一次 完全背包 每件可以选无限次 容量正序遍历 允许同一物品被重复选取 多重背包 每件最多选 s[i] 次 枚举选取件数 k 在 0~s[i] 范围内尝试所有可能
状态转移方程（二维版）
含义：对于第 i 件物品，尝试选 0 件、1 件、2 件……最多 k 件，取所有方案中的最大值。
一维滚动数组优化
背包逆序 防止同一物品被重复使用
完全背包正序 允许同一物品被重复使用
多重背包 根据 s[i] 的大小，退化为 01 背包或完全背包
二维数组版（多重背包通用模板）
逐行说明：
一维滚动数组版（混合背包优化）
逐行说明：
💡 核心对比总结
对比项 01背包 完全背包 多重背包 每件物品数量 1件 无限件 s[i]件 容量遍历方向 逆序（大到小） 正序（小到大） 视情况而定 一维转移方程 dp[j]=max(dp[j],dp[j-w]+v) 同上 同上（外层多一层k循环） 逆序/正序的原因 防止同一物品被重复使用 允许同一物品被重复使用 — 时间复杂度 O(n×c) O(n×c) O(n×c×s)
🧪 记忆口诀
01背包逆着走，完全背包顺着走，多重背包看数量——多了当完全，少了拆01。
