c++ - 如何平衡两个数组之间的差异如最小化？

Question

我有一个数组A[]={3,2,5,11,17}，并且B[]={2,3,6}B 的大小总是小于 A。现在我必须将每个元素 B 映射到A 的不同元素，以使总差异sum( abs(Bi-Aj) )变得最小（其中 Bi 已映射到 Aj）。算法的类型是什么？

对于示例输入，我可以选择 、2->2=0，3->3=0然后选择6->5=1。所以总成本是 0+0+1 = 1。我一直在考虑对两个数组进行排序，然后sizeof B从 A 中取出第一个元素。这行得通吗？

Answer 1

它可以被认为是一个不平衡的分配问题。

成本矩阵应为 B[i] 和 A[j] 的值之差。您可以向 B 添加虚拟元素，以使问题变得平衡，并使相关的成本非常高。

然后可以应用匈牙利算法来解决它。

对于示例情况 A[]={3,2,5,11,17} 和 B[]={2,3,6}，成本矩阵应为：

.   3  2  5 11 17
2   1  0  3  9 15
3   0  1  2  8 14
6   3  4  1  5 11
d1 16 16 16 16 16
d2 16 16 16 16 16