在加权项之间分配点的算法？

Question

我有100分可以分发给一组物品.每个项目必须获得相对于其他项目的比例数量的点数(权重).有些项目的权重可能为0,但必须获得一些积分.

我尝试通过给每个项目5分,然后按比例输出剩余的分数来做到这一点,但是当我有21个项目时,算法将0分配给一个项目.当然,我最初可以提出1点,但问题仍然是101件或更多.通常,这个算法应该处理少于20个项目,但我希望算法在面对更多项目时是健壮的.

我知道使用浮点数/分数是完美的,但底层系统必须接收整数,总数必须为100.

这是框架/语言无关的,虽然我将在Ruby中实现.

目前,我有这个(伪代码):

total_weight = sum_of(items.weight)
if total_weight == 0 then
  # Distribute all points equally between each item
  items.points = 100 / number_of_items
  # Apply remaining points in case of rounding errors (100 / 3 == [33, 33, 34])
else
  items.points = 5
  points_to_dole_out = 100 - number_of_items * 5
  for(item in items)
    item.points += item.weight * total_weight / 100
  end
end

Answer 1

首先,给每个项目一点.这是为了满足您所有项目获得积分的要求.然后得到每个项目的总重量的百分比,并将剩余点数的百分比(向下舍入)奖励.

将剩下部分积分.按小数部分的大小对项目集进行排序,然后按从最大小数部分到最小部分的顺序逐个发出剩余的点数.

因此,如果一件物品的重量为12,所有物品的总重量为115,那么你首先要奖励它1分.如果还有4个其他项目,那么在获得最低分数后将剩下110分.然后,您将奖励该项目10分,因为它占总重量的百分比是9.58和10.538 9.58%的110.然后您将根据.538进行排序,如果它接近顶端,它可能最终会被撞到一个11.