如何用贪心算法解决单店限购一件的全商品采购分配问题

首先明确问题本质：这是一个二分图匹配问题——左侧是门店节点，右侧是商品节点，当门店可售某商品时，两者间存在边。我们需要找到一个匹配，覆盖所有商品（前提是商品数量≤门店数量）。

你之前尝试的「优先处理仅单一门店有售的商品」是贪心的基础步骤，但仅靠这一步无法覆盖所有场景，需要结合后续的分层贪心策略：

完整贪心执行步骤 #

1. 锁定唯一来源商品

   • 遍历所有商品，找出那些只有一个门店可售的商品，直接将该商品分配给对应的门店。
   • 分配完成后，标记该门店为「已占用」（不能再采购其他商品），同时将该商品从所有门店的可售列表中移除，从待分配商品集合中删除。
   • 这一步是核心前提：如果不先锁定这类商品，后续可能会把唯一能售卖它的门店分配给其他商品，导致该商品无法被采购。

2. 处理剩余多来源商品与空闲门店

   • 对于剩余的待分配商品（均有≥2个可选门店）和空闲门店，执行以下循环直到所有商品分配完成或判定无解：
     • 从待分配商品中，选择当前可选门店数量最少的商品（优先约束性强的商品，避免后期无门店可选）。
     • 为该商品分配一个当前可售商品数量最少的空闲门店（尽量保留可售商品多的门店，给其他约束性弱的商品留更多选择）。
     • 标记该门店为已占用，将该商品从待分配集合中移除，并从其他门店的可售列表中删除该商品。

3. 校验结果

   • 如果所有商品都完成分配，输出方案；如果循环结束仍有商品未分配，则说明当前不存在可行采购方案。

为什么单一处理步骤会失效？ #

举个典型反例：

门店：X、Y、Z；商品：p、q、r

• X可售：p、q
• Y可售：q、r
• Z可售：p、r

这里没有仅单一门店可售的商品，若只靠初始的单一来源处理步骤会陷入停滞。但用完整贪心策略：

• 所有商品都有2个可选门店，任选一个（比如p），分配可售商品最少的门店（X或Z均可），锁定X和p；
• 剩余商品q可选Y，r可选Z，完成分配。

注意事项 #

贪心算法不保证100%找到可行解（比如某些复杂的二分图结构，贪心的局部最优会导致全局无解）。如果需要确保找到所有可行解或判定无解，建议使用匈牙利算法等二分图匹配的确定性算法。但上述贪心策略在大多数实际场景中，能高效找到可行方案。

内容的提问来源于stack exchange，提问作者xilinos