Suggestion on algorithm to distribute objects of d

Question

I have the following problem:

Given N objects (N < 30) of different values multiple of a "k" constant i.e. k, 2k, 3k, 4k, 6k, 8k, 12k, 16k, 24k and 32k, I need an algorithm that will distribute all items to M players (M <= 6) in such a way that the total value of the objects each player gets is as even as possible (in other words, I want to distribute all objects to all players in the fairest way possible).

EDIT: By fairest distribution I mean that the difference between the value of the objects any two players get is minimal. Another similar case would be: I have N coins of different values and I need to divide them equally among M players; sometimes they don't divide exactly and I need to find the next best case of distribution (where no player is angry because another one got too much money).

I don't need (pseudo)code to solve this (also, this is not a homework :) ), but I'll appreciate any ideas or links to algorithms that could solve this.

Thanks!

Answer 1

This is a straight-forward implementation of Justin Peel's answer:

M = 3
players = [[] for i in xrange(M)]

values = [10,4,3,1,1,1]
values.sort()
values.reverse()
for v in values:
    lowest=sorted(players, key=lambda x: sum(x))[0]
    lowest.append(v)

print players
print [sum(p) for p in players]

I am a beginner with Python, but it seems to work okay. This example will print

[[10], [4, 1], [3, 1, 1]]
[10, 5, 5]

Answer 2

EDIT:

The purpose was to use the greedy solution with small improvement in the implementation, which is maybe transparent in C#:

static List<List<int>> Dist(int n, IList<int> values) 
{ 
    var result = new List<List<int>>(); 
    for (int i = 1; i <= n; i++) 
        result.Add(new List<int>()); 
    var sortedValues = values.OrderByDescending(val => val);//Assume the most efficient sorting algorithm - O(N log(N))
    foreach (int val in sortedValues) 
    { 
        var lowest = result.OrderBy(a => a.Sum()).First();//This can be done in O(M * log(n)) [M - size of sortedValues, n - size of result]
        lowest.Add(val); 
    } 
    return result; 
} 

Regarding this stage:

var lowest = result.OrderBy(a => a.Sum()).First();//This can be done in O(M * log(n)) [M - size of sortedValues, n - size of result]

The idea is that the list is always sorted (In this code it is done by OrderBy). Eventually, this sorting wont take more than O (log(n)) - because we just need to INSERT at most one item into a sorted list - that should take the same as a binary search. Because we need to repeat this phase for sortedValues.Length times, the whole algorithm runs in O(M * log(n)).

So, in words, it can be rephrased as: Repeat the steps below till you finish the Values values: 1. Add the biggest value to the smallest player 2. Check if this player still has the smallest sum 3. If yes, go to step 1. 4. Insert the last-that-was-got player to the sorted players list

Step 4 is the O (log(n)) step - as the list is always sorted.

Answer 3

The greedy solution suggested by a few people seems like the best option, I ran it a bunch of times with some random values, and it seems to get it right every time.
If it's not optimal, it's at the very least very close, and it runs in O(nm) or so (I can't be bothered to do the math right now)
C# Implementation:

static List<List<int>> Dist(int n, IList<int> values)
{
    var result = new List<List<int>>();
    for (int i = 1; i <= n; i++)
        result.Add(new List<int>());
    var sortedValues = values.OrderByDescending(val => val);
    foreach (int val in sortedValues)
    {
        var lowest = result.OrderBy(a => a.Sum()).First();
        lowest.Add(val);
    }
    return result;
}

Answer 4

30 ^ 6 isn't that large (it's less than 1 billion). Go through every possible allocation, and pick the one that's the fairest by whatever measure you define.

Answer 5

how about this:

order the k values. order the players.

loop over the k values giving the next one to the next player. when you get to the end of the players, turn around and continue giving the k values to the players in the opposite direction.

Answer 6

Repeatedly give the available object with the largest value to the player who has the least total value of objects assigned to him.