Минимальное количество элементов в массиве, которое дает то же значение ИЛИ, что и у всего массива

Question

Дан массив из n элементов.Вопрос состоит в том, чтобы найти минимальное количество элементов в массиве, которое приведет к тому же ИЛИ, что и исходный массив.

Например arr[] = {1,2,3,4,6}.ИЛИ всех значений в массиве дает 7 .Если мы рассмотрим только элементы 6,1 и ИЛИ, то получим 7 .Таким образом, ответ будет 2 .

Мой подход состоит в том, чтобы построить двоичное дерево из 0 и 1, где 0 образует левого потомка, а 1 - правого.

Fetchокончательный ответ (т.е. 7) пересекает дерево и находит ближайшее число, которое охватывает почти все биты 7. Вид пораженного после этого первого шага.

Может ли кто-нибудь дать подсказку о том, как приступить к следующим итерациям.

Answer 1

Я думаю, что это можно решить, только попробовав каждую возможную комбинацию и выбрав (одну из) наименьшую комбинацию целых чисел с тем же значением 'или', что и у всех значений 'или вместе.

Это взрывается для больших наборов целых чисел.

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

Answer 2

Это проблема Set Cover , которая является NP-трудной.1 биты в массиве OR-ed - это охватываемый набор и числа в подмножествах карты массива, т.е. каждое число представляет собой подмножество единиц, которые установлены в его двоичном представлении.

жадный алгоритмпроизводит лог (N) коэффициент приближения.Пруф: https://www.cs.cmu.edu/~avrim/451f12/lectures/lect1106.pdf

Answer 3

Некоторые идеи, которые помогут в оптимизации.

1. Любое число, которое «полностью замаскировано» / затмено другим, с операцией ИЛИ, например, |b == b верно, тогда a бесполезно для решения.

2. Количество установленных двоичных битов имеет значение, чем больше битов установлено, тем больше вероятность того, что оно станет частью окончательного решения.

3. числа с битами, общими со многими другими, вряд ли найдутся в решении.

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

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

Повторяя это множество раз, вы должны получить ответ.

Как это оптимизировать дальше, я не знаю.