Как выбрать элементы из двух массивов, чтобы сумма была минимальной?

Question

У меня есть два массива одинаковой длины, и я могу выбрать либо массив1, либо массив2, и вывод суммы должен быть наименьшим. Однако число раз, когда я выбирал элемент из массива 1, должно быть таким же, как я выбирал из массива 2.

Пример:

array1 = [2, 3, 5, 1]

array2 = [1, 2, 3, 2]

Вывод будет 8, потому что:

At index0: I picked 2 from array1.
At index1: I picked 2 from array2.
At index2: I picked 3 from array2.
At index3: I picked 1 from array1.

Мой текущий подход: я сортирую пару массивов на основе элемента в массиве1. Поэтому я выбрал array1 в index0 и index1, затем array2 в index2 и index3.

Пример после сортировки:

array1 = [1, 2, 3, 5]

array2 = [2, 1, 2, 3]

At index0: I picked 1 from array1.
At index1: I picked 2 from array1.
At index2: I picked 2 from array2.
At index3: I picked 3 from array2.

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

array1 = [2, 3, 5, 1]

array2 = [1, 7, 6, 2]

После сортировки на основе массива1:

array1 = [1, 2, 3, 5]

array2 = [2, 1, 7, 6]

At index0: I picked 1 from array1.
At index1: I picked 2 from array1.
At index2: I picked 7 from array2.
At index3: I picked 6 from array2.

Когда идеальным решением является:

At index0: I picked 2 from array2.
At index1: I picked 1 from array2.
At index2: I picked 3 from array1.
At index3: I picked 5 from array1.

Может кто-нибудь помочь мне с этим? Спасибо.

Answer 1

Вычислить разницу массив1 - массив2:

array1 = [2, 3, 5, 1]
array2 = [1, 2, 3, 2]

diff   = [1, 1 ,2, -1]
index  = [0, 1, 2, 3]

Сортировать его (и запомнить индексы):

sorted_diff: [-1, 1, 1, 2]
index2     : [ 3, 0, 1, 2]
            array1 | array2

Вы должны отрицать половину массива, чтобы получить минимальную сумму., Поэтому index1 , index2 из массива 2.

Пример 2:

array1 = [2, 3, 5, 1]
array2 = [1, 7, 6, 2]

diff   = [1, -4 ,-1, -1]
index  = [0, 1, 2, 3]

sorted = [-4, -1, -1, 1]
index2 = [ 1, 2, 3, 0]
        array1 | array2

Так что возьмите из массива index3, index0.