Есть 3 числа: A, B и C. Необходимо получить выражение A+B=C, при этом чтоб C было минимальным. Нужно переставлять биты внутри чисел (переставлять можно только в пределах одного числа. Т.е можно поменять какие-то 2 бита внутри числа А, но нельзя поменять два бита из А и B).
Ограничения на числа 2^31-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 но она очень грубая. В целом должно успеть (делать отсечение по отрицательному количеству не забывать).
Комментариев нет:
Отправить комментарий