Предложение по алгоритму распределения объектов различного значения

Question

У меня следующая проблема:

Учитывая N объектов (N <30) с различными значениями, кратными константе «k», т.е. k, 2k, 3k, 4k, 6k, 8k, 12k, 16k, 24k и 32k, мне нужен алгоритм, который будет распределять все предметы для M игроков (M <= 6) таким образом, чтобы общая стоимость объектов, которые получает каждый игрок, была как можно более равномерной (иными словами, я хочу распределить все объекты среди всех игроков самым справедливым способом). </p>

РЕДАКТИРОВАТЬ: Под честным распределением я имею в виду, что разница между стоимостью объектов, которые получают два игрока, минимальна. Другой похожий случай: у меня N монет разных ценностей, и мне нужно делить их поровну между M игроками; иногда они не делятся точно, и мне нужно найти следующий лучший вариант распределения (где ни один игрок не злится, потому что другой получил слишком много денег).

Мне не нужен (псевдо) код для решения этой проблемы (также это не домашняя работа :)), но я буду признателен за любые идеи или ссылки на алгоритмы, которые могут решить эту проблему.

Спасибо!

Answer 1

Проблема сильно NP-полная. Это означает, что невозможно найти правильное решение в разумные сроки. (См. Проблема с 3 разделами , спасибо, Пол).

Вместо этого вы захотите найти хороший примерный генератор решений. Они часто могут быть очень близки к оптимальному ответу за очень короткое время. Я могу порекомендовать метод Имитация отжига , который вы также сможете использовать для множества других NP-полных задач.

Идея такова:

1. Распределите предметы случайным образом.
2. Постоянно производите случайные обмены между двумя случайными игроками, если это делает систему более честной или чуть менее справедливой (см. Вики в деталях).
3. Остановитесь, когда у вас будет что-то достаточно справедливое или у вас закончится время.

Это решение намного сильнее, чем многие жадные алгоритмы. Жадный алгоритм - это тот, в котором вы постоянно добавляете самый крупный предмет в «самого бедного» игрока. Пример тестового примера, где жадный сбой - [10,9,8,7,7,5,5].

---

Я сделал реализацию SA для вас. Это следует за статьей вики строго, в образовательных целях. Если вы оптимизируете его, я бы сказал, что улучшение в 100 раз не будет нереальным.

from __future__ import division
import random, math

values = [10,9,8,7,7,5,5]
M = 3
kmax = 1000
emax = 0

def s0():
    s = [[] for i in xrange(M)]
    for v in values:
        random.choice(s).append(v)
    return s

def E(s):
    avg = sum(values)/M
    return sum(abs(avg-sum(p))**2 for p in s)

def neighbour(s):
    snew = [p[:] for p in s]
    while True:
        p1, p2 = random.sample(xrange(M),2)
        if s[p1]: break
    item = random.randrange(len(s[p1]))
    snew[p2].append(snew[p1].pop(item))
    return snew

def P(e, enew, T):
    if enew < e: return 1
    return math.exp((e - enew) / T)

def temp(r):
    return (1-r)*100

s = s0()
e = E(s)
sbest = s
ebest = e
k = 0
while k < kmax and e > emax:
    snew = neighbour(s)
    enew = E(snew)
    if enew < ebest:
        sbest = snew; ebest = enew
    if P(e, enew, temp(k/kmax)) > random.random():
        s = snew; e = enew
    k += 1

print sbest

Обновление: После игры с Branch'n'Bound я теперь считаю, что этот метод лучше, так как он дает отличные результаты для случая N = 30, M = 6 в течение секунды. Тем не менее, я думаю, вы могли бы так же поиграть с имитацией отжига.

Answer 2

Жадное решение, предложенное несколькими людьми, кажется лучшим вариантом, я запускал его несколько раз со случайными значениями, и, кажется, каждый раз получаю правильное решение.
Если он не оптимален, он, по крайней мере, очень близок, и работает в O (нм) или около того (я не могу потрудиться сделать математику прямо сейчас)
Реализация 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);
    foreach (int val in sortedValues)
    {
        var lowest = result.OrderBy(a => a.Sum()).First();
        lowest.Add(val);
    }
    return result;
}

Answer 3

Это прямая реализация ответа Джастина Пила:

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]

Я новичок в Python, но, похоже, все в порядке. Этот пример напечатает

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

Answer 4

Повторно дайте доступный объект с наибольшим значением игроку, которому назначено наименьшее общее количество объектов.

Answer 5

как насчет этого:

порядок значений k. заказать игроков.

Зацикливайте значения k, передавая следующее значение следующему игроку. когда вы доберетесь до конца игроков, развернитесь и продолжайте давать значения k игрокам в обратном направлении.

Answer 6

EDIT:

Цель состояла в том, чтобы использовать жадное решение с небольшим улучшением в реализации, которое может быть прозрачным в 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; 
} 

Относительно этого этапа:

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]

Идея состоит в том, что список всегда сортируется (в этом коде это делает OrderBy). В конце концов, эта сортировка не займет больше, чем O (log (n)) - потому что нам просто нужно ВСТАВИТЬ не более одного элемента в отсортированный список - что должно быть так же, как бинарный поиск. Поскольку нам нужно повторить эту фазу для sortedValues.Longth раз, весь алгоритм работает в O (M * log (n)).

Итак, на словах это можно перефразировать как: Повторяйте шаги ниже, пока не закончите значения Values: 1. Добавить наибольшую ценность для самого маленького игрока 2. Проверьте, есть ли у этого игрока наименьшая сумма 3. Если да, перейдите к шагу 1. 4. Вставьте последнего полученного игрока в список отсортированных игроков

Шаг 4 - это шаг O (log (n)) - так как список всегда сортируется.

Answer 7

30 ^ 6 не такой большой (это менее 1 миллиарда). Пройдите каждое возможное распределение и выберите тот, который является самым справедливым по любой мере, которую вы определяете.