Разбить массив на четыре блока так, чтобы сумма значений XOR блоков была максимальной

Question

Учитывая массив целых чисел, которые необходимо разделить на четыре блока, чтобы сумма XOR блоков была максимальной.

I / P - [1,2,1,2, 1,2]

O / P - 9

Объяснение: Box1 - [1,2] Box2 - [1,2] Box3 - [1,2] Box4- []

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

def max_Xor(b1,b2,b3,b4,A,index,size):
    if index == size:
        return b1+b2+b3+b4  
    m=max(max_Xor(b1^A[index],b2,b3,b4,A,index+1,size),
        max_Xor(b1,b2^A[index],b3,b4,A,index+1,size),
        max_Xor(b1,b2,b3^A[index],b4,A,index+1,size),
        max_Xor(b1,b2,b3,b4^A[index],A,index+1,size))
return m
def main():
    print(max_Xor(0,0,0,0,A,0,len(A)))

Заранее спасибо !!

Answer 1

Есть несколько вещей, чтобы ускорить ваш алгоритм:

1. Построить некоторую логику запуска: не имеет смысла помещать что-либо в блок 3, пока блоки 1 и 2 не будут дифференцированы. На самом деле, вы должны иметь порядок приоритета, чтобы не повторять конфигурации в другом порядке.
2. Запоминание вашей логики;это позволяет избежать повторяющихся вычислений.
3. Для больших случаев воспользуйтесь преимуществом существующей алгебры значений.

Этот последний элемент может оказаться самым большим сбережением. Например, если ваши самые длинные числа включают в себя несколько 5-битных и 4-битных чисел, нет смысла рассматривать более короткие числа, пока вы не поместите их в коробки, получая максимальное преимущество для старших бит. Имея только четыре поля, вы не можете иметь число из 3-разрядных чисел, которое доминирует над одним неуместным 5-разрядным числом.

Ваша цель - разместить нечетное число 5-разрядных чиселв 3 или все 4 коробки;при этом проверяйте только, выполняет ли этот «пессимизацию» бит 4 оставшихся чисел. Например, учитывая шесть 5-значных чисел (диапазон 16-31) и несколько маленьких (0-7), вы должны сначала обрабатывать только комбинации, которые разделяют 5-значные числа на (3, 1, 1,1), так как это оставляет этот ценный 5-битный включенным в каждом наборе.

При более равномерном сочетании значений на вашем входе вам также нужно будет подумать, как распределить 4-битные значения дляаналогичный "держи это странным" эвристический. Обратите внимание, что при работе от самого большого до самого маленького вам нужно беспокоиться только о том, чтобы сохранить его нечетным и следить за следующим битом.

Эти методы должны позволить вам сократить рекурсию настолько, чтобы она закончилась вовремя.

Answer 2

Я бы постепенно переходил от старшего к младшему. Для каждого бита попробуйте все комбинации, которые распределяют все еще неиспользуемые числа, для которых установлен этот бит, так, чтобы их нечетное число было в каждом поле, больше ничего не имеет значения. Выберите лучший путь в целом. Одна проблема, которая усложняет этот жадный метод, состоит в том, что два блока с набором младших битов могут равняться одному блоку с набором следующего старшего бита.

В качестве альтернативы запомните состояние блоков в своей рекурсии как упорядоченный кортеж.

Answer 3

Мы можем использовать динамическое программирование здесь, чтобы разбить задачу на меньшие множества, а затем сохранить их результат в таблице. Затем используйте уже сохраненный результат, чтобы вычислить ответ для большего набора. Например:

Input -- [1,2,1,2,1,2]

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

box = 1, num =  [1,2,1,2,1,2]
ans = 1 3 2 0 1 3

Так как у нас есть только одна коробка, все числа войдут в эту коробку. Мы будем хранить этот ответ в таблице. Давайте назовем матрицу как DP.

DP[1] = [1 3 2 0 1 3] 
DP[i][j] stores answer for distributing 0-j numbers to i boxes.

Теперь давайте возьмем случай, когда у нас есть два поля, и мы будем брать числа один за другим.

num = [1] since we only have one number it will go into the first box.
DP[1][0] = 1

Позволяет добавить еще один номер.

num = [1 2]

теперь есть два способа поместить этот новый номер в коробку.

case 1: 2 will go to the First box. Since we already have answer 
for both numbers in one box. we will just use that.

answer = DP[0][1] + 0 (Second box is empty)

case 2: 2 will go to second box.
answer = DP[0][0] + 2 (only 2 is present in the second box)

Максимум двух случаев будет сохранен вDP [1] [1].

DP[1][1] = max(3+0, 1+2) = 3.

Теперь для num = [1 2 1]. Опять же, для нового номера у нас есть три случая.

box1 = [1 2 1], box2 = [], DP[0][2] + 0
box1 = [1 2], box2 = [1], DP[0][1] + 1
box1 = [1 ], box2 = [2 1], DP[0][0] + 2^1

Максимум этих трех будет ответом для DP [1] [2].

Аналогично мы можем найти ответ num = [12 1 2 1 2] box = 4

1 3 2 0 1 3 
1 3 4 6 5 3 
1 3 4 6 7 9 
1 3 4 6 7 9 

Также обратите внимание, что a xor b xor a = b. вы можете использовать это свойство, чтобы получить xor сегмента массива за постоянное время, как это предлагается в комментариях. Таким образом, вы можете разбить задачу на меньшее подмножество и использовать меньший набор ответов, чтобы вычислить для больших. Надеюсь это поможет. После понимания концепции вы можете пойти дальше и реализовать ее быстрее, чем экспоненциально.