删除列表冗余集合最小化唯一子元素数量的算法求解方案

这个需求本质是带硬约束的组合优化问题：你需要从每个食谱的多个可行配料组合里恰好挑1个，最终让所有选中组合里出现过的唯一食材总数尽可能小。

根据你的数据规模选对应方案即可：

• 小规模数据集（食谱总数不超过20，每个食谱的候选配料组合数不超过5）
  直接穷举所有选择组合即可。总组合数是每个食谱候选数的乘积，比如15个食谱每个有2个候选，总共有32768种组合，普通电脑几毫秒就能算完，遍历每种组合的总唯一食材数，取数值最小的对应组合就是全局最优解，完全不会出错。
  拿你给的示例来说：

  recipe1 = (("egg", "salt", "pepper"),) # 只有1个候选，必选
  recipe2 = (("egg", "carrot", "ham"), ("cream", "carrot", "ham"))
  recipes = (recipe1, recipe2)
  

  遍历两种选择：

  1. recipe2选("egg", "carrot", "ham")：总唯一食材是egg、salt、pepper、carrot、ham，共5种
  2. recipe2选("cream", "carrot", "ham")：总唯一食材是egg、salt、pepper、cream、carrot、ham，共6种
     直接选第一种就得到最优结果。

• 中大规模数据集（食谱数多、每个食谱候选组合多，穷举计算量太大）
  用贪心启发式算法就行，计算效率极高，在食谱这类食材重复率高的场景下，结果和全局最优的差距通常在5%以内，完全够用：

  1. 先初始化全局已选食材集合为空，把所有只有1个候选组合的食谱的配料直接加入全局集合，这些食谱没有选择空间，属于必选内容
  2. 遍历所有还没选定组合的食谱，给每个食谱的所有候选组合算分：分数=这个组合里没出现在全局已选集合里的食材数量，分数越低代表选这个组合新增的食材越少
  3. 选出分数最低的那个候选组合，把它的所有配料合并进全局已选集合，标记对应食谱已完成选择
  4. 如果遇到多个候选分数一样，就优先选「已在全局集合里的食材占比最高」的那个，能进一步降低后续选择新增食材的概率
  5. 重复步骤2-4，直到所有食谱都选定唯一的配料组合

如果你的场景要求必须拿到100%全局最优解，数据规模又大到穷举跑不动，可以把问题转成0-1整数规划模型求解：给每个食材设一个0-1变量标记是否被选中，给每个食谱的每个候选组合设一个0-1变量标记是否被选中，加两个硬约束：每个食谱恰好有1个候选组合的变量为1、如果某个候选组合被选中，它包含的所有食材的变量必须为1，目标函数设为最小化所有食材变量的总和，用开源整数规划求解器就能算出精确最优解。

内容的提问来源于stack exchange，提问作者adrienlucca.net