找到两个数字列表的匹配

Question

我有两组数字,SET2通常包含更多项目.保证SET2的计数 等于或大于SET1的计数.实际上,由于订单很重要,输入是列表而不是集合.

我的目标是组合(总结)/重新排序SET2中的数字,使其尽可能类似于SET1.我将相似度定义为每个位置的偏差之和.有关我计算相似性的方式,请参阅此文章.总和越小越好.

我的第一个方法是尝试所有组合并选择最好的组合.这仅适用于非常小的集合(尤其是第二个集合).看到这篇文章和罗林的答案.是否有更聪明的方法来获得良好的组合？我绝对不需要最好的一个.一个好的结果会很好.显然,具有空子集的集合是无意义的.绝对不平衡的集合对我来说似乎不太有希望.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)

如果我忘记描述前提或我的描述不清楚甚至有缺陷,请告诉我.我也很乐意提供另一个例子.

提前致谢!

Answer 1

启发式，应该效果很好：

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}.

迭代 1: fromSet2 = 7, Set1 = {20:{}, 9:{}, 7:{}, 3:{}}, fromSet1=20. 将 20 减 7，然后将结果加 7。更新：Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}。

迭代2: fromSet2 = 6, Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}, fromSet1=13. 将 13 减 6，然后将其结果加 6。更新：Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}。

迭代3：fromSet2 = 6，，Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}。fromSet1=9将 9 减 6，然后将结果加 6。更新：Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}。

迭代4：fromSet2 = 4，，Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}。fromSet1=7将 7 减 4，然后将结果加 4。更新：Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}。

迭代5：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:{}}。

...