Комбинаторная задача на перестановки

#алгоритм #оптимизация #комбинаторика #динамическое_программирование

Есть 3 числа: A, B и C. Необходимо получить выражение A+B=C, при этом чтоб C было
минимальным. Нужно переставлять биты внутри чисел (переставлять можно только в пределах
одного числа. Т.е можно поменять какие-то 2 бита внутри числа А, но нельзя поменять
два бита из А и B).

Ограничения на числа 2^31-1.

Решения может не существовать, все числа положительные.

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

Подскажите в какую сторону копать.
    

Ответы

Ответ 1

Пишу только алгоритм, автору думаю будет интересно самому реализовать.

1 - Перебираем число С (если делать правильно, то будет не больше 30 млн вариантов,
С[31,15] ). В порядке возрастания. 

Теперь проверим можно ли получить фиксированное С.

Для этого используем динамику. 

Начальное значение F[0][ bit_count(A)] [bit_count(B)][0] = true;

Поля: {бит в С, осталось битов в А, осталось битов в Б, есть перенос бита}.

Значение - можно ли такое получить.

Пересчёт. Если в С бит {i} совпадает с переносом, то переходы либо два нуля или 2
едиинцы {(a-1, b-1), (a,b)} флаг переноса выставить в первом случае. Аналогично если
не совпадают { (a-1,b), (a,b-1) } флаг переноса не меняется.

Если F[32][0][0][0] = true то мы нашли что хотели. Восстановить ответ можно и не
сложно (в крайнем случае ещё раз эту же динамику запустить).

Сложность порядка оценить тяжело, оценка сверху 30кк*32*32 но она очень грубая. В
целом должно успеть (делать отсечение по отрицательному количеству не забывать).