1. 从一道题看多重背包的本质困境第一次在题库里刷到kirito这道题的时候我盯着题目看了半天脑子里第一反应是这不就是个背包吗但仔细读完题面才发现它给的不是每种物品一件而是每种物品有有限个数量每个还有自己的价值。这就是典型的多重背包问题。多重背包的核心矛盾在于每种物品有 $n_i$ 件每件重量 $w_i$、价值 $v_i$背包容量为 $W$要在不超过容量的前提下最大化总价值。最朴素的想法是把每件物品都当成独立的01背包物品来处理——比如某种物品有5件就拆成5个独立的物品每个只能选或不选。这样做逻辑上完全正确但复杂度是 $O(W \times \sum n_i)$。如果某种物品有1000件背包容量又是10000那这个数量级直接爆炸。我在实际做题时踩过的第一个坑就是以为把多重背包拆成01背包就万事大吉了。小数据能过一旦数据量上去TLE超时是必然的。后来才意识到问题的关键在于拆的方式——暴力拆成 $n_i$ 个1和用二进制拆分拆成 $\log n_i$ 个捆绑包效率差了整整一个数量级。这道题之所以经典是因为它逼着你去思考如何用最少的物品数量表达出0到 $n_i$ 之间所有可能的选取数量。二进制优化就是回答这个问题的钥匙。2. 二进制拆分到底在拆什么2.1 用砝码称重理解二进制拆分先抛开代码用一个生活场景来解释。假设你有一堆砝码要能称出1到15克之间任意整数克的重量最少需要几个砝码答案是4个1克、2克、4克、8克。为什么因为1到15的二进制表示正好需要4位每一位对应一个砝码。112231244514……151248。每个砝码只有用或不用两种状态组合起来就能覆盖所有整数。二进制拆分就是这个道理。某种物品有 $n_i$ 件我不需要拆成 $n_i$ 个独立物品而是拆成若干个捆绑包1件、2件、4件、8件……直到剩余不足2的幂次时把剩下的全部打包成一个包。举个具体的例子某种物品有13件重量为 $w$价值为 $v$第1个包1件重量 $w$价值 $v$第2个包2件重量 $2w$价值 $2v$第3个包4件重量 $4w$价值 $4v$第4个包6件13-1-2-46重量 $6w$价值 $6v$这四个包通过选或不选可以组合出0到13之间的任意件数。比如选7件就是16选11件就是128等等这里没有8是14611。验证一下1、2、4、6这四个数任意子集和能覆盖0到13吗0,1,2,3(12),4,5(14),6,7(16),8(26),9(126),10(46),11(146),12(246),13(1246)——全覆盖没问题。2.2 为什么拆成1、2、4、8……而不是其他组合这里有个容易忽略的细节二进制拆分的正确性依赖于每个包只能选一次这个前提。因为拆出来的包本质上是01背包的物品每个包要么选要么不选。而1、2、4、8这种2的幂次序列配合最后那个余数包恰好能保证任意数量都能被唯一表示在不超过总数的情况下。如果拆成1、1、1、1……那就退化成了暴力拆分失去了优化的意义。如果拆成1、3、5、7这种奇数序列虽然也能覆盖某些数量但无法保证覆盖所有整数会出现凑不出某个件数的情况。我在调试时遇到过一个经典错误忘记处理最后的余数包。比如13件物品拆成1、2、4之后还剩6件如果直接丢掉这6件那么选取8到13件的情况就全部丢失了答案自然错误。正确的做法是把剩余的6件作为一个独立的包加进去。2.3 拆分后的复杂度分析拆分前某种物品有 $n_i$ 件需要处理 $n_i$ 次。拆分后只需要处理 $\lceil \log_2(n_i1) \rceil$ 个包。对于 $n_i 1000$拆分前是1000次拆分后大约是10个包效率提升100倍。整体复杂度从 $O(W \times \sum n_i)$ 降到 $O(W \times \sum \log n_i)$。在 $W10000$、物品种类100、每种1000件的情况下暴力拆分是 $10^9$ 级别二进制拆分只有 $10^7$ 级别差距非常明显。3. 把多重背包写成01背包的完整实操3.1 数据读入与拆分逻辑拿到题目后第一步是读入物品种类数 $N$ 和背包容量 $W$然后对每种物品进行二进制拆分把所有拆出来的包存到一个新的列表中。这个列表里的每个元素就是一个01背包物品有重量和价值两个属性。拆分的核心逻辑是这样的对于数量 $n$从 $k1$ 开始每次取 $k$然后 $n$ 减去 $k$$k$ 乘以2直到 $n k$最后把剩余的 $n$ 作为一个包。用伪代码描述k 1 while n 0: take min(k, n) 生成一个包重量 take * w价值 take * v n - take k * 2注意这里的min(k, n)就是处理余数的关键。当 $n$ 不足以再拿出 $k$ 件时把剩下的全部拿走。3.2 01背包的一维数组写法拆分完成后问题就变成了标准的01背包。我用的是一维数组倒序遍历的写法这是最经典的01背包实现方式for (int i 0; i packages.size(); i) { int pw packages[i].weight; int pv packages[i].value; for (int j W; j pw; j--) { dp[j] max(dp[j], dp[j - pw] pv); } }这里有个必须强调的点内层循环必须从大到小遍历。为什么因为01背包要求每个物品只能选一次。如果从小到大遍历$dp[j]$ 会被当前物品多次更新相当于变成了完全背包每种物品无限件。从大到小遍历时$dp[j-pw]$ 还是上一轮的状态保证了每个包只被考虑一次。我见过不少初学者在这里翻车拆分逻辑写得完全正确但内层循环方向搞反了结果答案偏大因为物品被重复使用了。3.3 边界条件与初始化$dp$ 数组的大小是 $W1$初始值全部为0。这表示容量为 $j$ 时能获得的最大价值。如果题目要求恰好装满那 $dp[0]0$其余为负无穷如果只要求不超过容量全部初始化为0即可。这道题属于后者所以直接全0初始化。最终答案是 $dp[W]$表示容量不超过 $W$ 时的最大价值。还有一个容易忽略的边界如果某种物品的数量为0拆分逻辑应该直接跳过不生成任何包。虽然题目一般不会给0但写代码时加个判断更稳妥。4. 那些年我在多重背包上踩过的坑4.1 拆分数组开太小导致越界二进制拆分后包的数量大约是 $\sum \log n_i$。如果物品种类有100种每种最多1000件那么包的总数大约是 $100 \times 10 1000$ 个。但有些题目的数据范围更大比如每种物品最多 $2^{31}-1$ 件那 $\log$ 之后大约是31个包100种就是3100个包。我一开始习惯性地把包数组开成和物品种类一样大结果直接越界。后来养成了习惯包数组的大小至少开到 $\sum \log_2(n_i1)$ 的上界保险起见可以开到物品种类数乘以32。4.2 内层循环下界写错01背包的内层循环下界是 $pw$即当前包的重量的。如果写成0虽然不会出错因为 $j-pw$ 为负数时数组越界但会多跑很多无用的循环。更严重的是如果写成 $j \geq 0$ 并且没有判断 $j \geq pw$直接访问 $dp[j-pw]$ 会导致数组下标为负程序崩溃。正确的写法是for (int j W; j pw; j--)这样 $j-pw$ 始终非负。4.3 混淆了多重背包和完全背包完全背包是每种物品无限件内层循环从小到大多重背包是每种物品有限件二进制拆分后内层循环从大到小。这两个的循环方向刚好相反我在初学阶段经常搞混。一个简单的记忆方法01背包包括拆分后的多重背包从大到小完全背包从小到大。因为01背包要保证每个物品只用一次从大到小遍历时前面的状态还没被当前物品污染完全背包允许重复使用从小到大遍历正好利用了已经更新的状态。4.4 价值为负或重量为0的特殊情况有些变种题目会出现价值为负的物品或者重量为0的物品。重量为0的物品在01背包中需要特殊处理如果价值为正直接无条件加入答案如果价值为负直接丢弃。因为重量为0意味着不占容量选它不影响其他物品。这道题没有这种特殊情况但作为经验遇到变种题目时要先判断这些边界。5. 从kirito这道题延伸出的优化思路5.1 单调队列优化另一种解法二进制优化把多重背包转化成了01背包复杂度是 $O(W \times \sum \log n_i)$。还有一种更高级的解法是单调队列优化可以把复杂度降到 $O(W \times N)$其中 $N$ 是物品种类数。单调队列的思路是按重量对容量进行分类对于同余类中的状态用滑动窗口维护最大值。这个解法实现起来比二进制拆分复杂不少但在数据量极大时优势明显。不过对于大多数题目来说二进制优化已经足够没必要过度设计。5.2 混合背包的处理有些题目会混合01背包、完全背包和多重背包。这时候可以分别处理01背包用倒序循环完全背包用正序循环多重背包二进制拆分后用倒序循环。三种情况分开写逻辑清晰不容易出错。我在做混合背包题时习惯把三种物品分别存到三个列表里然后依次处理。这样代码可读性更好调试也方便。5.3 空间优化的取舍一维数组的01背包已经把空间优化到了 $O(W)$这是最优的空间复杂度。如果题目对空间没有特殊要求也可以用二维数组但没必要。一维数组的倒序遍历写法已经非常成熟只要注意循环方向就不会出错。6. 完整代码实现与逐行注释#include bits/stdc.h using namespace std; struct Package { int weight; int value; }; int main() { int N, W; cin N W; vectorPackage packages; for (int i 0; i N; i) { int w, v, n; cin w v n; // 二进制拆分 int k 1; while (n 0) { int take min(k, n); packages.push_back({take * w, take * v}); n - take; k * 2; } } // 01背包 vectorint dp(W 1, 0); for (auto pkg : packages) { for (int j W; j pkg.weight; j--) { dp[j] max(dp[j], dp[j - pkg.weight] pkg.value); } } cout dp[W] endl; return 0; }这段代码的核心就是两个部分拆分和01背包。拆分部分用while循环不断取出2的幂次直到剩余数量为0。01背包部分用倒序遍历保证每个包只选一次。我在实际提交时把packages用vector动态存储避免了数组大小估算错误的问题。如果题目数据范围已知也可以用静态数组但vector更灵活。7. 调试技巧与验证方法7.1 用小数据手动验证写完代码后我习惯先用一组小数据手动跑一遍。比如物品种类1种重量2价值3数量5背包容量10拆分后得到包1件(2,3)、2件(4,6)、2件(4,6)。注意这里5拆成122因为5-144-22最后剩2。然后手动模拟01背包过程看最终答案是否是12选5件重量10价值15不对5件重量是10价值是15但容量是10所以答案是15。等等5件物品重量是 $5 \times 2 10$价值是 $5 \times 3 15$容量10刚好装下答案是15。用代码跑一遍验证。7.2 对拍验证如果时间允许我会写一个暴力版本直接把每件物品当01背包处理和一个优化版本二进制拆分用随机数据对拍。如果两个版本答案一致说明拆分逻辑正确。暴力版本虽然慢但逻辑简单不容易出错是验证优化版本的好工具。7.3 边界数据测试背包容量为0答案应该是0所有物品重量都大于容量答案应该是0某种物品数量为1退化成01背包某种物品数量极大测试拆分是否正确这些边界情况能覆盖大部分潜在bug。8. 多重背包在实际问题中的映射多重背包不仅仅是一道算法题它在实际场景中有很多对应。比如资源分配你有若干种资源每种有有限的数量要在预算内最大化收益。又比如货物装载每种货物有若干件每件有重量和价值要在载重限制下最大化价值。二进制优化的思想也可以迁移到其他问题。比如在有限次操作的场景中如果某个操作可以执行 $n$ 次每次效果相同就可以用二进制拆分把 $n$ 次操作压缩成 $\log n$ 个批量操作从而降低状态空间。我在做一个任务调度的小工具时就用了类似的思想某个任务可以重复执行多次每次消耗相同资源我把重复次数做了二进制拆分把状态数从 $O(n)$ 降到了 $O(\log n)$程序跑起来快了很多。这种用二进制表示数量的技巧本质上是用信息论的思路压缩状态空间。任何有限次重复的场景都可以考虑用这种方式优化。9. 关于这道题的一些个人体会kirito这道题本身并不复杂但它是理解多重背包和二进制优化的绝佳入口。我建议初学者不要一上来就看题解而是先自己尝试暴力拆分感受一下超时的痛苦然后再去理解二进制优化的精妙之处。这种先撞墙再找路的学习方式比直接看答案印象深刻得多。另外二进制拆分的代码虽然短但细节很多余数包的处理、循环方向、数组大小每一个都可能成为bug的来源。我在教别人的时候发现大多数人第一次写都会在某个细节上翻车这很正常多写几遍就熟了。最后说一个我自己的习惯每次写完背包类题目我都会把 $dp$ 数组打印出来看看确认状态转移的过程符合预期。这个习惯帮我发现过好几次循环方向写反的问题。对于动态规划类题目能看到中间状态比只看最终答案更有助于调试。 
长河君 · 2026/10/6 10:05:53 · 阅读 1.2k 多重背包二进制优化：从kirito题解到01背包实战
1. 从一道题看多重背包的本质困境第一次在题库里刷到kirito这道题的时候我盯着题目看了半天脑子里第一反应是这不就是个背包吗但仔细读完题面才发现它给的不是每种物品一件而是每种物品有有限个数量每个还有自己的价值。这就是典型的多重背包问题。多重背包的核心矛盾在于每种物品有 $n_i$ 件每件重量 $w_i$、价值 $v_i$背包容量为 $W$要在不超过容量的前提下最大化总价值。最朴素的想法是把每件物品都当成独立的01背包物品来处理——比如某种物品有5件就拆成5个独立的物品每个只能选或不选。这样做逻辑上完全正确但复杂度是 $O(W \times \sum n_i)$。如果某种物品有1000件背包容量又是10000那这个数量级直接爆炸。我在实际做题时踩过的第一个坑就是以为把多重背包拆成01背包就万事大吉了。小数据能过一旦数据量上去TLE超时是必然的。后来才意识到问题的关键在于拆的方式——暴力拆成 $n_i$ 个1和用二进制拆分拆成 $\log n_i$ 个捆绑包效率差了整整一个数量级。这道题之所以经典是因为它逼着你去思考如何用最少的物品数量表达出0到 $n_i$ 之间所有可能的选取数量。二进制优化就是回答这个问题的钥匙。2. 二进制拆分到底在拆什么2.1 用砝码称重理解二进制拆分先抛开代码用一个生活场景来解释。假设你有一堆砝码要能称出1到15克之间任意整数克的重量最少需要几个砝码答案是4个1克、2克、4克、8克。为什么因为1到15的二进制表示正好需要4位每一位对应一个砝码。112231244514……151248。每个砝码只有用或不用两种状态组合起来就能覆盖所有整数。二进制拆分就是这个道理。某种物品有 $n_i$ 件我不需要拆成 $n_i$ 个独立物品而是拆成若干个捆绑包1件、2件、4件、8件……直到剩余不足2的幂次时把剩下的全部打包成一个包。举个具体的例子某种物品有13件重量为 $w$价值为 $v$第1个包1件重量 $w$价值 $v$第2个包2件重量 $2w$价值 $2v$第3个包4件重量 $4w$价值 $4v$第4个包6件13-1-2-46重量 $6w$价值 $6v$这四个包通过选或不选可以组合出0到13之间的任意件数。比如选7件就是16选11件就是128等等这里没有8是14611。验证一下1、2、4、6这四个数任意子集和能覆盖0到13吗0,1,2,3(12),4,5(14),6,7(16),8(26),9(126),10(46),11(146),12(246),13(1246)——全覆盖没问题。2.2 为什么拆成1、2、4、8……而不是其他组合这里有个容易忽略的细节二进制拆分的正确性依赖于每个包只能选一次这个前提。因为拆出来的包本质上是01背包的物品每个包要么选要么不选。而1、2、4、8这种2的幂次序列配合最后那个余数包恰好能保证任意数量都能被唯一表示在不超过总数的情况下。如果拆成1、1、1、1……那就退化成了暴力拆分失去了优化的意义。如果拆成1、3、5、7这种奇数序列虽然也能覆盖某些数量但无法保证覆盖所有整数会出现凑不出某个件数的情况。我在调试时遇到过一个经典错误忘记处理最后的余数包。比如13件物品拆成1、2、4之后还剩6件如果直接丢掉这6件那么选取8到13件的情况就全部丢失了答案自然错误。正确的做法是把剩余的6件作为一个独立的包加进去。2.3 拆分后的复杂度分析拆分前某种物品有 $n_i$ 件需要处理 $n_i$ 次。拆分后只需要处理 $\lceil \log_2(n_i1) \rceil$ 个包。对于 $n_i 1000$拆分前是1000次拆分后大约是10个包效率提升100倍。整体复杂度从 $O(W \times \sum n_i)$ 降到 $O(W \times \sum \log n_i)$。在 $W10000$、物品种类100、每种1000件的情况下暴力拆分是 $10^9$ 级别二进制拆分只有 $10^7$ 级别差距非常明显。3. 把多重背包写成01背包的完整实操3.1 数据读入与拆分逻辑拿到题目后第一步是读入物品种类数 $N$ 和背包容量 $W$然后对每种物品进行二进制拆分把所有拆出来的包存到一个新的列表中。这个列表里的每个元素就是一个01背包物品有重量和价值两个属性。拆分的核心逻辑是这样的对于数量 $n$从 $k1$ 开始每次取 $k$然后 $n$ 减去 $k$$k$ 乘以2直到 $n k$最后把剩余的 $n$ 作为一个包。用伪代码描述k 1 while n 0: take min(k, n) 生成一个包重量 take * w价值 take * v n - take k * 2注意这里的min(k, n)就是处理余数的关键。当 $n$ 不足以再拿出 $k$ 件时把剩下的全部拿走。3.2 01背包的一维数组写法拆分完成后问题就变成了标准的01背包。我用的是一维数组倒序遍历的写法这是最经典的01背包实现方式for (int i 0; i packages.size(); i) { int pw packages[i].weight; int pv packages[i].value; for (int j W; j pw; j--) { dp[j] max(dp[j], dp[j - pw] pv); } }这里有个必须强调的点内层循环必须从大到小遍历。为什么因为01背包要求每个物品只能选一次。如果从小到大遍历$dp[j]$ 会被当前物品多次更新相当于变成了完全背包每种物品无限件。从大到小遍历时$dp[j-pw]$ 还是上一轮的状态保证了每个包只被考虑一次。我见过不少初学者在这里翻车拆分逻辑写得完全正确但内层循环方向搞反了结果答案偏大因为物品被重复使用了。3.3 边界条件与初始化$dp$ 数组的大小是 $W1$初始值全部为0。这表示容量为 $j$ 时能获得的最大价值。如果题目要求恰好装满那 $dp[0]0$其余为负无穷如果只要求不超过容量全部初始化为0即可。这道题属于后者所以直接全0初始化。最终答案是 $dp[W]$表示容量不超过 $W$ 时的最大价值。还有一个容易忽略的边界如果某种物品的数量为0拆分逻辑应该直接跳过不生成任何包。虽然题目一般不会给0但写代码时加个判断更稳妥。4. 那些年我在多重背包上踩过的坑4.1 拆分数组开太小导致越界二进制拆分后包的数量大约是 $\sum \log n_i$。如果物品种类有100种每种最多1000件那么包的总数大约是 $100 \times 10 1000$ 个。但有些题目的数据范围更大比如每种物品最多 $2^{31}-1$ 件那 $\log$ 之后大约是31个包100种就是3100个包。我一开始习惯性地把包数组开成和物品种类一样大结果直接越界。后来养成了习惯包数组的大小至少开到 $\sum \log_2(n_i1)$ 的上界保险起见可以开到物品种类数乘以32。4.2 内层循环下界写错01背包的内层循环下界是 $pw$即当前包的重量的。如果写成0虽然不会出错因为 $j-pw$ 为负数时数组越界但会多跑很多无用的循环。更严重的是如果写成 $j \geq 0$ 并且没有判断 $j \geq pw$直接访问 $dp[j-pw]$ 会导致数组下标为负程序崩溃。正确的写法是for (int j W; j pw; j--)这样 $j-pw$ 始终非负。4.3 混淆了多重背包和完全背包完全背包是每种物品无限件内层循环从小到大多重背包是每种物品有限件二进制拆分后内层循环从大到小。这两个的循环方向刚好相反我在初学阶段经常搞混。一个简单的记忆方法01背包包括拆分后的多重背包从大到小完全背包从小到大。因为01背包要保证每个物品只用一次从大到小遍历时前面的状态还没被当前物品污染完全背包允许重复使用从小到大遍历正好利用了已经更新的状态。4.4 价值为负或重量为0的特殊情况有些变种题目会出现价值为负的物品或者重量为0的物品。重量为0的物品在01背包中需要特殊处理如果价值为正直接无条件加入答案如果价值为负直接丢弃。因为重量为0意味着不占容量选它不影响其他物品。这道题没有这种特殊情况但作为经验遇到变种题目时要先判断这些边界。5. 从kirito这道题延伸出的优化思路5.1 单调队列优化另一种解法二进制优化把多重背包转化成了01背包复杂度是 $O(W \times \sum \log n_i)$。还有一种更高级的解法是单调队列优化可以把复杂度降到 $O(W \times N)$其中 $N$ 是物品种类数。单调队列的思路是按重量对容量进行分类对于同余类中的状态用滑动窗口维护最大值。这个解法实现起来比二进制拆分复杂不少但在数据量极大时优势明显。不过对于大多数题目来说二进制优化已经足够没必要过度设计。5.2 混合背包的处理有些题目会混合01背包、完全背包和多重背包。这时候可以分别处理01背包用倒序循环完全背包用正序循环多重背包二进制拆分后用倒序循环。三种情况分开写逻辑清晰不容易出错。我在做混合背包题时习惯把三种物品分别存到三个列表里然后依次处理。这样代码可读性更好调试也方便。5.3 空间优化的取舍一维数组的01背包已经把空间优化到了 $O(W)$这是最优的空间复杂度。如果题目对空间没有特殊要求也可以用二维数组但没必要。一维数组的倒序遍历写法已经非常成熟只要注意循环方向就不会出错。6. 完整代码实现与逐行注释#include bits/stdc.h using namespace std; struct Package { int weight; int value; }; int main() { int N, W; cin N W; vectorPackage packages; for (int i 0; i N; i) { int w, v, n; cin w v n; // 二进制拆分 int k 1; while (n 0) { int take min(k, n); packages.push_back({take * w, take * v}); n - take; k * 2; } } // 01背包 vectorint dp(W 1, 0); for (auto pkg : packages) { for (int j W; j pkg.weight; j--) { dp[j] max(dp[j], dp[j - pkg.weight] pkg.value); } } cout dp[W] endl; return 0; }这段代码的核心就是两个部分拆分和01背包。拆分部分用while循环不断取出2的幂次直到剩余数量为0。01背包部分用倒序遍历保证每个包只选一次。我在实际提交时把packages用vector动态存储避免了数组大小估算错误的问题。如果题目数据范围已知也可以用静态数组但vector更灵活。7. 调试技巧与验证方法7.1 用小数据手动验证写完代码后我习惯先用一组小数据手动跑一遍。比如物品种类1种重量2价值3数量5背包容量10拆分后得到包1件(2,3)、2件(4,6)、2件(4,6)。注意这里5拆成122因为5-144-22最后剩2。然后手动模拟01背包过程看最终答案是否是12选5件重量10价值15不对5件重量是10价值是15但容量是10所以答案是15。等等5件物品重量是 $5 \times 2 10$价值是 $5 \times 3 15$容量10刚好装下答案是15。用代码跑一遍验证。7.2 对拍验证如果时间允许我会写一个暴力版本直接把每件物品当01背包处理和一个优化版本二进制拆分用随机数据对拍。如果两个版本答案一致说明拆分逻辑正确。暴力版本虽然慢但逻辑简单不容易出错是验证优化版本的好工具。7.3 边界数据测试背包容量为0答案应该是0所有物品重量都大于容量答案应该是0某种物品数量为1退化成01背包某种物品数量极大测试拆分是否正确这些边界情况能覆盖大部分潜在bug。8. 多重背包在实际问题中的映射多重背包不仅仅是一道算法题它在实际场景中有很多对应。比如资源分配你有若干种资源每种有有限的数量要在预算内最大化收益。又比如货物装载每种货物有若干件每件有重量和价值要在载重限制下最大化价值。二进制优化的思想也可以迁移到其他问题。比如在有限次操作的场景中如果某个操作可以执行 $n$ 次每次效果相同就可以用二进制拆分把 $n$ 次操作压缩成 $\log n$ 个批量操作从而降低状态空间。我在做一个任务调度的小工具时就用了类似的思想某个任务可以重复执行多次每次消耗相同资源我把重复次数做了二进制拆分把状态数从 $O(n)$ 降到了 $O(\log n)$程序跑起来快了很多。这种用二进制表示数量的技巧本质上是用信息论的思路压缩状态空间。任何有限次重复的场景都可以考虑用这种方式优化。9. 关于这道题的一些个人体会kirito这道题本身并不复杂但它是理解多重背包和二进制优化的绝佳入口。我建议初学者不要一上来就看题解而是先自己尝试暴力拆分感受一下超时的痛苦然后再去理解二进制优化的精妙之处。这种先撞墙再找路的学习方式比直接看答案印象深刻得多。另外二进制拆分的代码虽然短但细节很多余数包的处理、循环方向、数组大小每一个都可能成为bug的来源。我在教别人的时候发现大多数人第一次写都会在某个细节上翻车这很正常多写几遍就熟了。最后说一个我自己的习惯每次写完背包类题目我都会把 $dp$ 数组打印出来看看确认状态转移的过程符合预期。这个习惯帮我发现过好几次循环方向写反的问题。对于动态规划类题目能看到中间状态比只看最终答案更有助于调试。