两个有序列表中项目的最佳配对策略同时保持顺序的算法

Question

我有以下两个有序的项目列表:

A = ["apples","oranges","bananas","blueberries"]
B = ["apples","blueberries","oranges","bananas"]

每个项目都有一个等于字符串长度的分数，所以...

apples = 6 points
oranges = 7 points
bananas = 7 points
blueberries = 11 points

我想创建一个包含一对 (A,B) 的列表，其中包含来自 A 的索引或来自 B 的索引，或两者都包含，而不更改它们在每个列表中出现的顺序。

每对都有其项目的分数，因此通过配对项目，我们将两个项目的总分减半。我想获得得分最小的对组合。

例如，在上面的两个列表中，每个项目都可以配对，但有些配对会阻止我们配对其他项目，因为我们不能在不更改其中一个列表的顺序的情况下将两者配对。例如，我们不能将 “blueberries” 配对，也不能将 “oranges” 配对，因为 “oranges” 出现在之前 “blueberries” 在一个列表中，但在另一个列表中之后。我们只能配对一个或另一个。每个列表也可以多次包含相同的项目。

上述问题的最优结果是...

    +---+---+----------------+-------+
    | A | B | Value          | Score |
+---+---+---+----------------+-------+
| 0 | 0 | 0 | "apples"       | 6     |
+---+---+---+----------------+-------+
| 1 | - | 1 | "blueberries"  | 11    |
+---+---+---+----------------+-------+
| 2 | 1 | 2 | "oranges"      | 7     |
+---+---+---+----------------+-------+
| 3 | 2 | 3 | "bananas"      | 7     |
+---+---+---+----------------+-------+
| 4 | 3 | - | "blueberries"  | 11    |
+---+---+---+--------+-------+-------+
                     | Total | 42    |
                     +-------+-------+

我认为答案是这样的:

1. 找到对
2. 将这些对分成可能的对组
3. 计算权重最大的组

我可以通过将一个列表中的对连接到另一个列表来确定哪些对在视觉上排除了哪些其他对，如果该连接与另一个连接相交，它将排除它。我不确定这将如何以编程方式完成。

我该如何解决这个问题？

Answer 1

请注意，我的回答假设只有 2 个列表，并且每个列表中的项目最多只能出现一次。

您要做的第一件事是构建一个 map /字典，其中项目作为键，一对整数作为值。该映射将包含两个数组中一项的索引。遍历第一个列表并将索引放在该对的第一个值中，将 -1 放在第二个值中。对第二个列表执行相同的操作，但显然将索引放在第二个值中。像这样:

pairs = map<string, pair<int, int>>

i = 0
while i < A.Length
    pairs[A[i]].first = i
    pairs[A[i]].second = -1
    i++
i = 0
while i < B.Length
    pairs[B[i]].second = i
    i++

现在，您必须确定可以进行哪些配对组合。此伪代码创建所有可能组合的列表:

i = 0
while i < A.Length
    j = i
    index = -1
    combination = list<pair>
    while j < A.Length
        pair = pairs[A[j]]
        if pair.second > index
            combination.add(pair)
            index = pair.second
        j++
    combinations.add(combination)
    i++

现在，剩下的就是权衡可能的组合，但不要忘记包括未配对的项目。

编辑

我现在想的是为每个项目构建一个包含所有可能对的映射。会产生以下结果的东西。

oranges: [0,2][0,5][5,2][5,5][0,-1][-1,2][5,-1][-1,5]
apples: [1,1][1,-1][-1,1]
bananas: [2,3][2,-1][-1,3]
... 

使用排除逻辑，我们可以对这些对进行分组并生成对列表的映射。

oranges: [0,2][5,-1][-1,5], [0,5][5,-1][-1,2], ..., [0,-1][5,-1][-1,2][-1,5]
apples: [1,1], [1,-1][-1,1]
...

现在，在结果输出中只能使用每个项目的一对列表，并且一些列表在不同项目之间相互排除。剩下的就是想出一个算法来权衡每种可能性。