二分图判定与满足全员早餐的最小食物选择问题技术问询

问题2：求满足所有人早餐需求的最少食物数量 #

这个问题本质是集合覆盖问题的简化版：我们要选最少的食物，让每个人的偏好列表里至少有一个食物被选中。

实用解法分两种场景：

• 小规模数据（食物/人数不多）：可以用贪心算法快速得到近似最优解（大部分时候就是精确解），步骤如下：

  1. 初始化所有人为「未满足」状态，统计每个食物能覆盖的未满足人数。
  2. 每次选当前覆盖未满足人数最多的食物，把被这个食物覆盖的人标记为「已满足」。
  3. 重复步骤1-2，直到所有人都被满足，统计选中的食物数量。
     比如你的示例里，f2能覆盖p1和p3（2个人），是覆盖人数最多的，先选它；剩下p2未满足，选f3就能搞定，总共2个食物，正好是最优解。

• 需要精确最优解（数据规模小）：可以用回溯法枚举所有可能的食物组合，找到能覆盖所有人的最小子集，但这种方法效率低，只适合M和N都很小的情况。

如果是大规模数据，可能需要用更高效的近似算法或者启发式算法，但日常场景里贪心基本够用啦。

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