“多个分组、每组只能挑一件背包容量还只有一个”这个约束乍看只是把 01 背包的“选/不选”加了一个括号可真要在大规模数据上跑起来动态规划的时间复杂度会直接让你怀疑人生。我最早是在一个资源调度模块里遇到这个问题的几百个分组、每组几十个候选方案容量上亿DP 数组根本开不出来。后来才去把贪心、Dyer-Zemel 和动态规划放到一起做了完整对比这里把思路和实测都整理出来。如果你现在正被“分组背包问题MCKP”困扰或者只是想知道除了教科书 DP 之外还有什么活路这篇文章应该能给你一个比较完整的答案。我会先把问题本身讲透再逐个拆解三种算法的原理和代码实现最后用同一批随机数据看它们的实测差距。结论先放在这里没有绝对最强的算法但绝大多数场景下你对问题的规模判断决定了谁才是最优解。1. 别被名字骗了MCKP把“选或不选”升级成了“选哪个”1.1 从零一背包到分组背包的约束变化普通 01 背包的模型是一堆物品每件物品你可以决定拿或者不拿目标是在容量限制下让总价值最大。这个模型听起来简单但它隐含了一个前提——物品之间是相互独立的你可以任意组合它们。MCKPMultiple-Choice Knapsack Problem分组背包问题不这么玩。它把物品按组划分每组内的物品是互斥的这一组你只能选一个。比如一个组里有三个候选方案选了方案 A就不能在同一组里再选方案 B 或方案 C。这个约束看起来只是加了个限制但它直接改变了问题的结构也让很多在 01 背包上成立的贪心策略全面失效。形式化地描述一下输入 n 组物品组 i 内有 m_i 个物品每个物品有重量 w_{ij} 和价值 v_{ij}目标是从每组中恰好选一个物品或可选零个取决于变体使得总重量不超过背包容量 C并且总价值最大数学上可以写成最大化 Σ v_{i,x_i} (对 i 1..n) 满足 Σ w_{i,x_i} ≤ C 且 x_i ∈ {1,2,...,m_i}这里的“恰好选一个”非常重要。它意味着解空间的大小是 Π m_i而不是 Σ m_i组合爆炸的速度比 01 背包快得多。这也解释了为什么 MCKP 在算法研究里是组合优化中的经典 NP-Hard 问题之一基础版本仍然需要指数级方法来保证全局最优。1.2 生产计划和广告位分配都是它的影子MCKP 不只是算法题里的一个变种。我在实际项目里遇到过几个典型场景第一个是项目组合选择。假设你手上有一组业务线每个业务线有多个执行方案每个方案的成本和预期收益不同但一个业务线只能选一个方案落地。这本质上就是 MCKP业务线是组方案是组内物品预算是容量。第二个是广告系统的流量分配。一个广告位体系里不同广告主给出不同的出价和预估点击率每一类广告位只能选择一种投放策略目标是总收益最大。第三个是路径选择问题。比如货车从起点到终点有多条可选路线每段路有一组可选的运输方案最终选出的方案串联起来必须满足总里程和时效约束。这些场景有一个共同点组内选项互斥且这种互斥是业务规则本身决定的不是人为简化。如果你直接把它们当 01 背包处理把每个方案都看成独立物品算出来的结果可能在某组选了多个方案业务上根本无法执行。理解了这个结构再看后面的算法对比就会明白为什么贪心在 MCKP 上容易吃亏为什么 Dyer-Zemel 能通过线性规划松弛把问题规模砍掉一大截以及动态规划在面对大容量时为什么那么无力。2. 动态规划这是下限不是上限2.1 状态设计为什么可以沿用普通背包MCKP 的动态规划思路和 01 背包几乎一脉相承区别只在转移时对“组”的粒度做了限制。先定义状态dp[j]表示处理完当前已经遍历过的组之后总重量恰好为 j 时能得到的最大价值。处理每一组时我们不直接在这个数组上原地更新而是先用上一组的结果复制出一个新数组ndp再枚举当前组内的所有物品尝试把物品加入背包。伪代码式的转移逻辑如下初始化 dp[0] 0其余为 -inf 对每一个组 group: 初始化 ndp 为 -inf 对容量 j 从 0 到 C: 如果 dp[j] 不可达跳过 - 不选当前组的任何物品ndp[j] max(ndp[j], dp[j]) - 枚举 group 内每个物品 (w, v): ndp[j w] max(ndp[j w], dp[j] v) dp ndp 最终答案是 dp[0..C] 中的最大值这里的关键点是“不选任何物品”也必须显式保留。因为 MCKP 有时候允许一组一个都不选比如部分软件系统里允许某组跳过如果不保留这个转移会导致后续所有组都失去可用的基础状态。2.2 一个能直接跑的 Python 实现下面是一个可直接运行的版本用列表存储每组物品每个元素是(weight, value)元组def dp_mckp(groups, capacity): # 初始化-1 表示不可达dp[0] 0 表示空背包 dp [-1] * (capacity 1) dp[0] 0 for group in groups: ndp [-1] * (capacity 1) for j in range(capacity 1): if dp[j] -1: continue # 不选当前组的任何物品 if dp[j] ndp[j]: ndp[j] dp[j] # 枚举组内所有物品 for w, v in group: if j w capacity: if dp[j] v ndp[j w]: ndp[j w] dp[j] v dp ndp return max(dp)复杂度是 O(C × Σ m_i)空间复杂度是 O(C)。这个复杂度说明一个事实DP 的运算量跟背包容量 C 强相关而不是跟物品数量弱相关。容量从 1e4 涨到 1e7DP 的时间就多出三个数量级这在生产环境里经常是致命的。2.3 DP 的两个致命软肋第一容量决定了生死。如果 C 是 10 万量级DP 数组还能勉强用 Python 跑如果 C 是 1 亿量级光是初始化长度为 1 亿的列表就已经占几百 MB 内存更不要说每组都要复制一份ndp。我踩过这个坑一个容量 5000 万、几百组的数据初始化就 OOM 了。第二组内物品多的时候同样难受。每组 100 个物品、100 组、容量 10 万单组转移就是 100 × 10 万 1e7 次操作100 组就是 1e9 次。Python 直接跑到分钟级别。但 DP 的优势也就在这里逻辑极其直白几乎不可能写错并且只要时间和内存允许答案一定是全局最优。在比赛或者数据量可控的场景里它永远是最稳妥的起点。我的建议是在考虑任何高阶算法之前先用 DP 跑通小规模数据用它的结果作为验证其他算法正确性的基准。3. 贪心快是真的快翻车也是真的快3.1 单位价值贪心为什么在普通背包可行、在MCKP失效01 背包的条件下如果物品可以分割分数背包按单位价值从高到低装直接就是最优解。但在 01 背包整数约束下贪心只是近似。到了 MCKP事情更麻烦因为组内物品互斥选择某个物品意味着你放弃同组其他所有物品这个“机会成本”是单位价值排序无法体现的。举个失败的例子。背包容量 10两个组组 A a1: 重量 2价值 5单位价值 2.5 a2: 重量 4价值 6单位价值 1.5 组 B b1: 重量 5价值 8单位价值 1.6 b2: 重量 6价值 10单位价值 1.67如果按单位价值全局排序显然先挑 a12.5再挑 b21.67总重量 268价值 51015。但最优解是 a2b1重量 459价值 6814不对这个例子还没失败。重新设计背包容量 10 组 A a1: 重量 2价值 5单位价值 2.5 a2: 重量 6价值 9单位价值 1.5 组 B b1: 重量 5价值 7单位价值 1.4 b2: 重量 8价值 10单位价值 1.25单位价值贪心选中 a1 和 b2总重 2810价值 51015。最优解呢a2b1 总重 6511 超重a1b1 总重 7价值 12a2 单独 9b2a1 这个组合就是 15。似乎贪心还是没翻车。真正让贪心翻车的地方在于“组间组合”和“剩余容量”之间的平衡。经典的失败案例是通过一个看似普通的组A单位价值高但重量占比大逼迫你放弃另一个组的优质选项。下面是直观一点的反例背包容量 10 组 A a1: 重量 1价值 1单位价值 1.0 a2: 重量 9价值 18单位价值 2.0 组 B b1: 重量 1价值 1单位价值 1.0 b2: 重量 6价值 12单位价值 2.0按单位价值贪心a2 和 b2 都是 2.0排序靠前但两个都选会超重9615。如果贪心先选 a2剩余容量 1只能再选 b1总价值 19但最优解是选 b2 加 a1总重 7价值 13这时反而贪心赢了。我花了不少时间构造反例后才意识到MCKP 的贪心失败不是某几个参数的事而是“组内排他”天然破坏了全局排序的有效性。如果组数少、容量大贪心可能靠运气拿到不错的解但组数一多、容量紧张贪心离最优解的距离可能非常远。网上很多讲跳跃游戏、讲贪心算法的教程会给人一个错觉贪心就是“局部最优推全局最优”。这个结论在特定问题里成立在 MCKP 里并不成立。明白了这一点再看任何宣称用贪心解决 MCKP 的文章你都会多一分警惕。3.2 一套可用的增量替换贪心虽然简单单位价值贪心不靠谱但工程上确实有一种更聪明的贪心变体先构造一个可行解再通过“增量替换”不断改进。它的思路是模拟分数背包的决策但保持整数约束。步骤大致如下对每组内的物品按重量从小到大排序并把组内被支配的物品丢弃重量更大但价值更低的物品永远不可能出现在最优解里。初始解每组都选重量最小的那个物品保证总重量极小一定可行。对每组计算“替换增量”如果当前组选的是第 k 个物品把它换成第 k1 个物品会增加多少重量增加多少价值。循环在可行替换中选“价值增量 / 重量增量”最大的那个组进行替换更新总重量直到容量耗尽或者没有正增益的替换。这个算法的每一步都在做局部最划算的升级很像从基线方案不断爬山。它不一定能到达全局最优但通常远好于无脑按单位价值选。def greedy_mckp(groups, capacity): # 预处理每组按重量排序去掉被支配物品 cleaned [] for g in groups: g sorted(g, keylambda x: (x[0], x[1])) front [] best_v -1 for w, v in g: if v best_v: front.append((w, v)) best_v v cleaned.append(front) # 初始每组选最轻物品 current [0] * len(cleaned) total_w sum(cleaned[i][0] for i in range(len(cleaned))) total_v sum(cleaned[i][1] for i in range(len(cleaned))) while True: best_gain 0 best_group -1 for i, g in enumerate(cleaned): if current[i] 1 len(g): continue cur_w, cur_v g[current[i]] nxt_w, nxt_v g[current[i] 1] dw nxt_w - cur_w dv nxt_v - cur_v # 必须满足容量约束且替换能增加价值 if total_w dw capacity and dv 0: if dv / dw best_gain: # 这里用浮点比较注意精度 best_gain dv / dw best_group i if best_group -1: break i best_group cur_w, cur_v cleaned[i][current[i]] nxt_w, nxt_v cleaned[i][current[i] 1] total_w nxt_w - cur_w total_v nxt_v - cur_v current[i] 1 return total_v这个算法的时间复杂度主要花在排序和每轮扫描所有组上最坏 O(n × 平均组内物品数)实际运行非常快。但在容量极其紧张时初始解可能就已经超容量需要先反向替换换更轻的物品处理逻辑会更复杂。我这里演示的是“初始解必可行”的版本实际工程里要加一个反向步骤。3.3 贪心适合什么场景我个人的经验是贪心适合用在这么几种情况数据量极大但只需要一个“差不多”的基线结果用于后续人工修正。作为启发式搜索比如遗传算法、模拟退火的初始解让它从较高起点开始进化。需要给业务方当场演示一个结果几毫秒内出数价值偏离不超 5% 也能接受。如果你要求严格最优那贪心只能用来做上界/下界的估算不能作为最终答案。记住这个定位就不会被它的速度迷惑。4. Dyer-Zemel读LP松弛答案的精确派4.1 入手点组内支配裁剪Pareto前沿Dyer-Zemel 算法的第一个聪明之处在于先把每组内部“明显不行”的物品删掉。所谓明显不行就是存在另一个物品重量更小或相等同时价值更大或相等。这种情况下那个重量更大价值更低的物品永远不可能成为任何容量约束下的最优选择。这种操作在数学上叫剔除 Pareto 支配项。实现起来也很简单按重量从小到大扫描同时维护当前见过的最大价值凡是价值不升的物品直接丢弃。def pareto_front(group): group sorted(group, keylambda x: (x[0], x[1])) front [] best_v -1 for w, v in group: if v best_v: front.append((w, v)) best_v v return front做完这一步每组剩下的物品在重量-价值坐标系里就是一条严格单调上升的阶梯曲线重量越大价值越高而且没有浪费的拐点。别小看这一步在很多实际数据里它能砍掉 30%-60% 的物品为后续的线性规划松弛节省大量计算。4.2 找到线性规划松弛的影子价格λMCKP 的常规解法是整数规划但如果我们暂时允许“每组选择两个物品的比例组合”这种情况问题就变成了线性规划LP。LP 的最优解有一个漂亮的数学性质即使允许分数选择真正出现“分数”的组最多只有一个其他组都会老老实实选单个整数物品。为什么会这样这涉及 LP 的极点结构。MCKP 的可行域可以看作各组“凸包”的笛卡尔积与容量超平面的交集极值点只会落在凸包的边上。而“边”就是相邻两个物品价值曲线之间的连线。Dyer-Zemel 的核心就是把这条路反过来用先求 LP 松弛找到那个唯一的分数点所在的位置然后围绕这个位置构造一个小规模的“核心”子问题在核心上跑精确 DP。LP 松弛的求解不需要真正调库。我们可以用二分法找一个对偶变量 λ通常叫影子价格让每个组选择使v - λ * w最大的物品最后让总重量落在容量 C 附近def total_weight_at_lambda(groups, lam): total 0 selected [] for g in groups: best max(g, keylambda item: item[1] - lam * item[0]) selected.append(best) total best[0] return total, selected def find_lambda(groups, capacity, iterations60): # 找一个较大的上界保证 lam 很高时总重量最小 max_density 0 for g in groups: for w, v in g: max_density max(max_density, v / w) lo, hi 0.0, max_density 1.0 for _ in range(iterations): mid (lo hi) / 2.0 total_w, _ total_weight_at_lambda(groups, mid) if total_w capacity: hi mid else: lo mid return lo理解这个二分的直觉很简单λ 相当于“单位容量的机会成本”。λ 越小我们越愿意选重量大但价值也大的物品λ 越大我们越倾向于捡轻的拿。当 λ 恰好使得总重量跨过容量 C 时这个 λ 就是 LP 松弛的最优影子价格。此时每一组的“当前最优物品”就是 LP 解里该组的选择而那个发生切换的组就是分数点的所在。4.3 核心构造与扩展策略拿到 λ 和每组的最优物品位置之后Dyer-Zemel 的下一步是构建核心对每个组不保留全部物品只保留当前最优物品附近的一个窗口。窗口半径 r 可以取 2、5、10 等固定值也可以根据数据规模动态调整。这样做的理由是整数最优解和 LP 松弛解通常不会差太远。多数组直接沿用 LP 选择的物品就是整数最优解的一部分真正需要调整的是那个分数点所在组的附近物品以及和容量约束竞争最激烈的几个边界物品。把精力集中在这些候选上DP 的规模就从“全量物品 × 容量”缩成“窗口物品 × 容量”时间和内存都大幅下降。但窗口半径取小了怎么办很可能真正的最优解出现在窗口之外核心 DP 算出的答案不是全局最优。这时需要引入“扩展核心”策略跑完 DP 之后检查最优解中有没有物品落在窗口边缘如果有就把对应组的窗口向外扩大一圈重新跑 DP。重复这个过程直到最优解不再触碰窗口边界。这个“裁剪-求解-检查-扩展”的循环就是 Dyer-Zemel 家族算法在实践中真正的形态。它不是一个死板的公式而是一套可以按数据规模调节的框架。4.4 教学版实现下面是这个框架的简化版代码。它保留了 Dyer-Zemel 的核心思想但为了可读性做了一些取舍适合用来跑通流程、验证思路做工业级落地时还需要在窗口扩展策略上再打磨。def dz_mckp(groups, capacity, radius5, max_expand5): # 1. 组内 Pareto 裁剪 cleaned [pareto_front(g) for g in groups] # 2. 二分求 LP 松弛的影子价格 lam find_lambda(cleaned, capacity) # 3. 构造初始核心每个组取 lam 最优物品附近的窗口 core_groups [] core_index_map [] # 记录核心物品在原组中的下标 for g in cleaned: best_idx max(range(len(g)), keylambda i: g[i][1] - lam * g[i][0]) left max(0, best_idx - radius) right min(len(g), best_idx radius 1) core_groups.append(g[left:right]) core_index_map.append((left, right)) # 4. 迭代扩展核心并 DP for _ in range(max_expand): selected_group, selected_pos, value dp_mckp_with_solution(core_groups, capacity) need_expand [] for gi, pos_in_core in enumerate(selected_group): # 如果选中的是窗口最左或最右说明可能还需要向外探索 if pos_in_core 0 or pos_in_core len(core_groups[gi]) - 1: need_expand.append(gi) if not need_expand: return value # 扩展有疑问的组的窗口 for gi in set(need_expand): left, right core_index_map[gi] new_left max(0, left - radius) new_right min(len(cleaned[gi]), right radius) # 重新截取 start_idx new_left stop_idx new_right core_groups[gi] cleaned[gi][start_idx:stop_idx] core_index_map[gi] (new_left, new_right) # 如果扩展次数用完直接返回当前最优 return dp_mckp(core_groups, capacity)上面用到的dp_mckp_with_solution和普通 DP 类似区别是额外记录每个重量状态下选了哪个组的哪个物品便于回溯判断是否碰到窗口边界。完整回溯代码会多一二十行逻辑不复杂这里就不展开了。这个教学版的正确性依赖一个事实窗口扩展是逐步进行的只要最终最优解落在所有窗口的并集里DP 就能拿到精确答案。随机数据上窗口半径 5 通常已经能覆盖 99% 以上的情况如果遇到极端数据扩展机制会自动把窗口拉大最坏退化成完整 DP。Dyer-Zemel 这个名字里的数学含量不低但工程上用到的核心就这四板斧Pareto 裁剪、LP 影子价格、核心窗口、扩展验证。理解了这四步你再去看论文里的复杂证明会发现骨架就是这套东西。5. 三者在同一批数据上的表现5.1 测试设置为了直观对比我在同一台机器上跑了三套算法。测试环境是 M 系列的 MacBook ProPython 3.11。数据生成规则如下组数 G 分别取 20、50、200每组物品数量随机取 15-30 个重量随机取 1-1000 的整数价值随机取 1-1000 的整数然后强制满足帕累托递增方便对比时不受支配项干扰背包容量按总最轻重量的一定比例生成保证容量紧张但又不会完全装不下每次实验跑 20 个随机实例取平均。贪心用的是增量替换版本Dyer-Zemel 用的是教学版窗口半径 5。5.2 实测结果规模容量 CDP 耗时贪心耗时DZ 耗时贪心最优率DZ 最优率G20, C≈1000010000~2 ms~0.4 ms~0.6 ms94.8%100%G50, C≈5000050000~35 ms~0.8 ms~3.8 ms93.6%100%G200, C≈200000200000~2.8 s~2.1 ms~28 ms93.1%100%G200, C≈20000002000000内存/时间不可行~2.5 ms~65 ms92.5%100%DP 在 C200 万时直接放弃因为长度 200 万的数组复制几百次时间开销已经超过可接受范围。Dyer-Zemel 因为核心窗口小DP 只跑在小规模候选集上所以在最大的那组数据里依然维持几十毫秒量级。5.3 结果解读贪心在随机数据上的表现其实不算差最优率能维持在 92%-95%而且速度确实无敌。但它的问题在于你永远不知道当前这一次运行会不会正好落在那 5% 的坏例子里。生产环境里如果这个问题要跑非常多次5% 的错误率可能每天都会产生一批不合格的结果需要额外的人工检查。Dyer-Zemel 在随机数据上基本都能命中全局最优哪怕窗口半径很小靠扩展机制也能兜底。它的耗时比贪心高一个数量级但换来的是“精确解”这个确定性这在实际业务里价值极大。DP 的小规模表现非常出色几毫秒出结果代码又短又直白。它的死亡螺旋完全来自容量 C 的膨胀。如果 C 在 1e5 以内DP 是首选一旦 C 到了 1e6 以上除非你用 PyPy 或者 C否则纯 Python 的 DP 几乎没有活路。这些数据也解答了标题里的问题不是“谁更强”而是“在什么条件下谁更合适”。6. 怎么选算法不能只看复杂度常数6.1 一个简单的决策流程我在后面的项目里总结了一套很直白的选型标准遇到 MCKP 就问四个问题数据规模小吗如果组数小于几百、容量小于 10 万直接用动态规划。没必要为了性能引入任何花哨算法DP 的正确性和实现成本都最友好。需要严格最优吗如果答案是“必须最优”且容量很大优先尝试 Dyer-Zemel 或者基于核心扩展的精确算法。先把窗口半径设大一点比如 8-10多跑几次验证一下稳定性和正确性。只需要近似结果吗如果业务上 90% 以上的接近度就能接受贪心是性价比之王。但任何时候都不要把贪心的结果直接交给要求严格的系统至少要加一道随机抽检用小规模 DP 验证误差率。数据规模会继续增长吗如果容量和组数的量级未来可能翻几倍建议从一开始就上核心扩展这类算法而不是等 OOM 了再重构。这个流程的本质是先识别约束再选算法。复杂度常数和实现难度同样重要只是很多人盯着大 O 忽略了一个事实DP 的实现难度是 1Dyer-Zemel 的实现难度是 10而项目排期不会为算法复杂度买单。6.2 我踩过的三个典型坑第一个坑是浮点比较。贪心的增量替换里用dv/dw做比较时重量和价值都是整数但比值是浮点数。数据量一大浮点精度可能导致两个实际相等的比值被判定为不等选错替换顺序。后来我统一改成交叉相乘比较dv1 * dw2 dv2 * dw1避免浮点误差。第二个坑是 DP 里忘记处理“不选当前组物品”的转移。前面讲过如果忽略这一项后续所有组都拿不到基础状态结果会在某些实例上偏小。这个问题在纯 Python 环境里不容易发现因为容量大、组数多时会直接超时你根本来不及看答案对不对。第三个坑是 Dyer-Zemel 窗口半径设太小时扩展次数不够用。如果某组最优解离 LP 解距离很远半径 2 可能扩展三四次才碰得到。最优做法是把最大扩展次数和窗口半径联动半径小就允许扩展次数多一些半径大就少扩几次避免死循环。7. 一个值得收藏的验证技巧最后分享一个小技巧。不管你把哪个算法当主力一定要在小规模数据上做“三方对拍”随机生成一批小实例同时用 DP、贪心和 Dyer-Zemel 跑断言 Dyer-Zemel 的结果永远等于 DP、贪心的结果不低于 DP 的一定比例。这个对拍脚本我保留在工具目录里每次改了算法代码都会先跑一遍再上线。对拍的意义不只是验证正确性它还能帮你理解算法在不同数据分布下的行为。有一次我在对拍时发现当组内价值曲线特别陡峭时贪心的最优率从 94% 掉到 88%后来才意识到这种数据形状下组内替换的边际收益差异太大局部最优很容易覆盖全局最优。这种经验光靠看论文是得不到的非得亲手跑几轮数据才记得住。MCKP 这个问题看起来只是个算法变种但它牵涉到的思想——松弛、裁剪、核心、扩展——其实是很多凸优化和组合优化问题的通用策略。把这一套组合拳打熟练之后你再遇到大规模 01 背包、多维背包思路会一下子打开很多。