将一个范围列表缩放到另一个范围的算法

Question

我有一个固定的基本列表，如下所示:

[50, 100, 150, 200, 500, 1000]

列表定义了范围:0 到 50、50 到 100，一直到 1000 到无穷大。

我想编写一个函数，将任何数字列表转换为与上述列表兼容的列表。 “兼容”是指其中只有该列表中的数字，但数字尽可能接近原始值。因此，对于 [111, 255, 950] 的示例输入，我将得到 [100, 200, 1000]。到目前为止，我有一个像这样工作的天真的代码:

for each i in input
{
    calculate proximity to each number in base list
    get the closest number
    remove that number from the base list
    return the number
}

这适用于大多数情况，但当输入规模失控时就会崩溃。当我有像 [1000, 2000, 3000] 这样的输入时，第一个数字从基本列表中获取最后一个数字，然后 2000 和 3000 分别得到 500 和 200(因为 1000 和 500 已经采取)。这导致向后列表 [1000, 500, 200]。

我该如何防范？

Answer 1

方法一

这可以通过使用 Hungarian algorithm 在 O(n^3) 时间内解决。其中 n 是 max(len(list),len(input))。

首先建立一个矩阵，给出将每个输入分配给列表中每个数字的成本。

matrix[i,j] = abs(input[i]-list[j])

然后使用匈牙利算法找到输入与列表中数字的最小成本匹配。

如果列表中的数字多于输入，则添加一些额外的虚拟输入，这些输入与列表中的任何数字匹配的成本为零。

方法二

如果第一种方法太慢，那么您可以使用动态规划来计算最佳拟合。

我们的想法是计算一个函数 A(a,b)，它给出列表中前 a 个输入与前 b 个数字的最佳匹配。

A(a,b) = min( A(a-1,b-1)+matrix[a,b], A(a,b-1) )

这应该给出 O(n^2) 的解决方案，但需要更多的努力才能读回解决方案。