algorithm - 重新缩放整数向量

Question

假设我有一个正整数向量 V。如果整数的总和大于正整数 N，我想重新调整 V 中的整数，使总和 <= N。V 中的元素必须保持在零以上。 V的长度保证为<= N。

是否有一种算法可以在线性时间内执行这种重新缩放？

这不是家庭作业，顺便说一句 :)。我需要将映射从符号重新调整为符号频率以使用范围编码。

一些快速思考和谷歌搜索没有给出问题的解决方案。

编辑:

好吧，这个问题有点不清楚。 “重新缩放”意味着“正常化”。也就是说，将 V 中的整数(例如通过将它们乘以常数)转换为更小的正整数，从而满足 sum(V) <= N 的标准。保留的整数之间的比率越好，压缩效果就越好。

问题在这种情况下是开放式的，该方法不需要找到最佳(例如，最小二乘拟合意义上)的方式来保持比率，而是一个“好的”方式。按照建议将整个向量设置为 1 是 Not Acceptable (除非被迫)。例如，找到满足总和标准的最小除数(定义如下)就足够了。

下面的朴素算法不起作用。

1. 求当前sum(V), Sv
2. 除数 := int(ceil(Sv/N))
3. 将 V 中的每个整数除以除数，向下舍入，但不小于 1。

这在 v = [1,1,1,10] 且 N = 5 时失败。

divisor = ceil(13 / 5) = 3.
V := [1,1,1, max(1, floor(10/3)) = 3]
Sv is now 6 > 5.

在这种情况下，正确的规范化是 [1,1,1,2]

一种可行的算法是对除数(如上定义)进行二进制搜索，直到找到 [1,N] 中满足总和标准的最小除数。从 ceil(Sv/N) 猜测开始。然而，这在操作次数上不是线性的，而是与 len(V)*log(len(V)) 成正比。

我开始认为在一般情况下不可能在线性时间内做好。我可能会求助于某种启发式方法。

Answer 1

只需将所有整数除以它们的 Greatest Common Divisor .您可以通过 Euclid's Algorithm 的多个应用程序有效地找到 GCD .

d = 0
for x in xs:
    d = gcd(d, x)

xs = [x/d for x in xs]

积极的一点是，您始终以这种方式获得尽可能小的表示，而不会丢失任何精度，也无需选择特定的 N。缺点是，如果您的频率是大的互质数，您将别无选择，牺牲精度(并且您没有指定在这种情况下应该做什么)。