@scoo_by

Как разбить множество на всевозможные два подмножества с равной суммой элементов?

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

Например, множество [1,2,3,4,5,6,7] разбивается на [7, 6, 1] [5, 4, 3, 2] , [7, 5, 2]
[6,4,3,1] , [7, 4, 3] [6,5,2,1] и [7, 4, 2, 1] [6,5,3] (т.е. [7, 6, 1] и [7, 1, 6] одинаковы)

Есть понимание, что сумма всех элементов должна делиться на два. А дальше возникают трудности.
  • Вопрос задан
  • 536 просмотров
Пригласить эксперта
Ответы на вопрос 3
Adamos
@Adamos
Ну, самое тупое - отсортировать множество по возрастанию (1 - 7) и перебирать его перестановки по принципу счетчика.
На каждой итерации проверяем, получается ли сумма первых n элементов равной половине суммы всего множества. Такой набор (со всеми перестановками второй части) будет решением. Если не сложилось - пропускаем все перестановки до изменения n-ого (или (n-1)-ого) элемента, потом продолжаем.

P.S. Собственно, раз вам нужно с точностью до перестановки - вам и счетчик нужно увеличивать с условием, что все элементы от первого до n-ного отсортированы по возрастанию.
Ответ написан
Комментировать
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Полный перебор. Вам надо найти множества, имеющие сумму в половину от суммы всех чисел.

Можно итеративно - перебирайте число от 0 до 2^|количество чисел|. Биты в этом числе будут обозначать, берется ли конкретный элемент множества в сумму. Дальше считайте сумму текущего подмножества пользуясь бытовыми операциями, чтобы проверить стоит ли заданный бит в 0 или 1. Если набрали половину общей суммы - выводите те индексы, где биты 1 как одно множество, а оставшиеся - как второе. Чтобы каждое разбиение не выводить 2 раза, требуйте, чтобы старший бит был 0 (перебирайте до 2^|количество чисел-1|)

Можно рекурсивно. Рекурсивная функция принимает текущий набор чисел и номер следующего числа кандидата. Функция или берет или не берет текущего кандидата и запускается рекурсивно передавая следющий номер как кандидата. Если все числа рассмотрены - проверяйте сумму и выводите разбиение. Можно соптимизировать - если уже набрали сумму больше половины, дальше перебирать смысла нет. Опять же, первое число можно потребовать всегда брать или всегда не брать, чтобы не выводить одно и то же разбиение 2 раза.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы