分组背包“每组至多选一个”的状态转移需外层遍历组、中层倒序遍历容量j（w→w[i]）、内层枚举本组物品i，用dp[j]=max(dp[j], dp[j−w[i]]+v[i])；倒序保证依赖的是上一组或本组未更新的状态，避免同组多选。
分组背包问题中“每组至多选一个”的状态转移怎么写
核心就是：对每组物品，单独做一次「0-1 背包」式的更新，且必须用**滚动数组从后往前**遍历容量，同时在组内枚举所有物品时，**不跨组复用当前组的更新结果**。
常见错误是把组内循环写成正向遍历，或者在同一个 dp[j] 上连续尝试多个同组物品——这会变相允许选多个。
- 正确做法：外层遍历组，中层倒序遍历容量
j（从W到w[i]），内层遍历该组每个物品i，用dp[j] = max(dp[j], dp[j - w[i]] + v[i]) - 关键约束靠「倒序遍历」保证：每次更新
dp[j]时，依赖的dp[j - w[i]]来自上一组或本组未更新的状态，不会受本组前面物品的影响 - 如果想严格限制「恰好选一个」（而非至多一个），需额外维护一个辅助数组或改用二维 DP，但绝大多数场景只需「至多一个」
为什么不能直接套用完全背包的正向遍历
因为完全背包正向遍历 j 的本质是：允许重复使用同一物品；而分组背包中，同一组不同物品之间是互斥关系——选了 A 就不能再选 B，哪怕它们体积价值不同。
一旦用正向遍历，比如组内有物品 (w=2,v=3) 和 (w=3,v=5)，容量 j=5 时可能先用第一个更新出 dp[5] = dp[3] + 3，再用第二个基于刚更新的 dp[5] 去算 dp[5] = max(dp[5], dp[2] + 5)，这就隐含了「两个都选」的路径（只要容量够），破坏分组约束。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 正向遍历 → 状态可被同组多个物品叠加影响 → 违反「每组至多一个」
- 倒序遍历 → 每次
dp[j]只依赖未被本组更新过的旧值 → 组内物品彼此独立比较，最终取最优那一个
C++ 实现时容易漏掉的初始化和边界
很多人只关注转移逻辑，却在初始化上栽跟头：若要求「恰好装满」，dp[0] 初始化为 0，其余为负无穷；若只是「不超过容量的最大价值」，则全部初始化为 0 即可。这个选择直接影响结果是否合法。
- 忘记将
dp数组初始化为负无穷（如-0x3f3f3f3f）会导致无法装满时返回错误的 0（实际应不可行） - 组内物品枚举前没检查
w[i] ，导致数组越界或无效更新 - 误把组号循环和物品循环嵌套反了：必须是「组 → 容量 → 组内物品」，反过来就变成多重背包了
vector<int> dp(W + 1, 0); // 不要求恰好装满
for (const auto& group : groups) {
for (int j = W; j >= 0; --j) { // 倒序
for (const auto& item : group) {
if (item.w <h3>当组内物品数量大或有额外约束时怎么办</h3>
<p>纯暴力枚举组内物品时间复杂度是 O(组数 × 容量 × 组大小)，如果某组有上千个物品，会超时。这时需要预处理：对该组做一次内部 0-1 背包，压缩成「容量→最大价值」的映射，再整体合并——但注意，这仅适用于组内物品可任意组合（即你其实想解的是「组内子背包 + 组间分组背包」），而原题明确要求「每组只能选一个」，所以不能压缩，必须保留单物品粒度。</p>
<ul>
<li>真正能优化的点只有：提前排序组内物品，按重量升序，遇到 <code>w[i] > j</code> 就 break；或用 vector.reserve 避免频繁扩容</li>
<li>如果组内还有依赖关系（比如选了 A 就不能选 B），那就不再是标准分组背包，得建图或加维度，DP 状态要扩展</li>
<li>多维限制（如体积+重量双约束）时，滚动数组变成二维，倒序逻辑要同步拓展到两个维度，极易出错</li>
</ul>
<p>最易被忽略的是：分组背包的「组」必须是逻辑上互斥的集合，代码里如果 group[i] 是空 vector，不加判断就会跳过整轮更新，但有时空组意味着“该组不允许选”，有时又表示“该组无可用物品”，语义必须和业务对齐。</p></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
