Балансировка нагрузки: как разбить набор чисел на две части с примерно равными суммами?

Question

[Andrey Dugin]

На входе имеем набор D из N чисел. Требуется оптимальным образом разбить его на два так, чтобы суммы чисел в получившихся наборах были примерно равны:

D(N) ==> D1(N1) и D2(N2), причём ABS(SUM(D1)-SUM(D2))=MIN, N1+N2=N, SUM(D1)+SUM(D2)=SUM(D)

Я сделал простейшую реализацию через random и большое число итераций, но хотел бы написать чёткий и быстрый алгоритм (понимаю, что в общем случае устойчивость не гарантируется). Подскажите пожалуйста, в какую сторону копать? Хотя бы ключевые слова для гуглинга (подозреваю, что это из области алгоритмов кластеризации). Был бы также интересен алгоритм разбиения на произвольное число частей M (М меньше N).

Answer 1

[Rsa97]

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

Comments

[Andrey Dugin]

Да, похоже, именно так и есть. Почитаю и вернусь чуть позже. Спасибо!

[Rsa97]

@pygame Мысля о подборе половины суммарного веса возникла сразу, про алгоритм рюкзака я что-то где-то когда-то читал. Оставалось только найти его описание и убедиться, что он здесь подходит, заодно наткнувшись на пару обсуждений такой же задачи.

Answer 2

[Andrey Dugin]

В итоге я сделал полный перебор с исключением заведомо неоптимальных решений. Судя по википедии, это "Метод ветвей и границ". По моим наблюдениям, в зависимости от исходных данных, обсчёт набора из 25 чисел может занять от всего ~20 и вплоть до 3.5М циклов. На Python 2.7:

# -*- coding: utf-8 -*-

from random import randint
from itertools import combinations

#data = [53, 50, 74, 4, 11, 68, 65, 50, 25, 84, 65, 63, 14, 54, 49, 17, 65, 48, 74, 66]
data = [randint(1,100) for i in xrange(25)]
#data = [990,1,2,3,1000]

data.sort(reverse=True)
limit = float(sum(data))/2
# Pre-calculate min and max possible number of elements in a group
bounds = [0, 0]
for i in (0,1):
    maxsum = 0
    for n, item in enumerate(data[::(1,-1)[i]], 1):
        cursum = maxsum + item
        if cursum <= limit:
            maxsum = cursum
        else:
            bounds[i] = n - int(n > 1)
            break
nmin, nmax = bounds
# Main calculations
maxsum, cycles = 0, 0
for n in xrange(nmin, nmax+1):
    # The following check could be efficient with integer numbers, not float
    if maxsum == limit:
        # One of exact solutions has been found
        break
    else:
        # Iterate through all possible combinations:
        # combinations('ABCD', 2) --> AB AC AD BC BD CD
        for vector in combinations(data, n):
            cycles += 1
            cursum = sum(vector)
            if maxsum < cursum <= limit:
                maxsum = cursum
                solution = vector
                # The following check could be efficient with integer numbers, not float
                if maxsum == limit:
                    # One of exact solutions has been found
                    break
            elif cursum <= maxsum:
                # No reason to continue because data is sorted in descending order 
                # and all of the following sums in this loop will be even smaller
                break
# Print result
print 'data =', data
print 'nmin =', nmin
print 'nmax =', nmax
print 'solution =', solution
print 'cycles =', cycles
print 'limit =', limit
print 'sum =', maxsum

Answer 3

[Андрей Вершинин]

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

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

Comments

[Rsa97]

3а. Попробовать добавить ещё один элемент так, чтобы уменьшился модуль разности между суммой выборки и общей суммой делённой на количество частей.

[Andrey Dugin]

В общем случае это решение не удовлетворяет условию ABS(SUM(D1)-SUM(D2))=MIN. Мне интересно найти наиболее быстрый алгоритм, дающий точное решение (или любое из нескольких эквивалентных).

[Андрей Вершинин]

@adugin Вы писали "примерно" равны. А слова "точное" и "быстро" в этом случае не очень сочетаются. Ваша задача называется мультипликативной задачей о рюкзаке с ограничением на каждый из ранцев равным sum(D) / N. Вам точно нужно для N разбиений или только для двух?

[Andrey Dugin]

@WolfdalE "Примерно равны" обозначает лишь, что суммы частей могут быть не равны (в общем случае). Я задал условие, что разность сумм должна быть минимальна, т.е. требуется максимально возможное приближение к равенству. Моя задача (балансировка нагрузки) не является мультиликативной, т.к. её достаточно решить для одного рюкзака (любого из двух), во второй уйдёт всё остальное. Мне интересно и N=2, и N>2.

[Andrey Dugin]

@WolfdalE Уточню: задача в моей формулировке не является мультипликативной именно для двух рюкзаков.