Учитывая N целых интервалов [lo_i, hi_i].
От каждого интервала выбирается число, такое, что побитовое ИЛИ из них становится заданным числом X. (Не имеет значения, имеет ли результат больше 1 бит, чем X, т.е. если сгенерированное число равно Y, (X & Y) = = X)
Я предполагаю, что эта проблема является NP полной, хотя я не нашел NP трудную задачу, легко сводящуюся к этому.
Но для тех наборов, которые содержат 2 ^ (mostSignificantDigit) - 1, я бы сделал эвристику: во-первых, попробуйте число 1...1 (mostSignificantDigit-1), во-вторых, число с самым значительным битом и столько же другие биты как возможно установлены. Эта эвристика является лишь плохим в том случае, если бы вам потребовалось число из набора с самым значительным битом и несколькими различными менее значимыми битами.
С помощью этой эвристики вы также можете выбрать среди тех наборов наибольшее число 1.... 1 как дополнительную эвристику.
Позвольте немного обобщить проблему. Я буду писать побитовые операторы, такие как OR и AND и SR (shift right).
Для натурального числа X интервалы [lo_1, hi_1],..., [lo_N, hi_N], состоящие из натуральных чисел и бит b в {0, 1}, определяют, существуют ли натуральные числа y_1 в [ lo_1, hi_1],..., y_N в [lo_N, hi_N], что, если Y = y_1 OR... OR y_N, он считает, что (X и Y) = X и что существует я такое, что x_i <= hi_i - b.
Базовый регистр для моего рекурсивного алгоритма - это когда lo_1 = hi_1 = lo_2 =... = hi_n = 0. Существует решение тогда и только тогда, когда X = 0 и b = 0.
Индуктивно подготавливаем подзадачу, позволяя X '= X SR 1 и lo_i' = lo_i SR 1 и hi_i '= hi_i SR 1. Пусть Odd (i) истинно тогда и только тогда, когда hi_i AND 1 = 1. Пусть Odd + (i) быть истинным тогда и только тогда, когда Odd (i) и lo_i < hi_i. Если X И 1 = 0:
Если существует я такое, что Odd + (i), то пусть b '= 0. В противном случае пусть b' = b.
Если X И 1 = 1:
Если существуют различные я и j такие, что Odd + (i) и Odd (j), то пусть b '= 0. Если не существует j таких, что Odd (j), то пусть b' = 1. В противном случае, пусть b '= b.
Верните ответ для подзадачи.