Не так много задач на перебор разобрано на этом канале, давайте исправлять ситуацию. Простая задача на перебор подмножеств:
Есть много способов перебрать все подмножества, сейчас я расскажу самый простой с точки зрения реализации, но нам понадобится немного математики.
Давайте посмотрим, как можно хранить множества. Так как каждый камень может находиться в одной из двух кучек, можно поставить им в соответствие 0 или 1. И тогда вариант разбиения на две кучки можно записать с помощью n цифр. Например оптимальное разбиение для примера из задачи может быть записано 01101 (первый и четвёртый предметы в первой кучке, все остальные во второй). Такое представление называется битовой маской.
Чтобы найти оптимальное разбиение необходимо перебрать все варианты (на самом деле не совсем так, но мы же пишем простое решение), то есть битовые маски от 000...00 до 111...11.
Битовые маски можно хранить в массиве, а можно вспомнить, что любое число в компьютере хранится в двоичной системе счисления, а это и есть своего рода битовая маска. Тогда для перебора всех битовых масок надо пройтись циклом от 0 (маска 000...00) до 2 в степени n не включая (маска 111...11).
Начнём писать решение на Python:
Здесь 2 в степени n вычисляется с помощью битовой операции "сдвиг влево": 1 << n. Действительно, степени двойки имеют ровно одну единицу в своём двоичном представлении, и она стоит ровно на n-ой позиции, если считать справа.
В результат изначально положил большое число. Можно было бы написать чуть аккуратнее - положить сумму весов всех камней (что соответствовало бы маске 000...00).
Теперь для каждой маски надо посчитать суммы весов в каждой из двух кучках:
Здесь я снова воспользовался битовыми операциями. Выражение с ними находит значение i-го бита в маске: сначала мы сдвигаем маску вправо (тем самым ставим искомый бит на последнюю позицию), а затем делаем "И" с единицей (это зануляет все биты, кроме, возможно, последнего). В результате получается 0 или 1. Пройдясь по всем битам маски, накопим веса кучек.
Осталось проверить текущее разбиение с оптимальным из уже проверенным и, возможно, улучшить ответ:
Давайте посчитаем количество операций: внешний цикл делает 2**18 итераций и внутри ещё цикл на 18. Получается 4718592. Для Python'а это на грани (а точнее, даже немного за гранью) того, сколько можно выполнить за одну секунду. К счастью, есть вариант сдать на PyPy.
Ускорить в два раза можно, заметив, что каждой маске есть парная, и мы все их перебираем. Этого легко избежать, если внешний цикл сделать до 2 в степени n - 1.
Ещё большего ускорения можно добиться, если использовать код Грея, но об этом как-нибудь в другой раз.
Предыдущий выпуск: Задача 532. Трамвай
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
