选择元素的最佳配对

Question

我有以下问题，例如：给定一个带有符号
1 1 2 3 3 4
的桶和一本菜谱来创建配对，例如:
121324
从桶中选择最佳配对，在桶中保留尽可能少的符号。因此，使用上面的示例值，最佳配对将是:
131324，它将使用给定的所有符号。
从桶中简单地选取可能导致类似于:
1213使得3和4不匹配。3和4无法匹配，因为该书不包含该特定连接的制作方法

注:
实际问题平均包含：桶中500个元素，约30种符号。

我们已经尝试使用bruteforce算法来实现这个解决方案，但是我担心即使是我们的孙子孙女也活不到看到这个结果：）。

食谱书的大小是没有限制的，它甚至可以有每一个可能在桶里。不允许使用同一元素两次生成对。

答案不需要完全清空桶。这只是为了从桶里得到最多的双。在桶里留点也可以。它将是最好的寻找最优解，然而接近的近似也是足够好的。

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

示例:
bucket:
1 1 2 2 2 2 3 3 3 4 15 68
食谱:
12 34 15 68
最佳结果（可能之一）:
{1 2}{1 2}{3 4}{6 8}
剩余部分:
23578

Answer 1

这个问题本质上是一个最大匹配问题，只是允许有重复的对象。这里有一种方法来解决这个问题，假设您有一个最大匹配的求解器：

>

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

对于每个制作方法，对于匹配该制作方法的每对数字，在这些数字的节点之间添加一条边。