0

假设您有一组理想比率，其总和 = 1。例如，

set = [0.2, 0.1, 0.4, 0.3]

但是假设有一条规则规定，如果它不等于 0，则它们都不应该低于一个值：

min = 0.25

直观地说，我们可以说一个很好的拟合是：

set = [0.25, 0, 0.425, 0.325]

但我真的不知道我在那里做了什么。

这种问题有名字吗？什么是通用解决方案？

4

3 回答 3

1

让这个最小值为m，一般的解决方案可能是：

while there is a none zero value smaller then `m`:
   x <- lowest value
   for each y != x:
      y += y*x/ (1-x)
   x <- 0

很容易看出，上述循环在每次迭代中都保留了 sum==1，因为：

除 x = 1-x 之外的所有元素的
总和因此，所有增加的总和为

 x/(1-x) * [sum of all elements excluding x] = x / (1-x) * (1-x) = x

因此，在每次迭代中，总和减少和增加相同的值，因此总和保持为 1。

于 2013-08-07T18:26:13.873 回答
1

算法

我认为这大约是您建议的算法（在 Python 中）：

def fx(arr, m): 
  arr.sort()
  if arr[0] >= m:
    return arr 

  return _fx(arr, m, 0)

def _fx(arr, m, i): 
  extra = arr[i]
  arr[i] = 0 

  for j in range(i + 1, len(arr)):
    if arr[j] >= m:
      break
    extra -= m - arr[j]
    arr[j] = m 
    if extra < 0:
      arr[j] += extra
      return _fx(arr, m, i + 1)

  numToBump = len(arr) - j 
  for k in range(j, len(arr)):
    arr[k] += extra / numToBump

  return arr

解释：

首先，我们对数组进行排序。如果第一个元素高于最小值，我们就完成了。否则，_fx使用我们的参数调用辅助方法 ()，加上归零的索引 ( 0)。

在辅助方法中，我们将i第 th 个元素清零并将其原始值存储为我们必须分配的“额外”数量。首先，我们尝试将小于最小值的所有元素提升到最小值，方法是从extra. 如果我们在完成之前用完了多余的东西，我们会尝试将下一个元素归零。

如果我们让所有的东西都高于最小值，那么我们将剩余的额外部分分配给我们尚未触及的元素。

注意：我以不同的顺序返回元素，但最后取消排序很容易。

例子

这些都使用0.25.

[0.1, 0.2, 0.3, 0.4] -> [0, 0.25, 0.325, 0.425]

[0.1, 0.1, 0.4, 0.4] -> [0, 0, 0.5, 0.5]
于 2013-08-07T20:18:48.867 回答
0

至少如果我理解正确，你想取最小的，如果它小于最小值，把它减少到零。然后将足够的（如果有的话）给下一个最小的以满足最小值。（如果不够，将下一个最小值归零，将其值添加到您正在分发的内容中，然后重复）。

当你有最小的到最小的，还有一些剩余的东西要分配给其他人时，你想先把其他人加起来得到一个总和。然后遍历其他数字，并将每个数字除以总和以获得比率。然后，每个人的金额是比率乘以您需要分配的金额。

例如，使用您的原始号码：

set = [0.2, 0.1, 0.4, 0.3]

我们将第二项归零，并将 0.05 分配给第一项，然后分配 0.05。

然后我们将另外两个相加得到 0.7。我们将其他每个除以得到它们的比率：0.4/0.7 和 0.3/0.7。然后我们将每个比率乘以 0.05，得到分配给每个比率的数量：4/7*.05 = .0285714... 和 3/7*.05 = .0214857...

所以我们每一个都加了那么多。当我们到达最后一个时，我们只需将剩下的所有相加，因此如果有任何舍入错误，我们的总和将保持原样。

于 2013-08-08T04:54:54.487 回答