math - 获得两组数字的最小公等和和组合

Question

我目前正在用 C# 创建一个程序，该程序将寻找两组数字的最小可能相等总和，您可以在其中重复这些数字任意多次。

例如，我有这两组{ 10, 13, 18 }和{ 12, 16, 22 }. 我能得到的最低金额是28 :(10 + 18)和(12 + 16).

另一个例子是{5, 7, 9}和{1, 2, 3}。最小可能的总和是5 : (5)and (1+1+1+1+1)or (1+2+2)or or(2+3)等​​等。

关于我可以从哪里开始的任何建议？我实际上每组将使用 6 个数字，这些数字在数百/数千个标记中。

Answer 1

维护两个集合，从您的输入集合初始化，并按递增的数字排序（例如，使用基于树的集合结构）。现在比较两组中的第一个（即最小）元素。您从其集合中删除较小的元素，将相应输入集中的所有元素添加到该值，然后插入结果。当两个集合具有相同的最小元素时，您就完成了，并且该元素是您的最不常见的相等总和。