我有两组数字， SET2 通常包含更多项目。确保 SET2 的计数等于或大于 SET1 的计数。
从根本上说，由于顺序很重要，因此输入不是列表而是集合。
我的目标是对 SET2 中的数字进行组合(求和)/对其重新排序，以使其尽可能类似于 SET1 。我将相似性定义为每个位置的偏差之和。有关我计算相似性的方式，请参见this post。总和越小越好。
我的第一种方法是尝试所有组合并选择最佳组合。这仅适用于非常小的集合(尤其是第二个集合)。请参阅this post和Rawling的答案。
有没有更聪明的方法来获得良好的组合？我绝对不需要最好的。结果，一个好人会没事的。显然，带有空子集的集合是胡说八道。极端不平衡的布景对我来说似乎不是很有希望。 SET1往往有大约8个，但最多可以有18个条目。 SET2通常计数超过10(最多35)。
两组数字之和相等(舍入误差除外)。
这是一个有好有坏结果的示例(并非所有可能的结果):
SET1 = { 272370, 194560, 233430 }; SET2 = { 53407.13, 100000, 365634.03, 181319.07 }
272370 | 194560 | 233430
---------------------------------------------------------------------
365634.03 | 100000 + 53407.13 | 181319.07 (best match)
365634.03 | 181319.07 | 100000 + 53407.13 (good)
365634.03 | 100000 |181319.07 + 53407.13 (ok)
53407.13 |365634.03 + 100000 | 181319.07 (bad)
53407.13 |365634.03 + 181319.07 | 100000 (bad)
. |365634.03 + 181319.07 | 53407.13 + 100000 (invalid)
53407.13 + 100000 |365634.03 + 181319.07 | (invalid)
如果我忘了描述一个前提，或者我的描述不清楚甚至是错误的，请告诉我。我也很高兴提供另一个示例。
提前致谢!
最佳答案
启发式，应该可以很好地工作:
1. list<int> set1, set2;
2. sort(set2) // decreasing, set2[0] would be the greatest value in set2
3. struct set1item = {set1index, value, list<int> chosen}
4. prepare list<set1item> set1items from set1 //(index = index in set1 list, value = set1[index] and chosen = null)
5. put set1items to some priorityqueue pq // ordered by value
6. for each set2item in set2{
7. item = pq.first()
8. item.chosen.add(set2item);
9. item.value -= set2item;
10. pq.updateFirst(item)
11.}
它的工作方式是:从最高到最低依次遍历set2，从set1获得实际最高的元素，将其从set2获得的元素减少，然后将set2中的该元素添加到set1结果中的元素。
您必须记住检查set1中的所有元素是否没有空结果。
范例1:
Set1 = {20, 9, 7, 3}, Set2 = {7, 6, 6, 4, 2, 2, 2, 2, 2, 2, 2, 2}。iter1:
fromSet2 = 7，Set1 = {20:{}, 9:{}, 7:{}, 3:{}}，fromSet1=20。将20减7，并将其结果加7。更新:
Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}。iter2:
fromSet2 = 6，Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}，fromSet1=13。将13减6并将其结果加6。更新:
Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}。iter3:
fromSet2 = 6，Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}，fromSet1=9。将9减6并将其结果加6。更新:
Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}。iter4:
fromSet2 = 4，Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}，fromSet1=7。将7减4，然后将其结果加4。更新:
Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}。iter5:
fromSet2 = 2，Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}，fromSet1=7。将7减2并将其结果加2。更新:
Set1 = {3:{7, 6, 4}, 3:{6}, 5:{2}, 3:{}}。...
关于c# - 找到两个数字列表的良好匹配，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14500595/