企业官网建设流程全解析

OI Wiki 背包 DP：如何选择背包类型并完成状态转移

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

在 OI Wiki（MkDocs 构建的 OI / ICPC 知识 Wiki）中，背包 DP 是 动态规划部分的核心模型之一：面对一道选物求最大价值的问题，你需要先判断物品「能被选几次」，再套对应的转移写法。这篇文章沿着 背包 DP 一篇给出可落地的路径：按选次约束选择 0-1、完全、多重或混合背包，写出空间压缩后的状态转移，再用仓库自带的例题代码和样例输入输出验证你的实现。

按物品的选取次数选择背包类型

文档中四种模型的差别只在于每种物品可以被选几次，据此对号入座：

判断依据来自题目对选取次数的描述：文档以 「USACO07 DEC」Charm Bracelet 为例说明 0-1 背包——每个物体只有取与不取两种状态；完全背包「与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次」；多重背包「与 0-1 背包的区别在于每种物品有 $k_i$ 个，而非一个」；混合背包则是「将前面三种的背包问题混合起来」。

0-1 背包：状态定义与反向转移

设状态 $f_{i,j}$ 为只能放前 $i$ 个物品时，容量为 $j$ 的背包能达到的最大总价值，转移方程为：

$$ f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i}) $$

文档指出，二维记录会 MLE，由于对 $f_i$ 有影响的只有 $f_{i-1}$，可去掉第一维得到一维方程 $f_j=\max(f_j,f_{j-w_i}+v_i)$。

关键在枚举顺序。下面这段是文档标注的错误核心代码：

for (int i = 1; i <= n; i++) for (int l = 0; l <= W - w[i]; l++) f[l + w[i]] = max(f[l] + v[i], f[l + w[i]]);

它错在：$j\geqslant w_i$ 时 $f_{i,j}$ 会被同一轮的 $f_{i,j-w_i}$ 影响，相当于物品 $i$ 被多次放入——文档特别说明，这正是完全背包的解法。修正方法是容量从 $W$ 枚举到 $w_i$，保证 $f_{i,j}$ 总是在 $f_{i,j-w_i}$ 之前被更新：

for (int i = 1; i <= n; i++) for (int l = W; l >= w[i]; l--) f[l] = max(f[l], f[l - w[i]] + v[i]);

完全背包：同样的转移，正向枚举

完全背包的状态定义与 0-1 相同，但转移方程不同。朴素做法是枚举第 $i$ 件物品选了多少个，时间复杂度 $O(n^3)$：

$$ f_{i,j}=\max_{k=0}^{+\infty}(f_{i-1,j-k\times w_i}+v_i\times k) $$

优化后只需通过 $f_{i,j-w_i}$ 转移，因为 $f_{i,j-w_i}$ 已经充分考虑了第 $i$ 件物品的选取次数：

$$ f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i) $$

去掉第一维后，压缩的循环恰好是正向的——也就是上一节里对 0-1 背包而言错误、对完全背包而言正确的写法。

多重背包：先转成 0-1，再用二进制分组

多重背包可以直接枚举每种物品选 $k_i$ 次：把「每种物品选 $k_i$ 次」等价转换为「有 $k_i$ 个相同的物品各选一次」，时间复杂度 $O(W\sum_{i=1}^nk_i)$，核心代码：

for (int i = 1; i <= n; i++) { for (int weight = W; weight >= w[i]; weight--) { // 多遍历一层物品数量 for (int k = 1; k * w[i] <= weight && k <= cnt[i]; k++) { dp[weight] = max(dp[weight], dp[weight - k * w[i]] + k * v[i]); } } }

$O(\sum k_i)$ 部分可用二进制分组优化：把第 $i$ 种物品拆成由 $2^j$ 个单个物品「捆绑」而成的大物品，若 $k_i+1$ 不是 $2$ 的整数次幂，最后补一个剩余数量捆绑的大物品。文档给出的拆分示例：

• $6=1+2+3$
• $8=1+2+4+1$
• $18=1+2+4+8+3$
• $31=1+2+4+8+16$

拆分后按 0-1 背包求解，时间复杂度降为 $O(W\sum_{i=1}^n\log_2k_i)$。仓库中的分组代码（变量 $p$、$h$、$k$ 分别为单价重量、单价价值和数量）：

index = 0; for (int i = 1; i <= m; i++) { int c = 1, p, h, k; cin >> p >> h >> k; while (k > c) { k -= c; list[++index].w = c * p; list[index].v = c * h; c *= 2; } list[++index].w = p * k; list[index].v = h * k; }

若需进一步优化，文档指向 单调队列/单调栈优化。

混合背包：逐物品判断后套用对应核心代码

混合背包的伪代码（引自文档）就是逐物品分派：

for (循环物品种类) { if (是 0 - 1 背包) 套用 0 - 1 背包代码; else if (是完全背包) 套用完全背包代码; else if (是多重背包) 套用多重背包代码; }

以 「Luogu P1833」樱花 为例，核心代码用cnt[i]是否为零区分两种路径：

for (int i = 1; i <= n; i++) { if (cnt[i] == 0) { // 如果数量没有限制使用完全背包的核心代码 for (int weight = w[i]; weight <= W; weight++) { dp[weight] = max(dp[weight], dp[weight - w[i]] + v[i]); } } else { // 物品有限使用多重背包的核心代码，它也可以处理0-1背包问题 for (int weight = W; weight >= w[i]; weight--) { for (int k = 1; k * w[i] <= weight && k <= cnt[i]; k++) { dp[weight] = max(dp[weight], dp[weight - k * w[i]] + k * v[i]); } } } }

注释里还给了一个实用结论：多重背包的核心代码同样能处理 0-1 背包（数量上限为 1 时内层循环自然只跑一次），所以只需「无限 / 有限」两分支即可覆盖三种模型。

编译例题代码并用样例输入验证

仓库提供了两份可直接编译的例题程序和配套样例。注意两份程序的输入顺序不同，这是代码实际读入的顺序决定的：knapsack_1.cpp（0-1 背包）先读n W，knapsack_2.cpp（完全背包）先读W n。

0-1 背包例题（读入n W，随后 $n$ 行每行w[i] v[i]）：

g++ -O2 -o knapsack_1 docs/dp/code/knapsack/knapsack_1.cpp ./knapsack_1 < docs/dp/examples/knapsack/knapsack_1.in

样例输入knapsack_1.in为4 6加四行物品（1 4、2 6、3 12、2 7），文档配套的标准答案文件 knapsack_1.ans 内容是一个数23。你自己的程序对该样例输出 23，即与文档样例一致。

完全背包例题（读入W n，随后 $n$ 行每行w[i] v[i]）：

g++ -O2 -o knapsack_2 docs/dp/code/knapsack/knapsack_2.cpp ./knapsack_2 < docs/dp/examples/knapsack/knapsack_2.in

样例输入knapsack_2.in为70 3加三行物品（71 100、69 1、1 2），knapsack_2.ans 内容为140。

此外，仓库把例题代码的编译与正确性作为贡献检查的一环：scripts/README.md 说明存在测试文档实例代码正常编译的脚本，CLAUDE.md 给出在本地环境（Python 3.10+、uv、Yarn 就绪）下运行python3 scripts/correctness_check.py对 C++ 示例做编译验证的方式，适合批量改动例题代码后自查。

边界与注意事项

• 枚举顺序是两类模型的分水岭：0-1 背包正向枚举会退化成完全背包（物品可多次放入），完全背包反向枚举则只选一次。改代码时先确认目标模型，再定l的增减方向。
• 输出方案类问题需要额外记录：用 $g_{i,v}$ 标记第 $i$ 件物品占用空间 $v$ 时是否被选，转移时记录采用「选 / 不选」哪种策略，再从最后一件物品倒推（详见 背包 DP 的「输出方案」小节）；求方案数则把转移中的 $\max$ 换成求和、初始条件设为 $dp_0=1$；求最优方案总数需把状态改为「正好装满」，并对 $f$ 数组按负无穷（0xcf）初始化、$f[0]=0$、$g[0]=1$。
• 二维费用背包（如 「Luogu P1855」榨取 kkksc03）在状态中增加一维存放第二种费用即可，但文档提醒不要再为物品编号开一维，容易 MLE；分组背包（同组最多选一个）对每组做一次 0-1 背包，文档特别强调「一定不能搞错循环顺序」。
• 文档的参考资料一节列出了崔添翼的《背包问题九讲》作为延伸阅读。

完成上面任一路径后，可以打开 背包 DP 核对对应小节的转移方程与核心代码是否一致；遇到单调队列优化或多叉树依赖背包等进一步话题，再分别进入 单调队列/单调栈优化 或 动态规划部分简介 继续。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki