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

На входе имеем набор 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).
  • Вопрос задан
  • 7370 просмотров
Решения вопроса 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Для разбиения на две группы задача сводится к задаче о рюкзаке с весом рюкзака равным половине общего веса камней и ценностью камней равной их весу.
Ответ написан
adugin
@adugin Автор вопроса
В итоге я сделал полный перебор с исключением заведомо неоптимальных решений. Судя по википедии, это "Метод ветвей и границ". По моим наблюдениям, в зависимости от исходных данных, обсчёт набора из 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
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
Как уже написали, эта задача сводится к задаче о рюкзаке. Так как вам нужна скорость, предлагаю использовать жадный алгоритм, примерно таким образом:

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы