5

我有两组数字，其中SET2通常包含更多项目。保证SET2的计数 等于或大于SET1的计数。实际上，由于顺序很重要，因此输入是列表而不是集合。

我的目标是组合（总结）/重新排序SET2中的数字，使其尽可能与SET1相似。我将相似度定义为每个位置的偏差之和。请参阅这篇文章了解我计算相似度的方式。总和越小越好。

我的第一种方法是尝试所有组合并选择最好的组合。这仅适用于相当小的集合（尤其是第二个）。请参阅这篇文章和 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)

如果我忘记描述前提或者我的描述不清楚甚至是错误的，请告诉我。我也很乐意提供另一个例子。

提前致谢！

4

1 回答 1

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 中的所有元素是否没有空结果。

Set1 = {20, 9, 7, 3}, Set2 = {7, 6, 6, 4, 2, 2, 2, 2, 2, 2, 2, 2}例1：.

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

...

于 2013-01-24T14:04:40.433 回答