计算加权分配比率的算法

Question

这是我面临的问题。我有一些项目。然后我有不同数量的桶，它们的重量在 0 到 1 之间。我正在尝试计算每个桶中应该放入的项目的百分比。

例如，假设我有 20 个项目和 3 个桶：

• B1 - 重量：0.5
• B2 - 重量：0.5
• B3 - 重量：0.25

那么百分比将是：

• B1 - 40% 的项目 = 8 个项目
• B2 - 40% 的项目 = 8 个项目
• B3 - 20% 的物品 = 4 件

该百分比应增加到 100%，以便所有项目都将分配到存储桶中。在上面的例子中，B1 和 B2 的物品数量应该是 B3 的两倍，因为它们的重量是 B3 的两倍；但是，当所有 3 个桶放在一起时，B1 获得的项目的实际百分比是 40%。

是否已经有一个算法可以解决这个问题，或者你们中有人知道如何解决它吗？

Answer 1

我认为您可以将每个桶的重量除以所有物品的总重量，以找到每个桶应承载的物品百分比。

但是，如果物品的数量和桶的重量分配不均，则会出现一个小问题。为了举例，让我们考虑以下场景：

B1 - weight: 0.15
B2 - weight: 0.15
B3 - weight: 0.70

让我们假设有 23 个项目。

然后我们可以通过将总重量的分数乘以项目总数来计算应该分配给每个桶的项目数：

B1 - weight: 0.15, 3.45 items
B2 - weight: 0.15, 3.45 items
B3 - weight: 0.70, 16.1 items

可以处理这个分数桶问题的一种算法是计算每个桶的项目数，一次一个，然后将余数转移到下一次计算。所以，在这个例子中，我们会这样做：

B1 - 3.45 items, keep 3, rollover 0.45
B2 - 3.45 items + 0.45 = 3.9 items, keep 3, rollover 0.9
B3 - 16.1 items + 0.9 = 17 items (whole number, and last bucket)