求最小公等式和两组数字的组合 [英] Getting Least Common Equal Sum and Combination of Two Sets of Numbers

问题描述

我目前正在用C#创建一个程序，该程序将寻找两组数字的最小均等值，您可以在其中重复任意次数.

I'm currently creating a program in C# that would look for the lowest possible equal sum of two sets of numbers, in which you may repeat the numbers as many times as you want.

例如，我有这两套{ 10, 13, 18 }和{ 12, 16, 22 }.我可以获得的最低总金额为 28 :(10 + 18)和(12 + 16).

For example, I have these two sets { 10, 13, 18 } and { 12, 16, 22 }. The lowest possible sum that I can get is 28: (10 + 18) and (12 + 16).

另一个示例是{5, 7, 9}和{1, 2, 3}.最低的总和为 5 :(5)和(1+1+1+1+1)或(1+2+2)或(2+3)，依此类推.

Another example is {5, 7, 9} and {1, 2, 3}. Lowest possible sum is 5: (5) and (1+1+1+1+1) or (1+2+2) or (2+3) and so on.

关于我可以从哪里开始的任何建议?我实际上将每套使用6个数字，并且这些数字在数百/数千个标记之内.

Any suggestions on where I can start? I'll actually be using 6 numbers per set and the numbers are in the hundreds / thousands mark.

推荐答案

维护两个集合，这些集合从您的输入集合初始化，并按递增的顺序排列(例如，使用基于树的集合结构).现在比较两组中的第一个(即最小)元素.从集合中删除较小的那个，将相应输入集中的所有元素添加到该值，然后插入结果.如果两个集合都具有相同的最小元素，那么您就完成了，而那个元素就是您的最小公等式.

Maintain two sets, initialized from your input sets, and ordered by increasing numbers (e.g. using a tree-based set structure). Now compare the first (i.e. minimal) elements from the two sets. The smaller one you remove from its set, add all elements from the corresponding input set to that value, and insert the results. When both sets have the same minimal element, then you are done and that element is your least common equal sum.

这篇关于求最小公等式和两组数字的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！