Как равномерно раскидать N чисел по K контейнерам?

Рейтинг: 3Ответов: 1Опубликовано: 11.11.2014

Что-то не соображу, как оптимально решается такая задача:

Есть "случайный" набор N чисел от 0 до M. Распределение примерно экспоненциальное: мелких больше.

Их надо раскидать среди K контейнеров так, чтобы минимизировать разброс сумм чисел в контейнерах.

Думал, надо найти среднее, к которому стремиться; отсортировать набор и брать с краёв. Но не понятно, на чём останавливаться, когда набираю сумму в очередной контейнер. Вот, недобрал до "золотой середины" 5%, это хорошо, или ещё постараться? Явно неоптимально так наугад брать.

Upd. наверное, задача не самая простая. Похоже на одномерную «задачу об упаковке» + комбинаторику.

статистика математика алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 1Принят

Что сразу приходит в голову (но он вроде не такой хороший).
Начать распределять с больших чисел и раскидывать в наименьшую ячейку. Более мелкие значения будут обтесывать неравенство.

Обновление

Не понимаю, зачем жестко брать самое большое + самое маленькое? Сортируем по убыванию, к примеру получили [5 4 3 3 2 2 1 1 1]. И надо разбить на 3 контейнера:

  1. 5 = 4 = 3 // взяли 3 самых больших: 5,4,3
  2. 5 = 4 = 6 // число 3
  3. 5 = 6 = 6 // число 2
  4. 7 = 6 = 6 // число 2
  5. 7 = 7 = 7 // два числа 1, 1
  6. 8 = 7 = 7 // последнее число 1

Данный метод считаю наиболее простым, но, к сожалению, есть случаи, когда разброс будет неидеальным.