将两个有序列表中的加权项目配对，同时保持顺序

Question

我正在寻找解决这个问题的算法：

我有两个列表，例如：

A = {a, b, c, d}
B = {e, f, g}

和 table 告诉我一个列表中的每个项目与另一个列表中的项目的匹配程度。例如：

	e	f	g
a	10	2	1
b	1	0	2
c	2	0	0
d	1	20	0

现在我需要将 A 的项目与 B 的项目配对，以便匹配的总和最大化，同时保持两个列表的顺序并且每个项目只使用一次。并非所有项目都需要匹配。

对于这个例子，解决方案是：

[{a, e}, {d, f}]

Answer 1

简介

你可以使用动态规划来解决你的问题，一个元素dp[i][j]表示到当前位置i,j为止达到的最大可能总和。 i 对应于一个列表中的第 i 个元素，j 对应于另一个数组中的第 j 个元素。

流量

我会 Python 来起草一个算法，尽管同样的算法在 JAVA 或 C++ 等其他语言中会表现得更好。但是，使用 Python，它的可读性更高（恕我直言）。

准备

为简洁起见，我假设您的 table 总是至少有 2 行和列。

table个火柴和table个火柴的大小可以表示为：

n, m = 4, 3 # n stands for number of rows, and m - columns
matches = [[10, 2, 1],
  [1, 0, 2],
  [2, 0, 0],
  [1, 20, 0]]

创建一个 dp 数组，最初包含与 matches:

相同的元素

dp = matches

求最大总和

现在，要计算 dp[i][j] 的最大总和，我们必须考虑 4 个案例：

dp[i][j]可以是最大值。
dp[i][j - 1]是最大值。
dp[i - 1][j]是最大的
dp[i - 1][j - 1] + dp[i][j]是最大值

所以，可以这样来做：

for j in range(m):
    for i in range(n):
        top = -1
        if i > 0:
            top = dp[i - 1][j]
        left = -1
        if j > 0:
            left = dp[i][j - 1]
        topLeft = -1
        if i > 0 and j > 0:
            topLeft = dp[i - 1][j - 1]

        dp[i][j] = max(topLeft + dp[i][j], top, left, dp[i][j])

很好，如果你打印出来 dp[n - 1][m - 1]，你会看到你的任务的最大总和。

打印总和最大的序列

基本上，您必须执行相反的过程才能打印出序列。您应该从 dp[n - 1][m - 1] 开始，因为它表示最大总和。

所以，向左走，检查左边的元素是否与最大值不同。如果不同，则当前元素仅在不等于上面的元素时才属于序列（这意味着 dp[i-1][j-1] + dp[i][j] 或 dp[i][j] 是最大的）。

另一种选择是最左边的元素也是最大的。然后，向上寻找原点最大元素并停止程序。

因此，重复上面一行的主要过程，直到构建序列。

solution = []
i = n - 1
j = m - 1
done = False
while i >= 0 and not done:
    current_max = dp[i][j]
    while j > 0:
        if dp[i][j - 1] != current_max:
            break
        j -= 1

    if j <= 0:
        while i > 0 and dp[i][0] == dp[i - 1][0]:
            i -= 1
        solution.append((i, j))
        done = True
        break

    if i == 0 or dp[i][j] != dp[i - 1][j]:
        solution.append((i, j))
        j -= 1

    i -= 1

完整代码

# n - rows
# m - columns
n, m = 4, 3
matches = [[10, 2, 1],
      [1, 0, 2],
      [2, 0, 0],
      [1, 20, 0]]

A = ['a', 'b', 'c', 'd']
B = ['e', 'f', 'g']

dp = matches

for j in range(m):
    for i in range(n):
        top = -1
        if i > 0:
            top = dp[i - 1][j]
        left = -1
        if j > 0:
            left = dp[i][j - 1]
        topLeft = -1
        if i > 0 and j > 0:
            topLeft = dp[i - 1][j - 1]

        dp[i][j] = max(topLeft + dp[i][j], top, left, dp[i][j])

print (dp[n - 1][m - 1])

solution = []
i = n - 1
j = m - 1
done = False
while i >= 0 and not done:
    current_max = dp[i][j]
    while j > 0:
        if dp[i][j - 1] != current_max:
            break
        j -= 1

    if j <= 0:
        while i > 0 and dp[i][0] == dp[i - 1][0]:
            i -= 1
        solution.append((i, j))
        done = True
        break

    if i == 0 or dp[i][j] != dp[i - 1][j]:
        solution.append((i, j))
        j -= 1

    i -= 1

while len(solution) > 0:
    i, j = solution.pop()
    print ('(%s,%s)' % (A[i], B[j]))

将两个有序列表中的加权项目配对，同时保持顺序

Pairing weighted items from two ordered lists while maintaining the order

algorithm

language-agnostic

combinatorics

简介

流量

准备

求最大总和

打印总和最大的序列

完整代码