algorithm - 选择最佳的元素配对

Question

我有以下问题，例如:给定一个带有符号的桶
1 1 2 3 3 4
和创建配对的食谱书，例如:
12 13 24
从桶中选择最优配对，在桶中留下尽可能少的符号。因此，使用高于最佳配对的示例值将是:
13 13 24 这将使用给定的所有符号。
天真的从桶中挑选可能会导致类似的结果:
12 13 让 3 和 4 不匹配。 3 和 4 无法匹配，因为该书不包含该特定连接的配方

注意事项:
真正的问题平均包括:桶中的 500 个元素，大约 30 种符号。

我们已经尝试使用暴力算法实现解决方案，但恐怕连我们的孙子也活不到看到结果:)。

食谱书的篇幅没有限制，甚至可以说是应有尽有。不允许两次由相同元素组成的对。

答案不需要完全清空桶。它只是要从桶中取出最多的对。把一些留在桶里也没关系。最好寻找最优解，但近似值也足够了。

我将感谢提出/给出解决问题算法提示的答案。

例子:
桶:
1 1 2 2 2 2 3 3 3 4 5 6 7 8 8
食谱书:
12 34 15 68
最佳结果(可能之一):
{1 2} {1 2} {3 4} {6 8}
剩余:
2 2 3 3 5 7 8

Answer 1

这个问题本质上是maximum matching problem稍微改变一下，您就可以拥有重复的对象。假设您有最大匹配求解器，这是解决此问题的一种方法:

1. 为输入列表中的每个数字创建一个节点。

2. 对于每个食谱，对于匹配该食谱的每对数字，在这些数字的节点之间添加一条边。

3. 运行最大匹配算法并返回以这种方式报告的对。

您可以使用大量现成的最大匹配算法，如果您需要自己编写一个，请考虑 Edmonds' Blossom Algorithm ，与其他方法相比，这种方法相当高效且编写起来不那么棘手。