我有一个不变的基本列表，像这样：
[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]。
我将如何防范呢？
这可以通过使用匈牙利算法在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）解决方案，但是需要更多的精力才能读回解决方案。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句