如何在添加新值时保持恒定百分比

Question

我想制作一种算法，使用某个理想的百分比将实体总数分配到不同的类别中。例如，第一类应包含所有实体的 50.3%，第二类 - 34.3%，第三类 - 15.4%。

在某些理想条件下，一切都很好。我很容易为每个类别计算实体的期望值，然后使用类似于 this 的某种算法来保持正确的总和。小例子：

All categories are empty
We are adding 100
To the first 50
To the second = 34
To the third = 16 (fixed by current algorithm, was 15)

但是，在某些时候，类别已经可以包含一些未按照我们理想的百分比分布的实体！而且我不知道在这种情况下应该使用什么算法。该算法应使用这些规则分发新实体：

添加后我们应该尽可能接近理想的百分比。理想百分比和实际百分比之间的偏差应该很小并且彼此接近。
算法无法从任何类别中删除现有实体。它应该只分发新的。

示例：

At start:
First is empty
Second contains 10
Third contains 40

We are adding 50
To the first 38
To the second 12
To the third 0 (too much entities here before adding)

Result:
First = 38; deviation = 12.3%
Second = 22; deviation = 12.3%
Third = 40; deviation = 24.6%

不要问我是怎么得到 38 和 12 的，我只是尝试了不同的组合，直到看起来合适为止。关于算法有什么想法吗？

Answer 1

以下方法可能有效。假设您维护 3 个列表，每个类别 1 个，运行 avg（即列表的当前平均值）和总元素。需要额外的 2 个元素来确保添加元素的复杂性保持不变。

数据结构：

category_list {
    items : []
    average : float
    count : int
}

category_list categories[3]; # 1 for each category
avg_distribution[3]; # this will hold the distribution allowed for each category

算法：

addItems(int items[]) {
   for item in items:
     category = getCategory(item)
     insertItem(category, item)
}

# This algo will identify the category to be inserted in constant time or the no.of categories available. 
# For this scenario we can say it runs in O(1)
int getCategory(int item) {
   minAvg = INT_MAX
   minCat = 0
   for cat in range(3):
      category = categories[cat]
      newAvg = (category.avg*(category.count)+item.value) / (category.count+1)
      newAvg = newAvg - avg_distribution[cat] 
      # this is to make sure we consider only the deviation part and not the entire avg.
      if newAvg < minAvg:
         minAvg = minAvg
         minCat = cat 

   return minCat
}

# This will insert item in a given category in O(1)
insertItem(category, item) {
    category.items[category.count] = item.value
    category.avg = (category.avg*(category.count)+item.value) / (category.count+1)
    category.count++;
}

# This method is need to initially load all the elements in given category
loadAllItems(int items[], int category) {
    category = categories[category]
    for item in items:
       insertItem(category, item)
}

希望对您有所帮助！

如何在添加新值时保持恒定百分比

How to mantain constant percentage while adding new values

algorithm

percentage