Алгоритм справедливого распределения чисел на два набора

Question

Учитывая набор из n чисел (1 <= n <= 100), где каждое число является целым числом от 1 до 450, нам нужно распределить этот набор чисел на два набора A и B, чтобы в следующих двух случаях верно: </p>

1. Общее количество в каждом наборе отличается максимум на 1.
2. Сумма всех чисел в A максимально равна сумме всех чисел в B, т.е. распределение должно быть справедливым.

Может кто-нибудь предложить эффективный алгоритм для решения вышеуказанной проблемы?

Спасибо.

Answer 1

Я бы попробовал генетические алгоритмы, так как это очень хорошая проблема - применять их.

Кодификация - это просто двоичная строка длины N, что означает 0 в первой группе и 1 во второй группе. Дайте отрицательную пригодность, когда количество элементов в каждой группе отличается, и положительную пригодность, когда суммы похожи ... Что-то вроде:

fitness(gen) = (sum(gen)-n/2))^2 + (sum(values[i]*(-1)**gen[i] for i in 0..n))^2

(И минимизировать пригодность)

Конечно, это может дать вам неоптимальный ответ, но для больших реальных проблем этого обычно достаточно.

Answer 2

Подойдет любой алгоритм двойного ранца (независимо от распределения чисел).

Answer 3

Я предполагаю, что числа не являются последовательными, и вы не можете повторно сбалансировать?

Из-за ограничения 1 вам нужно будет всегда переключать сегменты при каждой вставке. Таким образом, каждый раз, когда вам не нужно выбирать корзину, выбирайте логическую корзину (где добавление числа сделает сумму ближе к другой группе). Если этот ковш не совпадает с вашим предыдущим, вы получаете еще один ход, где вас не заставляют.