多重背包朴素做法因拆分数量过大导致超时，二进制拆分通过幂次分解将每类物品压缩至O(log c[i])项，再用逆序0-1背包求解，关键需正确计算余数并严格倒序更新dp。
为什么多重背包直接做会超时
多重背包的朴素做法是把每个物品拆成 c[i] 个单独的 0-1 背包项，时间复杂度变成 O(V × Σc[i])，当某个 c[i] 达到 10⁵ 级别时，光拆分就卡死。二进制拆分本质是用“倍增思想”压缩数量：把 c[i] 拆成若干个 2 的幂次（1, 2, 4, ..., 2ᵏ）加一个余数，总项数降到 O(log c[i]) 级别。
怎么拆分才能不漏组合
对第 i 个物品，数量为 c，按以下方式拆：
- 取
k = 0开始，只要2^k ≤ c，就生成一个新物品：重量w[i] × 2^k，价值v[i] × 2^k - 最后剩下一个余数
r = c − (2^0 + 2^1 + ... + 2^{k−1}) = c − (2^k − 1)，若r > 0，再加一个物品：重量w[i] × r，价值v[i] × r - 这样任意
0 ~ c个该物品的组合，都能被这些新物品的子集和唯一表示（二进制表示原理）
拆完之后怎么跑 0-1 背包
拆出来的所有新物品，和原问题中其他物品一起，当作标准 0-1 背包处理。注意：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 必须用**逆序循环**更新
dp[j]（从V到weight），否则会重复选取同一拆分项 - 不能用完全背包的正序写法，因为每个拆分项只能选 0 或 1 次
- 空间上仍可用一维
dp[0..V]，无需二维
for (int i = 0; i < n; i++) {
int c = cnt[i], w = weight[i], v = value[i];
for (int k = 1; k <= c; k *= 2) {
// 拆出 2^k 份
int nw = w * k, nv = v * k;
for (int j = V; j >= nw; j--) {
dp[j] = max(dp[j], dp[j - nw] + nv);
}
c -= k;
}
if (c > 0) { // 余数
int nw = w * c, nv = v * c;
for (int j = V; j >= nw; j--) {
dp[j] = max(dp[j], dp[j - nw] + nv);
}
}
}
容易错在哪几个地方
实际编码时高频翻车点：
立即学习“C++免费学习笔记（深入）”；
- 拆分循环里没及时更新
c，导致余数计算错误或重复拆分 - 内层背包循环方向写成正序（
for (j = nw; j ），结果变成完全背包语义 - 把拆分后的重量/价值算错，比如写成
w + k而不是w * k - 忽略数据范围：拆分后总物品数约
Σ log₂(c[i])，但若V很大（如 1e5），而n拆完有 1e4 项，O(n′ × V)可能仍超时，这时得换单调队列优化
二进制拆分不是万能银弹——它只解决“数量大但种类少”的情况；如果所有 c[i] 都是 1，它退化为 0-1 背包；如果所有 c[i] 都极大且 V 也极大，就得考虑更重的优化手段。
