想象一下，您有两个具有相同数量的 bin 的直方图。N 个观测值分布在各个 bin 之间。每个 bin 现在有 0 到 N 个观测值。
什么算法适合确定要从两个直方图中删除的最小观测数，以使它们成比例？它们的绝对数量不需要相等，只需彼此成比例即可。也就是说，必须有一个公因子，一个直方图中的所有 bin 都可以乘以这个因子，以使其与另一个直方图相等。
例如，想象以下两个直方图，其中每个直方图中的项目 i 指的是相应直方图的 bin i 中的观察数。
直方图 1：
4、7、4、9 直方图 2：2、0、2、1
对于这些直方图，解决方案是从直方图 1 中删除 bin 2 中的所有 7 个观测值，并从 bin 4 中删除另外 7 个观测值，使得 (histogram 1)*2 = histogram 2。
但是，可以使用什么通用算法来找到两个直方图的子集，使它们之间的总观察数最大化，同时使它们成比例？您可以从两个直方图中删除观察值，也可以只删除其中一个。
谢谢！
在我看来，问题是等价的（如果您将每个直方图视为 N 维向量），以最小化曼哈顿长度 |R|，其中 R=xA-B，A 和 B 是您的“向量”，x 是您的比例尺。
|R| 有一个最小值（不一定是整数），因此您可以使用简单的二分算法（或类似于牛顿法的方法）相当快地找到它。
然后，假设您想要一个比例为整数的解决方案，请测试两种情况 ceil(x) 和 floor(x)，以找出曼哈顿长度最小的情况（这就是您需要删除的观察次数） .
证明问题不是 NP 难的：
考虑一个低效的“解决方案”，您可以从所有箱中删除所有 N 个观察值。现在A和B都等于“零”直方图0 = (0,0,0,...)。这两个直方图是相等的，因此对于所有比例值s成比例为0 = s * 0，因此要删除的观测数的硬最大值是 N。
现在假设存在一个更有效的解决方案，其中 Assitions/removals < N 和比例尺度 s > 2*N （即在删除一些观察 A = N * B或B =N * A之后）。如果A = 0和B = 0，我们有前面的解决方案有 N 个移除（这与移除少于 N 个的假设相矛盾）。如果A = 0且B ≠ 0则不存在 s <> 0 使得0 = s * B并且不存在 s 使得 s * 0 = B（对于B = 0和S ≠ 0有类似的论点）。所以一定是A ≠ 0和B ≠ 0的情况。假设A是要缩放的直方图（所以A * s = B），A必须至少有一个非零条目A [i] 最小值为 1 （在去除额外的观察值之后），所以当缩放它将具有最小值≥。因此等价的条目B[i] 还必须至少有 2*N 个观测值。但是观察的总数最初是 N，所以我们需要向B [i] 添加至少 N 个观察，这与改进的解决方案的添加/删除少于 N 的假设相矛盾。因此，没有“有效”解决方案需要大于 N 的比例尺度。
因此，要找到一个有效的解决方案，在最坏的情况下，需要测试 0-N 范围内缩放因子的“最佳拟合”解决方案。
A = s * B中比例因子s的“最佳拟合”解决方案，其中A和B有 M 个 bin，每个都需要
{ Abs( A [i]- s * B [i]) mod s + Abs( A [i]- s * B [i]) div s } 添加/删除的总和（i=1 到 M）。
这是一个 M 阶操作，因此要测试 0-N 范围内的每个缩放因子将是一个O (M*N)阶算法
我相当肯定（但没有正式的证据），比例因子不能超过最填充箱中的观察数量。在实践中，它通常要小得多。对于具有 200 个 bin 且每个 bin 随机选择 30-300 个观测值的两个直方图：如果分别在A和B的所有 bin 中存在 Na > Nb 总观测值，则比例因子几乎总是在 Na/Nb-4 范围内找到< s < Na/Nb + 4，（如果 Na >> Nb，则s = 0）。