What's a good algorithm to distribute points between weighted items?

Question

I have 100 points to dole out to a set of items. Each item must receive a proportional number of points relative to others (a weight). Some items may have a weight of 0, but they must receive some points.

I tried to do it by giving each item 5 points, then doling out the remaining points proportionally, but when I have 21 items, the algorithm assigns 0 to one item. Of course, I could hand out 1 point initially, but then the problem remains for 101 items or more. Normally, this algorithm should deal with less than 20 items, but I want the algorithm to be robust in the face of more items.

I know using floats/fractions would be perfect, but the underlying system must receive integers, and the total must be 100.

This is framework / language agnostic, although I will implement in Ruby.

Currently, I have this (pseudo-code):

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

First, give every item one point. This is to meet your requirement that all items get points. Then get the % of the total weight that each item has, and award it that % of the remaining points (round down).

There will be some portion of points left over. Sort the set of items by the size of their decimal parts, and then dole out the remaining points one at a time in order from biggest decimal part to smallest.

So if an item has a weight of twelve and the total weight of all items is 115, you would first award it 1 point. If there were 4 other items, there would be 110 points left after doling out the minimum scores. You would then award the item 10 points because its percentage of the total weight is 9.58 and 10.538 9.58% of 110. Then you would sort it based on the .538 and if it were near the top end, it might end up getting bumped to a 11.

Answer 2

Hi

This might meet your requirements:

-- give every item 1 point since that is the minimum allowed;

-- now you have 100-N points left to dole out, each item gets its weighted share of what's left; apply some rounding rule when multiplying wt*(100-N);

-- if you round down you'll be left with some spare points, allocate them one at a time from the heaviest item downwards.

Any which way you do it you'll only get approximate allocation of points to items.

Regards

Mark

Answer 3

The 101 case cannot be solved given the two constraints {total == 100 } { each item > 0 } So in order to be robust you must get a solution to that. That's a business problem not a technical one.

The minimum score case is actually a business problem too. Clearly the meaning of your results if you dole out a min of 5 per item is quite different from a min score of 1 - the gap between the low, non-zero score and the low scores is potentially compressed. Hence you really should get clarity from the users of the system rather than just pick a number: how will they use this data?