OI Wiki 背包 DP如何选择背包类型并完成状态转移【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki在 OI WikiMkDocs 构建的 OI / ICPC 知识 Wiki中背包 DP 是 动态规划部分的核心模型之一面对一道选物求最大价值的问题你需要先判断物品「能被选几次」再套对应的转移写法。这篇文章沿着 背包 DP 一篇给出可落地的路径按选次约束选择 0-1、完全、多重或混合背包写出空间压缩后的状态转移再用仓库自带的例题代码和样例输入输出验证你的实现。按物品的选取次数选择背包类型文档中四种模型的差别只在于每种物品可以被选几次据此对号入座背包类型文档给出的选取约束转移枚举方向一维压缩后0-1 背包每个物品只能取一次容量从大到小l从W枚举到w[i]完全背包每种物品可以选取无限次容量从小到大l从w[i]枚举到W多重背包每种物品有 $k_i$ 个而非一个容量从大到小内层再枚举选取数量 $k$混合背包有的只能取一次、有的取无限次、有的取 $k$ 次逐物品判断后分别套用上面的核心代码判断依据来自题目对选取次数的描述文档以 「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_{k0}^{\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_{i1}^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_i1$ 不是 $2$ 的整数次幂最后补一个剩余数量捆绑的大物品。文档给出的拆分示例$6123$$81241$$1812483$$31124816$拆分后按 0-1 背包求解时间复杂度降为 $O(W\sum_{i1}^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.cpp0-1 背包先读n Wknapsack_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 2knapsack_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_01$求最优方案总数需把状态改为「正好装满」并对 $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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考