Что-то не соображу, как оптимально решается такая задача: Есть "случайный" набор N чисел от 0 до M. Распределение примерно экспоненциальное: мелких больше. Их надо раскидать среди K контейнеров так, чтобы минимизировать разброс сумм чисел в контейнерах Думал, надо найти среднее, к которому стремиться; отсортировать набор и брать с краёв. Но не понятно, на чём останавливаться, когда набираю сумму в очередной контейнер. Вот, недобрал до "золотой середины" 5%, это хорошо, или ещё постараться? Явно неоптимально так наугад брать. Upd. наверное, задача не самая простая. Похоже на одномерную «задачу об упаковке» + комбинаторику.
Ответ
Что сразу приходит в голову (но он вроде не такой хороший). Начать распределять с больших чисел и раскидывать в наименьшую ячейку. Более мелкие значения будут обтесывать неравенство. Обновление Не понимаю, зачем жестко брать самое большое + самое маленькое? Сортируем по убыванию, к примеру получили [5 4 3 3 2 2 1 1 1]. И надо разбить на 3 контейнера: 5 = 4 = 3 // взяли 3 самых больших: 5,4,3 5 = 4 = 6 // число 3 5 = 6 = 6 // число 2 7 = 6 = 6 // число 2 7 = 7 = 7 // два числа 1, 1 8 = 7 = 7 // последнее число 1 Данный метод считаю наиболее простым, но, к сожалению, есть случаи, когда разброс будет неидеальным.
Комментариев нет:
Отправить комментарий