东华OJ进阶系列里“盾神与砝码称重”这道题我刷完最大的感受是它不像表面看起来那么“入门”。题目背景很生活化——一个天平、一堆砝码、一个能“作弊”把砝码放物品同侧的盾神实际上考的是组合状态、背包思想和位运算优化是一道能把DP基础打得非常扎实的好题。很多第一次见到这题的人会直接想每个砝码要么不放要么放右边这不就是个普通子集和吗还真不是。这里最大的区别是砝码可以放物品同侧也就是可以“抵消”一部分重量这直接改变了整个状态模型。我把这个坑、正负状态处理、bitset 优化以及提交时容易踩的雷全部整理成一篇适合正在刷OJ、准备算法面试或者想系统搞懂“天平/称重类问题”的读者。1. 读懂题意这个题到底要算什么1.1 天平模型中的三种选择假设物品放在左盘砝码可以放右盘也可以放左盘还可以不放。天平平衡的条件是右盘砝码总重量 左盘砝码总重量 物品重量所以物品重量等于“右盘砝码和”减去“左盘砝码和”。对每个砝码来说它有三种贡献不放贡献 0放右盘贡献 w放左盘贡献 -w。题目要统计的是用这 n 个砝码每种砝码最多用一次一共能称出多少种不同的正整数重量。这就是“三种状态”和普通 0/1 背包“两种状态”的本质区别。如果用数学模型来描述就是给每个砝码赋一个系数 s_is_i 只能取 -1、0、1然后求所有可能的 ∑(s_i * w_i) 中有多少个不同的正数。1.2 为什么不是简单子集和很多同学第一次接触背包题会把这道题理解成“砝码只能放右边”那就退化成了经典子集和问题问能凑出哪些重量。这种情况一个砝码只有取或不取两种选择状态定义很简单一个一维 bool 数组倒着更新就能写完。但一旦砝码能放物品同侧问题性质就变了。砝码对最终重量的贡献可正可负最终结果不光是“相加”而是“做差”。我习惯把这个模型叫“子集差问题”每个砝码相当于一个可以取正、取负、取零的贡献值最终我们要统计所有符号组合的正值个数。举个例子砝码是 5 和 3除了能称 5、3、8 之外还能称 2因为右盘放 5左盘放 3物品重量就是 5 - 3 2。子集和模型完全覆盖不了这种情况。这也是这道题最值得玩味的地方一个“能不能把砝码放同侧”的设定变化把题目从入门背包直接拉到了需要认真考虑状态空间、偏移量和正负边界的中等题。1.3 选算法前先看数据范围刷OJ第一原则拿到题先看数据范围数据范围直接决定你该用哪种算法而不是一上来就写最优解法。我整理了大致的策略表数据规模可行方案时间复杂度n 15DFS 暴力枚举O(3^n)n 20 且总重量不大DFS 剪枝 / 折半搜索O(3^(n/2) log...)总重量 sum 2e5 左右带偏移量的动态规划O(n * sum)总重量 sum 更大bitset 位运算优化O(n * sum / 64) 左右实际OJ里这题常见的数据范围n 在几百到一千以内砝码重量累计和通常不超过 1e5 这个量级所以动态规划和 bitset 都能过。但理解暴力法和 DFS 依然很重要因为它是验证 DP 思路是否正确的最快方式。2. 暴力枚举先用 DFS 理解状态空间2.1 三叉树枚举所有状态组合如果 n 很小最直接的思路就是递归。每个砝码有三种选择我把它称为“三叉树”。走到最后一个砝码时当前累计的净重量如果是正数就丢进 set 里去重。#include bits/stdc.h using namespace std; int n; vectorint w; setint ans; void dfs(int idx, int cur) { if (idx n) { if (cur 0) ans.insert(cur); return; } dfs(idx 1, cur); // 不放 dfs(idx 1, cur w[idx]); // 放砝码侧 dfs(idx 1, cur - w[idx]); // 放物品侧 } int main() { cin n; w.resize(n); for (int i 0; i n; i) cin w[i]; dfs(0, 0); cout ans.size() endl; return 0; }这个代码的关键点是cur允许为负。因为实际称重时如果最终净重量是负数那只是左右盘互换的镜像情况对我们统计正整数重量没有影响所以我们只在叶子节点判断cur 0。2.2 set 去重与复杂度变化为什么用 set因为同一个正整数重量可能对应多种不同的砝码分配方案。比如砝码是 1、2、3重量 2 可以由砝码 2 单独称出也可以由右盘 3、左盘 1 称出3 - 1 2两种方式都合法但只能算一种重量。所以叶子节点不能直接计数必须去重。set 是最简单的去重工具代价是插入一次 O(log m)。n 比较小时这个开销无所谓但 n 到 15 以后3^15 ≈ 1400 万插入 set 也会明显变慢需要注意。2.3 暴力法的适用边界3^n 的复杂度增长非常快n 1059049随便跑n 1514348907勉强能跑n 203486784401完全不可行。所以纯 DFS 只适合 n 不超过 15 的场景或者作为验证用“对拍器”。如果 n 在 20 到 30 之间可以考虑折半搜索Meet in the Middle。思路是把砝码分成前后两半分别枚举所有符号组合得到两个数组 A 和 B每个数组的大小是 3^(n/2)。然后对 B 排序遍历 A 中的每个值 x在 B 里二分查找大于 -x 的元素个数累加就能统计出所有正重量数量。折半搜索可以把 n 30 左右的题从“不可能”变成“可接受”实现代码也比想象中简单但因为它不是这题最主流的解法我在这里只提一下思路后面重点讲 DP 和 bitset。3. 标准动态规划带偏移量的可达性数组3.1 状态定义必须带上偏移量从暴力法能很自然地过渡到 DP与其递归到叶子节点再统计不如用一个数组记录“处理完前 i 个砝码后哪些净重量可达”。但这里有个新手必踩的大坑净重量可能是负数。C 数组下标不能是负数所以不能直接开dp[重量]。解决办法是“偏移量”。设所有砝码总重量为 sum净重量的范围一定在 [-sum, sum] 之间。我们给下标统一加上一个偏移量 offset sum让实际重量 -sum 对应下标 0实际重量 0 对应下标 sum实际重量 sum 对应下标 2*sum。这样状态数组大小开到 2*sum 1所有负重量都有合法的数组下标。3.2 转移方程与滚动数组实现定义 dp[i][j] 表示处理完前 i 个砝码后能否到达实际重量 j - offset。每加入一个砝码 x旧状态 cur 可以转移到三个方向不放cur 不变放右盘cur x放左盘cur - x。因为会同时往两个方向加减所以不能用普通 0/1 背包那种“倒序循环防止重复使用”的方式最稳妥的做法是用一个临时数组做转移。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint w(n); int sum 0; for (int i 0; i n; i) { cin w[i]; sum w[i]; } int offset sum; vectorunsigned char dp(2 * sum 1, 0), ndp(2 * sum 1, 0); dp[offset] 1; for (int x : w) { fill(ndp.begin(), ndp.end(), 0); for (int j 0; j 2 * sum; j) { if (!dp[j]) continue; ndp[j] 1; // 不放砝码 if (j - x 0) ndp[j - x] 1; // 放物品侧重量减少 if (j x 2 * sum) ndp[j x] 1; // 放砝码侧重量增加 } dp.swap(ndp); } int ans 0; for (int j offset 1; j 2 * sum; j) { if (dp[j]) ans; } cout ans \n; return 0; }这里我用unsigned char而不是bool或vectorbool。原因有两个一是vectorbool内部是压位的直接if (!dp[j]) continue性能可能比普通数组慢一点还容易写出隐蔽错误二是unsigned char只占 1 字节省内存读写在大量循环里也很高效。最后统计答案时从offset 1开始也就是只统计实际重量大于 0 的状态这样自动把“净重量 0”也就是称不出任何重量的空状态排除在外。3.3 为什么“只做非负转移”会漏答案很多人写完 DP 后想优化既然最终只统计正重量那中间状态是不是只保留非负重量就够了比如只写if (j x) ndp[j - x] 1忽略 j - x 小于 0 的情况。这个想法看起来合理实际上会漏答案。我举一个反例砝码是 [5, 4, 4, 5]正确结果是能称出重量 2右盘放 5 和 5左盘放 4 和 4物品重量就是 10 - 8 2。如果按输入顺序逐一遍历符号组合是 5 -4 -4 5前缀重量依次是 5、1、-3、2中间某个时刻会跑到负数。一旦只做非负转移这个状态在第 3 个砝码时就被丢弃了后面再怎么加也回不来。所以处理正负贡献的 DP最稳妥的写法就是带偏移量让负数也有位置。这个点我在第一次做这题时踩过写出的答案错得莫名其妙后来对着反例手工模拟一遍才发现问题。4. bitset 优化一行转移背后的原理和坑4.1 用位运算同时更新所有状态如果 sum 比较大O(n * sum) 的 DP 可能卡在时间边缘这时候就该 bitset 上场了。bitset 的思路非常优雅用每一位表示一个状态“是否可达”位运算一次可以并行处理 64 个状态。同样带偏移量把实际重量 j - offset 映射到位 j初始化dp[offset] 1每加入一个砝码 x转移就是dp dp | (dp x) | (dp x);其中dp x表示所有状态都加上 x也就是砝码放右盘dp x表示所有状态都减去 x也就是砝码放左盘| dp表示不放该砝码。一个位运算同时完成了三种转移这就是 bitset 版 DP 的核心。需要说明的是bitset 的大小必须是编译期常量所以更通用的写法是直接开一个足够大的 MAXSconst int MAXS 200005; bitsetMAXS dp; dp[offset] 1; for (int x : w) { dp dp | (dp x) | (dp x); } int ans 0; for (int j offset 1; j offset sum; j) { if (dp[j]) ans; } cout ans \n;如果题目总重量范围更大std::bitset 不够灵活可以自己用vectorunsigned long long做压位原理一样就是手动实现左移右移和按位或。4.2 关键坑一条表达式和两条表达式天差地别这个坑我愿称之为“bitset 版砝码称重第一坑”。有些同学会写成dp | dp x; dp | dp x;这两行分开写结果完全错误。因为第一条语句执行完后dp已经被更新成“包含用过了这个砝码”的状态第二条语句又在新的dp基础上继续右移相当于同一个砝码被用了两次甚至更多次最后统计出的重量会明显偏大。对比一下背包问题里的“倒序更新”你会发现本质是同一个问题更新时要保证同一个物品不会被重复使用。bitset 版本必须把三种转移写在一个表达式里让它们都基于旧的dp计算或者用临时变量保存旧状态bitsetMAXS old dp; dp old | (old x) | (old x);4.3 经典一行转移为什么不带偏移也能过网上很多题解写的版本是不带偏移的bitsetN dp; dp[0] 1; for (int x : w) { dp dp | (dp x) | (dp x); }这个版本在某些测试数据下能过但严格来说是有问题的原因和 3.3 节完全一样它丢掉了中间为负、最终为正的合法路径。还是拿反例 [5, 4, 4, 5] 来说正确答案包含重量 2但不带偏移的 bitset 模拟出来的状态集合里根本没有 2。因为重量 2 对应的符号组合 5 -4 -4 5 在按输入顺序处理时中间会出现 -3而无偏移 bitset 的右移操作/会把位号移动到负数位置位号小于 0 就直接丢弃了这个状态就再也回不来了。所以带偏移量的 bitset 才是完整正确的写法。这也解释了为什么我强调“先理解 DP 再写优化”如果不懂偏移量的作用拿到一个 bitset 模板就抄遇到边界数据就会出问题而且非常难排查。5. 常见问题排查与提交经验5.1 排查清单速查表我把自己刷这道题以及帮别人 debug 时遇到的高频问题整理成了表格症状可能原因解决办法答案偏大同一个砝码在一个循环里被重复使用bitset 合并成一条表达式或用临时数组拷贝旧状态答案偏小没有处理负净重量状态加偏移量 offset让负数也有数组下标输出总是多 1把净重量 0 也统计进 ans统计时从 offset 1 开始或者dp.count() - 1后再对称处理内存溢出开了二维 bool 数组或者 vector 异常用滚动数组 unsigned char / bitset时间超限DFS 直接枚举 3^n或 O(n*sum) 在大数据下太慢换 bitset 压位或折半搜索5.2 自测数据这组用例建议背下来这里给出一组便于验证正确性的测试数据输入预期输出说明1 / 51只能称重量 52 / 1 231、2、3 都可以称出3 / 1 4 59包含 2 5 - 4 1 这种组合4 / 5 4 4 512注意重量 2 只能通过负中间态转移得到尤其是最后一组 [5, 4, 4, 5]专门用来检验你有没有踩“只做非负转移”的坑。如果你的程序输出 11 而不是 12多半就是负数状态被丢了。5.3 提交前的一些小贴士第一输入输出格式以题目为准。有的版本是一个测试用例有的版本是多组输入如果题目要求多组就把读入包在while (cin n)里每组重新初始化 dp。第二统计答案时不要依赖对称性简化。dp.count()算出的数量包含负重量、正重量和 0 三部分虽然正常情况下正负数量对称但边界截断可能破坏这个对称性。最稳的方法永远是显式统计offset 1到offset sum这段区间。第三如果使用std::bitset注意 MAXS 要比2 * sum 1大。某些题目的 sum 可能到几十万开小了会越界运行时不报错但结果全错。5.4 换一种问法解法怎么变砝码称重是一个非常经典的原型东华OJ里很多题都是它的变体理解了原型之后举一反三会很快。如果题目改成“判断能否称出某个指定重量 W”只需要判断dp[offset W]是否为 true。如果每个砝码有多个多重砝码可以用二进制拆分转成 0/1 背包或者按多重背包的二进制优化处理。如果砝码只能放右边那就退化成普通子集和一个一维 bool 数组倒序更新就能解决难度直接下降两档。如果题目要求输出所有方案那需要在 DP 之外额外记录转移路径或者直接用 meet-in-the-middle 枚举符号组合排序后输出对应组合复杂度也能接受。我个人在实际刷题中还有一个习惯先用 DP 数组版本把思路验证清楚再改成 bitset 优化版本提交。因为 bitset 虽然代码短但一旦出错调试起来比普通数组麻烦得多。先用慢而清晰的版本确认结果正确再用快版本冲时间这比一上来就写最优解更稳妥。盾神这道题表面上是在讲砝码称重实际上练的是“状态空间是否想全了”这个能力对后面做状压 DP、生成函数、背包变形题都特别有用。
盾神与砝码称重：从DP到bitset的状态空间优化全解析
东华OJ进阶系列里“盾神与砝码称重”这道题我刷完最大的感受是它不像表面看起来那么“入门”。题目背景很生活化——一个天平、一堆砝码、一个能“作弊”把砝码放物品同侧的盾神实际上考的是组合状态、背包思想和位运算优化是一道能把DP基础打得非常扎实的好题。很多第一次见到这题的人会直接想每个砝码要么不放要么放右边这不就是个普通子集和吗还真不是。这里最大的区别是砝码可以放物品同侧也就是可以“抵消”一部分重量这直接改变了整个状态模型。我把这个坑、正负状态处理、bitset 优化以及提交时容易踩的雷全部整理成一篇适合正在刷OJ、准备算法面试或者想系统搞懂“天平/称重类问题”的读者。1. 读懂题意这个题到底要算什么1.1 天平模型中的三种选择假设物品放在左盘砝码可以放右盘也可以放左盘还可以不放。天平平衡的条件是右盘砝码总重量 左盘砝码总重量 物品重量所以物品重量等于“右盘砝码和”减去“左盘砝码和”。对每个砝码来说它有三种贡献不放贡献 0放右盘贡献 w放左盘贡献 -w。题目要统计的是用这 n 个砝码每种砝码最多用一次一共能称出多少种不同的正整数重量。这就是“三种状态”和普通 0/1 背包“两种状态”的本质区别。如果用数学模型来描述就是给每个砝码赋一个系数 s_is_i 只能取 -1、0、1然后求所有可能的 ∑(s_i * w_i) 中有多少个不同的正数。1.2 为什么不是简单子集和很多同学第一次接触背包题会把这道题理解成“砝码只能放右边”那就退化成了经典子集和问题问能凑出哪些重量。这种情况一个砝码只有取或不取两种选择状态定义很简单一个一维 bool 数组倒着更新就能写完。但一旦砝码能放物品同侧问题性质就变了。砝码对最终重量的贡献可正可负最终结果不光是“相加”而是“做差”。我习惯把这个模型叫“子集差问题”每个砝码相当于一个可以取正、取负、取零的贡献值最终我们要统计所有符号组合的正值个数。举个例子砝码是 5 和 3除了能称 5、3、8 之外还能称 2因为右盘放 5左盘放 3物品重量就是 5 - 3 2。子集和模型完全覆盖不了这种情况。这也是这道题最值得玩味的地方一个“能不能把砝码放同侧”的设定变化把题目从入门背包直接拉到了需要认真考虑状态空间、偏移量和正负边界的中等题。1.3 选算法前先看数据范围刷OJ第一原则拿到题先看数据范围数据范围直接决定你该用哪种算法而不是一上来就写最优解法。我整理了大致的策略表数据规模可行方案时间复杂度n 15DFS 暴力枚举O(3^n)n 20 且总重量不大DFS 剪枝 / 折半搜索O(3^(n/2) log...)总重量 sum 2e5 左右带偏移量的动态规划O(n * sum)总重量 sum 更大bitset 位运算优化O(n * sum / 64) 左右实际OJ里这题常见的数据范围n 在几百到一千以内砝码重量累计和通常不超过 1e5 这个量级所以动态规划和 bitset 都能过。但理解暴力法和 DFS 依然很重要因为它是验证 DP 思路是否正确的最快方式。2. 暴力枚举先用 DFS 理解状态空间2.1 三叉树枚举所有状态组合如果 n 很小最直接的思路就是递归。每个砝码有三种选择我把它称为“三叉树”。走到最后一个砝码时当前累计的净重量如果是正数就丢进 set 里去重。#include bits/stdc.h using namespace std; int n; vectorint w; setint ans; void dfs(int idx, int cur) { if (idx n) { if (cur 0) ans.insert(cur); return; } dfs(idx 1, cur); // 不放 dfs(idx 1, cur w[idx]); // 放砝码侧 dfs(idx 1, cur - w[idx]); // 放物品侧 } int main() { cin n; w.resize(n); for (int i 0; i n; i) cin w[i]; dfs(0, 0); cout ans.size() endl; return 0; }这个代码的关键点是cur允许为负。因为实际称重时如果最终净重量是负数那只是左右盘互换的镜像情况对我们统计正整数重量没有影响所以我们只在叶子节点判断cur 0。2.2 set 去重与复杂度变化为什么用 set因为同一个正整数重量可能对应多种不同的砝码分配方案。比如砝码是 1、2、3重量 2 可以由砝码 2 单独称出也可以由右盘 3、左盘 1 称出3 - 1 2两种方式都合法但只能算一种重量。所以叶子节点不能直接计数必须去重。set 是最简单的去重工具代价是插入一次 O(log m)。n 比较小时这个开销无所谓但 n 到 15 以后3^15 ≈ 1400 万插入 set 也会明显变慢需要注意。2.3 暴力法的适用边界3^n 的复杂度增长非常快n 1059049随便跑n 1514348907勉强能跑n 203486784401完全不可行。所以纯 DFS 只适合 n 不超过 15 的场景或者作为验证用“对拍器”。如果 n 在 20 到 30 之间可以考虑折半搜索Meet in the Middle。思路是把砝码分成前后两半分别枚举所有符号组合得到两个数组 A 和 B每个数组的大小是 3^(n/2)。然后对 B 排序遍历 A 中的每个值 x在 B 里二分查找大于 -x 的元素个数累加就能统计出所有正重量数量。折半搜索可以把 n 30 左右的题从“不可能”变成“可接受”实现代码也比想象中简单但因为它不是这题最主流的解法我在这里只提一下思路后面重点讲 DP 和 bitset。3. 标准动态规划带偏移量的可达性数组3.1 状态定义必须带上偏移量从暴力法能很自然地过渡到 DP与其递归到叶子节点再统计不如用一个数组记录“处理完前 i 个砝码后哪些净重量可达”。但这里有个新手必踩的大坑净重量可能是负数。C 数组下标不能是负数所以不能直接开dp[重量]。解决办法是“偏移量”。设所有砝码总重量为 sum净重量的范围一定在 [-sum, sum] 之间。我们给下标统一加上一个偏移量 offset sum让实际重量 -sum 对应下标 0实际重量 0 对应下标 sum实际重量 sum 对应下标 2*sum。这样状态数组大小开到 2*sum 1所有负重量都有合法的数组下标。3.2 转移方程与滚动数组实现定义 dp[i][j] 表示处理完前 i 个砝码后能否到达实际重量 j - offset。每加入一个砝码 x旧状态 cur 可以转移到三个方向不放cur 不变放右盘cur x放左盘cur - x。因为会同时往两个方向加减所以不能用普通 0/1 背包那种“倒序循环防止重复使用”的方式最稳妥的做法是用一个临时数组做转移。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint w(n); int sum 0; for (int i 0; i n; i) { cin w[i]; sum w[i]; } int offset sum; vectorunsigned char dp(2 * sum 1, 0), ndp(2 * sum 1, 0); dp[offset] 1; for (int x : w) { fill(ndp.begin(), ndp.end(), 0); for (int j 0; j 2 * sum; j) { if (!dp[j]) continue; ndp[j] 1; // 不放砝码 if (j - x 0) ndp[j - x] 1; // 放物品侧重量减少 if (j x 2 * sum) ndp[j x] 1; // 放砝码侧重量增加 } dp.swap(ndp); } int ans 0; for (int j offset 1; j 2 * sum; j) { if (dp[j]) ans; } cout ans \n; return 0; }这里我用unsigned char而不是bool或vectorbool。原因有两个一是vectorbool内部是压位的直接if (!dp[j]) continue性能可能比普通数组慢一点还容易写出隐蔽错误二是unsigned char只占 1 字节省内存读写在大量循环里也很高效。最后统计答案时从offset 1开始也就是只统计实际重量大于 0 的状态这样自动把“净重量 0”也就是称不出任何重量的空状态排除在外。3.3 为什么“只做非负转移”会漏答案很多人写完 DP 后想优化既然最终只统计正重量那中间状态是不是只保留非负重量就够了比如只写if (j x) ndp[j - x] 1忽略 j - x 小于 0 的情况。这个想法看起来合理实际上会漏答案。我举一个反例砝码是 [5, 4, 4, 5]正确结果是能称出重量 2右盘放 5 和 5左盘放 4 和 4物品重量就是 10 - 8 2。如果按输入顺序逐一遍历符号组合是 5 -4 -4 5前缀重量依次是 5、1、-3、2中间某个时刻会跑到负数。一旦只做非负转移这个状态在第 3 个砝码时就被丢弃了后面再怎么加也回不来。所以处理正负贡献的 DP最稳妥的写法就是带偏移量让负数也有位置。这个点我在第一次做这题时踩过写出的答案错得莫名其妙后来对着反例手工模拟一遍才发现问题。4. bitset 优化一行转移背后的原理和坑4.1 用位运算同时更新所有状态如果 sum 比较大O(n * sum) 的 DP 可能卡在时间边缘这时候就该 bitset 上场了。bitset 的思路非常优雅用每一位表示一个状态“是否可达”位运算一次可以并行处理 64 个状态。同样带偏移量把实际重量 j - offset 映射到位 j初始化dp[offset] 1每加入一个砝码 x转移就是dp dp | (dp x) | (dp x);其中dp x表示所有状态都加上 x也就是砝码放右盘dp x表示所有状态都减去 x也就是砝码放左盘| dp表示不放该砝码。一个位运算同时完成了三种转移这就是 bitset 版 DP 的核心。需要说明的是bitset 的大小必须是编译期常量所以更通用的写法是直接开一个足够大的 MAXSconst int MAXS 200005; bitsetMAXS dp; dp[offset] 1; for (int x : w) { dp dp | (dp x) | (dp x); } int ans 0; for (int j offset 1; j offset sum; j) { if (dp[j]) ans; } cout ans \n;如果题目总重量范围更大std::bitset 不够灵活可以自己用vectorunsigned long long做压位原理一样就是手动实现左移右移和按位或。4.2 关键坑一条表达式和两条表达式天差地别这个坑我愿称之为“bitset 版砝码称重第一坑”。有些同学会写成dp | dp x; dp | dp x;这两行分开写结果完全错误。因为第一条语句执行完后dp已经被更新成“包含用过了这个砝码”的状态第二条语句又在新的dp基础上继续右移相当于同一个砝码被用了两次甚至更多次最后统计出的重量会明显偏大。对比一下背包问题里的“倒序更新”你会发现本质是同一个问题更新时要保证同一个物品不会被重复使用。bitset 版本必须把三种转移写在一个表达式里让它们都基于旧的dp计算或者用临时变量保存旧状态bitsetMAXS old dp; dp old | (old x) | (old x);4.3 经典一行转移为什么不带偏移也能过网上很多题解写的版本是不带偏移的bitsetN dp; dp[0] 1; for (int x : w) { dp dp | (dp x) | (dp x); }这个版本在某些测试数据下能过但严格来说是有问题的原因和 3.3 节完全一样它丢掉了中间为负、最终为正的合法路径。还是拿反例 [5, 4, 4, 5] 来说正确答案包含重量 2但不带偏移的 bitset 模拟出来的状态集合里根本没有 2。因为重量 2 对应的符号组合 5 -4 -4 5 在按输入顺序处理时中间会出现 -3而无偏移 bitset 的右移操作/会把位号移动到负数位置位号小于 0 就直接丢弃了这个状态就再也回不来了。所以带偏移量的 bitset 才是完整正确的写法。这也解释了为什么我强调“先理解 DP 再写优化”如果不懂偏移量的作用拿到一个 bitset 模板就抄遇到边界数据就会出问题而且非常难排查。5. 常见问题排查与提交经验5.1 排查清单速查表我把自己刷这道题以及帮别人 debug 时遇到的高频问题整理成了表格症状可能原因解决办法答案偏大同一个砝码在一个循环里被重复使用bitset 合并成一条表达式或用临时数组拷贝旧状态答案偏小没有处理负净重量状态加偏移量 offset让负数也有数组下标输出总是多 1把净重量 0 也统计进 ans统计时从 offset 1 开始或者dp.count() - 1后再对称处理内存溢出开了二维 bool 数组或者 vector 异常用滚动数组 unsigned char / bitset时间超限DFS 直接枚举 3^n或 O(n*sum) 在大数据下太慢换 bitset 压位或折半搜索5.2 自测数据这组用例建议背下来这里给出一组便于验证正确性的测试数据输入预期输出说明1 / 51只能称重量 52 / 1 231、2、3 都可以称出3 / 1 4 59包含 2 5 - 4 1 这种组合4 / 5 4 4 512注意重量 2 只能通过负中间态转移得到尤其是最后一组 [5, 4, 4, 5]专门用来检验你有没有踩“只做非负转移”的坑。如果你的程序输出 11 而不是 12多半就是负数状态被丢了。5.3 提交前的一些小贴士第一输入输出格式以题目为准。有的版本是一个测试用例有的版本是多组输入如果题目要求多组就把读入包在while (cin n)里每组重新初始化 dp。第二统计答案时不要依赖对称性简化。dp.count()算出的数量包含负重量、正重量和 0 三部分虽然正常情况下正负数量对称但边界截断可能破坏这个对称性。最稳的方法永远是显式统计offset 1到offset sum这段区间。第三如果使用std::bitset注意 MAXS 要比2 * sum 1大。某些题目的 sum 可能到几十万开小了会越界运行时不报错但结果全错。5.4 换一种问法解法怎么变砝码称重是一个非常经典的原型东华OJ里很多题都是它的变体理解了原型之后举一反三会很快。如果题目改成“判断能否称出某个指定重量 W”只需要判断dp[offset W]是否为 true。如果每个砝码有多个多重砝码可以用二进制拆分转成 0/1 背包或者按多重背包的二进制优化处理。如果砝码只能放右边那就退化成普通子集和一个一维 bool 数组倒序更新就能解决难度直接下降两档。如果题目要求输出所有方案那需要在 DP 之外额外记录转移路径或者直接用 meet-in-the-middle 枚举符号组合排序后输出对应组合复杂度也能接受。我个人在实际刷题中还有一个习惯先用 DP 数组版本把思路验证清楚再改成 bitset 优化版本提交。因为 bitset 虽然代码短但一旦出错调试起来比普通数组麻烦得多。先用慢而清晰的版本确认结果正确再用快版本冲时间这比一上来就写最优解更稳妥。盾神这道题表面上是在讲砝码称重实际上练的是“状态空间是否想全了”这个能力对后面做状压 DP、生成函数、背包变形题都特别有用。
