Балансировка наборов значений

Question

Итак, я работаю над небольшой забавной программой и столкнулся с этой довольно интересной проблемой: У меня есть несколько наборов значений предопределенных размеров набора. Все это уникальное подмножество большого пула значений. Средние значения каждого подмножества чисел должны быть как можно ближе друг к другу, насколько это возможно. Это не обязательно должно быть идеально, но должно быть достаточно близко, чтобы все наборы были «сбалансированы» друг против друга.

ex: {1,2,3,6,9,10,15,23,27} глобальное среднее: 10,66 нужно отсортировать в 2 набора по 2 и один набор по 5

приемлемый результат: {1,27} {2,23} {3,6,9,10}

На практике значения варьируются от 60 до 200, а наборы - от 6 до 20.

Я пробовал пару разных алгоритмов с разной степенью успеха, но мне было интересно посмотреть, что думают хорошие люди из StackOverflow.

Мой лучший, Zach

Answer 1

Это напоминает мне RubyQuiz # 65, "Разделение добычи" .Основное отличие состоит в том, что эта проблема искала сплиты, которые были бы точно равными, а не почти равными.Возможно, некоторые из этих решений помогут вам.

Answer 2

Звучит интересно. хотел бы знать, каково практическое применение этого.

Просто чтобы быть уверенным, предположим, что вы имели в виду, что непересекающиеся подмножества и сумма подмножеств примерно равны (а не средние)

Кроме того, в примере я не мог понять, как вы решили (наверняка) сделать 2 комплекта по 2 и один из 5.

Я могу придумать жадное субоптимальное решение.

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

Это не всегда даст вам оптимальное решение.

Для 1,2,3,6,9,10,15,23,27 обратное: 27, 23, 15, 10, 09, 06, 03, 02, 01

27 3 2 1 = 33

23 09 = 30

15 10 06 = 31