1. 分组背包问题概述分组背包问题是动态规划中一个经典变种它扩展了传统0-1背包问题的约束条件。在实际开发中我经常遇到需要从多个互斥的选项组中选择最优组合的场景比如广告投放策略选择、课程选修方案设计等。这类问题的核心特征是物品被划分为若干组每组内的物品相互冲突最多只能选择其中一个。与基础背包问题相比分组背包的决策维度从单个物品升级到了物品组。这种约束在实际业务中非常常见——比如电商促销时同一品类的优惠券往往只能选一张使用。理解这个模型的关键在于抓住组内互斥这个核心特征。2. 问题建模与状态定义2.1 标准问题描述给定N组物品和容量为V的背包每组物品有若干个同一组内物品最多选一个每个物品有体积v[i][j]和价值w[i][j]求不超过背包容量的最大价值这个模型可以形式化为max Σw[i][j]*x[i][j] s.t. Σv[i][j]*x[i][j] ≤ V Σx[i][j] ≤ 1 for each group i x[i][j] ∈ {0,1}2.2 状态转移方程推导定义dp[i][j]为考虑前i组物品背包容量为j时的最大价值。状态转移需要分情况讨论不选第i组任何物品dp[i][j] dp[i-1][j]选第i组的某个物品kdp[i][j] max(dp[i-1][j-v[i][k]] w[i][k])综合起来得到dp[i][j] max{ dp[i-1][j], max(dp[i-1][j-v[i][k]] w[i][k]) for all k in group i }这个方程体现了分组背包的核心思想——对每组物品做选或不选的决策如果选则必须遍历组内所有物品的可能性。3. 算法实现细节3.1 基础实现版本def group_knapsack(V, groups): n len(groups) dp [[0]*(V1) for _ in range(n1)] for i in range(1, n1): for j in range(V1): dp[i][j] dp[i-1][j] # 不选该组 for v, w in groups[i-1]: if j v: dp[i][j] max(dp[i][j], dp[i-1][j-v] w) return dp[n][V]这个实现的时间复杂度是O(NVS)其中S是平均每组物品数。空间复杂度O(NV)。3.2 空间优化技巧观察到dp[i]只依赖dp[i-1]可以优化为一维数组def group_knapsack_opt(V, groups): dp [0]*(V1) for group in groups: for j in range(V, -1, -1): # 逆向遍历 for v, w in group: if j v: dp[j] max(dp[j], dp[j-v] w) return dp[V]注意内层循环必须逆向遍历否则会重复计算同一组的多个物品4. 典型应用场景4.1 课程选修问题假设某计算机专业有以下课程分组编程语言组Java(4学分,8价值)、Python(3学分,7价值)算法组DP(3学分,9价值)、图论(4学分,10价值)系统组OS(5学分,12价值)、网络(4学分,11价值)学生最多选修20学分每组最多选一门。这就是典型的分组背包问题。4.2 广告投放优化某广告平台有视频广告组15s(成本5,收益8)、30s(成本8,收益12)图文广告组单图(成本3,收益5)、多图(成本6,收益9)文字广告组短文案(成本2,收益3)、长文案(成本4,收益6)预算限制为20每组最多投一个广告。用分组背包可以求出最优组合。5. 常见问题与调试技巧5.1 初始化陷阱错误做法dp [[0]*V]*n # 浅拷贝问题正确初始化dp [[0 for _ in range(V1)] for _ in range(n1)]5.2 边界条件处理常见错误包括忘记处理jv[i][k]的情况组索引从0还是1开始混淆容量遍历顺序错误必须从大到小5.3 性能优化建议当V很大时先过滤掉组内明显劣势的物品v大w小的对每组物品按v排序利用单调性剪枝考虑使用滚动数组或位运算优化6. 扩展变种与实践6.1 每组必选一件修改状态转移方程dp[i][j] max(dp[i-1][j-v[i][k]] w[i][k]) # 去掉不选该组的情况6.2 多维费用约束增加状态维度dp [[[0]*(V21) for _ in range(V11)] for _ in range(n1)]6.3 混合背包问题结合完全背包、多重背包等情况需要分情况处理不同组别的物品类型。在实际项目中我遇到过需要处理200组、总容量10^6级别的分组背包问题。关键突破点是预处理阶段合并相似物品使用快速最大值查询数据结构并行化处理独立组别分组背包的灵活建模能力使其成为解决实际约束优化问题的利器。掌握其核心思想后可以扩展到更复杂的业务场景中。 
长河君 · 2026/10/28 15:57:25 · 阅读 1.2k 分组背包问题解析与动态规划实践
1. 分组背包问题概述分组背包问题是动态规划中一个经典变种它扩展了传统0-1背包问题的约束条件。在实际开发中我经常遇到需要从多个互斥的选项组中选择最优组合的场景比如广告投放策略选择、课程选修方案设计等。这类问题的核心特征是物品被划分为若干组每组内的物品相互冲突最多只能选择其中一个。与基础背包问题相比分组背包的决策维度从单个物品升级到了物品组。这种约束在实际业务中非常常见——比如电商促销时同一品类的优惠券往往只能选一张使用。理解这个模型的关键在于抓住组内互斥这个核心特征。2. 问题建模与状态定义2.1 标准问题描述给定N组物品和容量为V的背包每组物品有若干个同一组内物品最多选一个每个物品有体积v[i][j]和价值w[i][j]求不超过背包容量的最大价值这个模型可以形式化为max Σw[i][j]*x[i][j] s.t. Σv[i][j]*x[i][j] ≤ V Σx[i][j] ≤ 1 for each group i x[i][j] ∈ {0,1}2.2 状态转移方程推导定义dp[i][j]为考虑前i组物品背包容量为j时的最大价值。状态转移需要分情况讨论不选第i组任何物品dp[i][j] dp[i-1][j]选第i组的某个物品kdp[i][j] max(dp[i-1][j-v[i][k]] w[i][k])综合起来得到dp[i][j] max{ dp[i-1][j], max(dp[i-1][j-v[i][k]] w[i][k]) for all k in group i }这个方程体现了分组背包的核心思想——对每组物品做选或不选的决策如果选则必须遍历组内所有物品的可能性。3. 算法实现细节3.1 基础实现版本def group_knapsack(V, groups): n len(groups) dp [[0]*(V1) for _ in range(n1)] for i in range(1, n1): for j in range(V1): dp[i][j] dp[i-1][j] # 不选该组 for v, w in groups[i-1]: if j v: dp[i][j] max(dp[i][j], dp[i-1][j-v] w) return dp[n][V]这个实现的时间复杂度是O(NVS)其中S是平均每组物品数。空间复杂度O(NV)。3.2 空间优化技巧观察到dp[i]只依赖dp[i-1]可以优化为一维数组def group_knapsack_opt(V, groups): dp [0]*(V1) for group in groups: for j in range(V, -1, -1): # 逆向遍历 for v, w in group: if j v: dp[j] max(dp[j], dp[j-v] w) return dp[V]注意内层循环必须逆向遍历否则会重复计算同一组的多个物品4. 典型应用场景4.1 课程选修问题假设某计算机专业有以下课程分组编程语言组Java(4学分,8价值)、Python(3学分,7价值)算法组DP(3学分,9价值)、图论(4学分,10价值)系统组OS(5学分,12价值)、网络(4学分,11价值)学生最多选修20学分每组最多选一门。这就是典型的分组背包问题。4.2 广告投放优化某广告平台有视频广告组15s(成本5,收益8)、30s(成本8,收益12)图文广告组单图(成本3,收益5)、多图(成本6,收益9)文字广告组短文案(成本2,收益3)、长文案(成本4,收益6)预算限制为20每组最多投一个广告。用分组背包可以求出最优组合。5. 常见问题与调试技巧5.1 初始化陷阱错误做法dp [[0]*V]*n # 浅拷贝问题正确初始化dp [[0 for _ in range(V1)] for _ in range(n1)]5.2 边界条件处理常见错误包括忘记处理jv[i][k]的情况组索引从0还是1开始混淆容量遍历顺序错误必须从大到小5.3 性能优化建议当V很大时先过滤掉组内明显劣势的物品v大w小的对每组物品按v排序利用单调性剪枝考虑使用滚动数组或位运算优化6. 扩展变种与实践6.1 每组必选一件修改状态转移方程dp[i][j] max(dp[i-1][j-v[i][k]] w[i][k]) # 去掉不选该组的情况6.2 多维费用约束增加状态维度dp [[[0]*(V21) for _ in range(V11)] for _ in range(n1)]6.3 混合背包问题结合完全背包、多重背包等情况需要分情况处理不同组别的物品类型。在实际项目中我遇到过需要处理200组、总容量10^6级别的分组背包问题。关键突破点是预处理阶段合并相似物品使用快速最大值查询数据结构并行化处理独立组别分组背包的灵活建模能力使其成为解决实际约束优化问题的利器。掌握其核心思想后可以扩展到更复杂的业务场景中。