Алгоритм сортировки списка значений по n группам так, чтобы сумма каждой группы была как можно ближе

Question

В основном у меня есть ряд значений, которые мне нужно разделить на n разных групп, чтобы суммы в каждой группе были как можно ближе к суммам в других? Список значений не очень длинный, поэтому я мог бы просто перебрать его, но мне было интересно, если кто-нибудь знает о более эффективном способе сделать это. Спасибо.

Answer 1

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

groups = [list() for i in range(NUM_GROUPS)]
for x in sorted(numbers, reverse=True):
    mingroup = groups[0]
    for g in groups:
        if sum(g) < sum(mingroup):
           mingroup = g
    mingroup.append(x)

Answer 2

Эта проблема называется " проблема многострочного разбиения " и действительно сложна в вычислительном отношении. Поиск в Google дал интересную статью "Многоканальное разделение чисел , где автор упоминает эвристику, предложенную larsmans, и предлагает несколько более продвинутых алгоритмов. Если приведенной выше эвристики недостаточно, вы можете посмотреть в газете или, возможно, связаться с автором, он, кажется, проводит исследования в этой области.

Answer 3

Знаете ли вы, на сколько групп нужно разбить его заранее?

У вас есть ограничение на максимальный размер группы?

Несколько алгоритмов для вариаций этой задачи:

• Алгоритм переноса слов Кнута

• алгоритмы, минимизирующие количество дискет, необходимых для хранения набора файлов, но сохраняющие любой файл, сразу читаемый с диска, на котором он хранится (вместо того, чтобы соединять его воедино из фрагментов, хранящихся на 2 дисках) - I слышать, что "копия на дискету с наилучшим соответствием" была популярна.

• Расчет списка раскроя с наименьшим количеством отходов. Расчет списка раскроя с наименьшим количеством отрезаемых отходов

• Что такое хороший алгоритм для сжатия записей в заблокированном файле? Что такое хороший алгоритм для сжатия записей в заблокированном файле?

• Учитывая N процессоров, как мне запланировать кучу подзадач так, чтобы вся работа была выполнена за минимальное время? многопроцессорное планирование .

Answer 4

Вы можете суммировать числа и делить на количество групп.Это дает вам целевое значение для сумм.Сортируйте числа и затем попытайтесь получить подмножества, чтобы сложить до необходимой суммы.Начните с максимально возможных значений, так как они будут вызывать наибольшую изменчивость сумм.Как только вы определите группу, которая не является оптимальной суммой (но близкой), вы можете пересчитать ожидаемую сумму оставшихся чисел (по n-1 группам), чтобы минимизировать среднеквадратичное отклонение от оптимального для оставшихся групп (если это показательВы заботитесь о).Комбинируя эту концепцию «ожидаемой суммы» с ответом Ларсмана, у вас должно быть достаточно информации, чтобы получить быстрый приблизительный ответ.Ничего оптимального в этом нет, но гораздо лучше, чем случайный и с красиво ограниченным временем выполнения.

Answer 5

Грубая сила может не сработать так, как вы думаете ...

Предположим, у вас есть 100 переменных и 20 групп:

• Вы можете поместить 1 переменную в 20 различных группах, что составляет 20 комбинаций.
• Вы можете поместить 2 переменных в 20 различных групп в каждой, что составляет 20 * 20 = 20^2 = 400 комбинаций.
• Вы можете поместить 3 переменных в 20 различных групп в каждой, что составляет 20 * 20 * 20 = 20^3 = 8000 комбинаций.
• ...
• Вы можете поместить 100 переменных в 20 различных групп в каждой, что составляет 20^100 комбинаций, что превышает минимальное количество атомов в известной вселенной (10^80).

Хорошо, вы можете сделать это немного умнее (не важно, куда вы положили первую переменную, ...), чтобы получить что-то вроде Branch and Bound , но , который будет по-прежнему масштаб ужасно .

Так что либо используйте быстрый детерминистический алгоритм, как предлагает larsman. Или, если вам нужно более оптимальное решение и у вас есть время для его реализации, взгляните на метаэвристические алгоритмы и программное обеспечение, которое их реализует (например, Drools Planner ).