如何从整数列表中最优选取符合条件的有效整数对以最小化剩余元素

你之前尝试的先排查无效配对再调整的思路确实冗余度太高，针对100的小规模数据，有更简单高效的方案：

可行方案参考 #

方案1：二分图最大匹配（100%得到最优解） #

你的问题本质是无向图最大匹配问题，用标准算法即可无压力得到最优结果：

• 给每个元素分配0~99的唯一索引（天然解决重复值问题）
• 构建邻接矩阵：adj[i][j] = True当且仅当i<j且索引i和j对应的元素满足配对条件
• 用匈牙利算法求解该无向图的最大匹配，得到的匹配集合就是能形成的最多配对，剩余未配对元素数量自然最少
  100节点的匈牙利算法运算量极低，哪怕用最基础的实现也能在毫秒级得到结果，代码实现也仅需几十行，逻辑非常清晰没有冗余。

方案2：随机贪心匹配（实现极简，适配你的场景） #

你提到无效配对出现概率极低，那完全可以用更简单的随机贪心方案，几乎能达到和最优解一样的效果：

• 重复执行以下流程20~50次：
  • 把所有元素的索引随机打乱
  • 初始化已使用标记数组，初始全为未使用
  • 顺序遍历打乱后的索引：如果当前索引未被使用，就往后找第一个未被使用且满足配对条件的索引，将二者标记为已使用，加入本次配对集合
  • 记录当前配对集合的大小，如果比历史最优的大就更新最优结果
• 最终返回最优的配对集合
  这个方案写起来极其简单，没有复杂的图算法逻辑，针对你的场景（无效配对极少），大概率能直接得到满配对（50对，剩余0个元素）的结果，性能也完全够用。

小优化提示 #

你可以先简化下配对条件的校验逻辑：原条件2 * a != gcd(a, a + b)等价于2 * a != gcd(a, b)，可以减少一次加法运算，当然你已经实现了校验函数的话不改也完全没问题。

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