Weight based mapping algorithm

Question

I am writing automatic assignment of tasks to the users. Every user has a weight (integer) and tasks should be distributed to the users according to their weights. For example I have 10 tasks and User A with weight 5, User B with weight 3 and User C with weight 2. Mapping function should assign User A with 5 task, B with 3 tasks, C with 2. This example is very straightforward, but it is not that easy when it comes to 34 users and 230 tasks for example. Is there any known algorithm i should look for?

• Kilian Foth: This is structurally the same problem as assigning seats in a parliamentary body to parties based on their number of votes. Search for "voting algorithms" to find solutions, or "voting paradoxes" if you want to be horrified.

Answer 1

The algorithm seems simple enough, apart from rounding errors.

1. Add up all the weights => Wt.
2. Allocate each user a number of tasks = N times user weight Wx / Wt, rounded down.
3. There should be about N/2 task left over due to rounding. Allocate 1 task to each user in descending order of magnitude of rounding error (or any other algorithm if you prefer).