将一个列表与另一个列表进行匹配，误差最小

Question

我有两个列表，A和B.A最多只有1000个元素，而B最多只有100个元素。我想将B的每个元素都匹配到A的一个元素，这样这些对的绝对差值之和就会最小化。

即我想选择| B |从A得到不同的索引，并将它们分配给B的索引，使得以下和最小化：sum（abs（A [j] -B [i]），其中| B |，j = index_mapping（i））。

我的第一种方法是：

1. 对于B的每个元素，以计算| B |答：
2. 的最接近元素选择在一个贪婪的方式对（即误差最小第一）

用一些简单的例子播放，很明显，我的方法是不是最好的。它应该适合我的目的，但我想知道是否有人可以提出更好的方法？

Answer 1

我结束了对这两个列表的排序，并遍历它们进行匹配。这对我所做的工作足够好。

Answer 2

唔......手头上，想到的第一个想法是，如果你可以对A和B进行排序，那么一旦你找到A [j]到B [i]的第一个映射，那么对于B [i +1]，你可以用A [j]而不是A [0]开始你的测试。

例如：

A = [ 23, 34, 38, 52, 67, 68, 77, 80, 84, 95 ] 
B = [ 31, 33, 64, 65, 99 ] 

你开始B [0] = 31，通过台阶，直到找到最接近的匹配，A [1]。由于列表是有序的，所以你知道 B [1]不会匹配小于A [1]的任何东西，所以你可以从那里开始比较。原来，A [1]仍然是最接近的匹配。在B [2]中，最接近的匹配是A [4]，所以你知道B [3]不会匹配低于A [4]的任何东西，所以不需要通过A [3]搜索A [0]。