引言新赛季备战进入白热化。2026 年南昌市中小学生信息学奥林匹克竞赛将于 10 月 25 日开赛其普及组考察范围明确把动态规划列为必考基础——而动态规划入门绕不开的第一座大山就是背包问题。背包家族0/1 背包、完全背包、多重背包、分组背包……几乎每年都会以各种面目出现在各类算法竞赛的普及组、提高组里有时是选物品求最大价值有时是凑出某个金额的最少硬币数本质都是同一套状态设计。本文用一道原创题带你把 0/1 背包吃透再顺藤摸瓜理清完全背包与多重背包并给出六条高频易错点与上手指引。一、题目 / 项目目标原创集训物资精打细算集训队出发参加信息学竞赛要把备赛物资装进一个容量为C的背包。共有N件物资第i件体积为v[i]、价值为w[i]每件最多只能选一次。求在总体积不超过C的前提下能装下的物资最大总价值是多少输入样例N 4, C 10 v [2, 2, 6, 5] // 体积 w [6, 3, 5, 4] // 价值输出样例14解释选体积为 2价值 6、体积 2价值 3、体积 6价值 5的三件总体积 10、总价值 14已达最优。这道题就是最经典的0/1 背包每样东西拿或不拿只能选一次。它考察的是如何用一个阶段 状态 转移的框架把指数级的暴力搜索压成多项式时间。二、核心考点状态设计dp[j]表示在容量不超过j时能得到的最大价值。转移方程对于第i件物品要么不选价值不变要么选腾出v[i]容量价值加w[i]dp[j] max(dp[j], dp[j - v[i]] w[i])一维空间优化朴素二维dp[i][j]可以滚动压缩成一维内层循环逆序遍历保证每件物品只被使用一次。初始化语义全 0 表示不超过容量的最大价值若要恰好装满需改初始化技巧见易错点 2。复杂度意识时间O(N·C)空间O(C)一维这是面试与竞赛的常考点。三、解法拆解0/1 背包3.1 思路把前i件物品、容量j的最优值递推出来。关键在于一维优化时内层必须逆序因为dp[j]的更新依赖dp[j - v[i]]而这个旧值必须是还没放第i件的状态若正序遍历dp[j - v[i]]已经被本轮第i件更新过等于同一件物品被反复拿就变成了完全背包。3.2 C 双版解法#include iostream #include vector #include algorithm using namespace std; int main() { int N 4, C 10; vectorint v {2, 2, 6, 5}; // 体积 vectorint w {6, 3, 5, 4}; // 价值 // dp[j] 容量不超过 j 时能获得的最大价值 vectorint dp(C 1, 0); for (int i 0; i N; i) { // 一维优化逆序遍历保证每件物品只选一次 for (int j C; j v[i]; --j) { dp[j] max(dp[j], dp[j - v[i]] w[i]); } } cout dp[C] endl; // 输出 14 return 0; }3.3 Python 双版解法def knapsack_01(v, w, C): dp [0] * (C 1) for i in range(len(v)): # 逆序遍历保证第 i 件只被考虑一次 for j in range(C, v[i] - 1, -1): dp[j] max(dp[j], dp[j - v[i]] w[i]) return dp[C] v [2, 2, 6, 5] w [6, 3, 5, 4] print(knapsack_01(v, w, 10)) # 输出 143.4 时间与空间复杂度时间复杂度O(N·C)双重循环每层物品对容量维度扫描一遍。空间复杂度一维写法O(C)若保留二维dp[N1][C1]则为O(N·C)便于回溯选了哪些物品。四、易错点六条命门一维优化内层必须逆序j从C递减到v[i]。写成正序会让同一物品被多次选取悄然变成完全背包答案偏大。恰好装满与不超过初始化不同求最大价值且恰好装满时应设dp[0]0、其余为-∞负无穷最后若dp[C] 0说明无解而不超过容量才全 0 初始化。数组开C1容量维度从 0 到C共C1个状态少开一格必越界。下标与循环范围对齐物品下标从0到N-1内层逆序下界是v[i]体积大于当前容量的物品直接跳过。别漏掉不选分支转移是max(dp[j], ...)dp[j]本身代表不选第i件漏写会丢失信息。大数溢出价值累加到很大时int可能溢出竞赛里改用long longC或 Python 原生大整数完全背包正序循环时dp[j - v[i]]取的是已含本轮的值这正是完全背包要的效果。五、进阶完全背包 / 多重背包 / 变形5.1 完全背包每件无限取只要把内层循环改为正序物品就能被反复选取// 完全背包每件可取无限次 for (int i 0; i N; i) for (int j v[i]; j C; j) dp[j] max(dp[j], dp[j - v[i]] w[i]);def knapsack_complete(v, w, C): dp [0] * (C 1) for i in range(len(v)): for j in range(v[i], C 1): # 正序可重复选 dp[j] max(dp[j], dp[j - v[i]] w[i]) return dp[C]典型应用硬币无限、凑某个金额的最少/最多方案。5.2 多重背包每件限c[i]次—— 二进制拆分若第i件最多取c[i]个可把c[i]拆成1, 2, 4, …及余数每件当作独立的 0/1 背包物品时间降到O(N·C·log c[i])def knapsack_multi(v, w, c, C): dv, dw [], [] for i in range(len(v)): k 1 rem c[i] while k rem: dv.append(v[i] * k) dw.append(w[i] * k) rem - k k 1 if rem 0: dv.append(v[i] * rem) dw.append(w[i] * rem) dp [0] * (C 1) for i in range(len(dv)): for j in range(C, dv[i] - 1, -1): dp[j] max(dp[j], dp[j - dv[i]] dw[i]) return dp[C]5.3 更多变形背包方案数dp[0]1转移由max改为dp[j] (dp[j] dp[j - v[i]]) % MOD。二维费用背包体积 重量双约束dp开二维两重内层都逆序。第k优解状态再扩充一维记录前k大值。六、小结与互动背包问题的灵魂只有一句话阶段里每个状态只由上一个阶段没被本阶段污染过的旧值转移而来。0/1 背包逆序保旧值完全背包正序用新值多重背包借二进制拆分解耦数量——搞懂这一条整族背包都能举一反三。你是刚啃完 0/1 背包还是已经在刷多重背包 / 分组背包了评论区聊聊你被背包支配或反杀的瞬间想看哪类动态规划变形下一篇拆解也欢迎点名。关注我新赛季一起把动态规划这块硬骨头啃下来。 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。