企业官网建设流程全解析

引言

新赛季备战进入白热化。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; vector<int> v = {2, 2, 6, 5}; // 体积 vector<int> w = {6, 3, 5, 4}; // 价值 // dp[j] = 容量不超过 j 时能获得的最大价值 vector<int> 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)) # 输出 14

3.4 时间与空间复杂度

• 时间复杂度：O(N·C)，双重循环，每层物品对容量维度扫描一遍。
• 空间复杂度：一维写法O(C)；若保留二维dp[N+1][C+1]则为O(N·C)，便于回溯选了哪些物品。

四、易错点（六条命门）

1. 一维优化内层必须逆序：j从C递减到v[i]。写成正序会让同一物品被多次选取，悄然变成完全背包，答案偏大。
2. "恰好装满"与"不超过"初始化不同：求"最大价值且恰好装满"时，应设dp[0]=0、其余为-∞（负无穷），最后若dp[C] < 0说明无解；而"不超过容量"才全 0 初始化。
3. 数组开C+1：容量维度从 0 到C共C+1个状态，少开一格必越界。
4. 下标与循环范围对齐：物品下标从0到N-1，内层逆序下界是v[i]（体积大于当前容量的物品直接跳过）。
5. 别漏掉"不选"分支：转移是max(dp[j], ...)，dp[j]本身代表不选第i件，漏写会丢失信息。
6. 大数溢出：价值累加到很大时int可能溢出，竞赛里改用long long（C++）或 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 内打开，也可复制下方明文链接：

1. 全国青少年信息素养大赛复赛集训题目Python&C++.docx
   https://pan.quark.cn/s/93995d3cb150
2. 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf
   https://pan.quark.cn/s/da97b5dbf75d
3. Python背记手册.pdf
   https://pan.quark.cn/s/7568ae9ca92b
4. Python课程
   https://pan.quark.cn/s/a94bf02d00c6
5. 2024信息素养大赛图形化复赛集训题答案3-9
   https://pan.quark.cn/s/6ccab7ec3cbc
6. 2025年03月份电子学会考级真题
   https://pan.quark.cn/s/4403c4228912
7. 2025全国青少年信息素养大赛赛项说明
   https://pan.quark.cn/s/d9d0df4a9f29
8. 青少儿信息素养大赛编程资料
   https://pan.quark.cn/s/4ab6bd83be8a

资料持续更新，关注获取最新分享。