Нужен алгоритм для этой проблемы

Question

Существует две целочисленные последовательности A [] и B [] длины N, обе не отсортированы.

Требование: путем обмена элементами между A [] и B [] (можно произвольно обмениваться, не с тем же индексом), сделать разницу между {суммой всех элементов в A []} и {суммой всех элементы в B []} должны быть минимальными.

PS: на самом деле, это вопрос интервью, с которым я столкнулся.

Большое спасибо

Answer 1

Это будет NP-хард! Я считаю, что вы можете сделать сокращение от Подмножество до этого.

Согласно комментариям BlueRaja / polygene, я постараюсь обеспечить полное сокращение от суммы подмножества.

Вот сокращение:

Проблема суммы подмножеств: Даны целые числа x ₁ , x ₂ , ..., x _n , существует ли какое-то непустое подмножество, которое суммирует ноль?

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

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

Скажем, теперь вам даны целые числа T = {x ₁ , x ₂ , ..., x _n } (multiset)

Пусть S _i = x ₁ + x ₂ + ... + x _n + x _i .

Пусть T _i = {x ₁ , x ₂ , ..., x _i-1 , x _{i + 1} , ..., x _n } (= T - x _i )

Определение

A _i = Массив, сформированный с использованием T _i

B _i = [S _i , 0, ..., 0] (т. Е. Один элемент - S _i , а остальные - нули).

Пусть m _i = минимальная разница, найденная нашей задачей для массивов A _i и B _i

(мы запускаем нашу задачу n раз).

Утверждение: Некоторое непустое подмножество T суммирует ноль тогда и только тогда, когда существует некоторый i, для которого m _i = 0.

Доказательство: (Wlog) говорят х ₁ + х ₂ + .. + х _к = 0

Тогда

A = [x _{k + 1} , ..., x _n , 0, ... 0]

B = [x ₂ , x ₃ , ..., x _k , S ₁ , 0, .. 0]

дает минимальную разницу m ₁ , которая равна | x ₂ + .. + x _k + (x ₁ +. .. + x _n ) + x ₁ - (x _{k + 1} + .. + x _n ) | = | 2 (x ₁ + x ₂ + .. x _k ) | = 0.

Аналогично доказывается часть if.

Фактически, это также следует (более легко) из раздела тоже: просто создайте новый массив со всеми нулями.

К счастью, я не допустил ошибок.

Answer 2

Возьмите любой пример проблемы с разделом NP-complete :

Разделить мультимножество A натуральных чисел на два мультимножества B и C с одинаковой суммой

как {a ₁ , a ₂ , ..., a _n }. Добавьте n нулей {0,0,0 ..., 0, a ₁ , ..., a _n } и спросите, можно ли разбить множество на два мультимножества A и B с одинаковой суммой и одинаковым количеством элементов. Я утверждаю, что эти два условия эквивалентны:

• Если A и B являются решением проблемы, то вы можете вычеркнуть нули и получить решение проблемы с разбиением.
• Если есть решение проблемы с разделами, например: _i1 + a _i2 + ... a _ik = a _j1 + ... + a _jl , где {a _i1 , a _i2 , a _ik , a _j1 , ..., a _jl } = {a ₁ , ..., a _n } тогда очевидно k + l = n. Добавьте л нули к левой стороне и k нолей к правой стороне, и вы получите 0 + ... + 0 + a _i1 + a _i2 + ... a _ik = 0 + ... + 0 + a _j1 + ... + a _jl , что является решением вашей проблемы.

Итак, это сокращение (так что проблема NP-сложная), а проблема NP, то есть NP-полная.

Answer 3

"последовательности A [] и B [] длины N" -> означает ли это, что A и B равны каждая длины N?

(Для ясности я использую массивы на основе 1 ниже).

Если так, как насчет этого:

1. Предположим, что A [1..N] и B [1..N]
2. Объединить A и B в новый массив C длиной 2N: C [1..N] <- A [1..N]; C [N + 1 .. 2N] <- B [1..N] </li>
3. Сортировка С. В порядке возрастания.
4. Возьмите первую пару чисел из C; отправьте первый элемент (C [1]) на A [1] и второй элемент (C [2]) на B [1]
5. Возьмите вторую пару чисел из C; на этот раз отправьте элемент second (C [4]) на A [2] и элемент first (C [3]) на B [2] (порядок элементов в пара, отправленная в A и B, противоположна 3)
6. ... повторять 3 и 4 до тех пор, пока C не исчерпается

Наблюдение здесь заключается в том, что в отсортированном массиве соседняя пара чисел будет иметь наименьшее различие (по сравнению с парой чисел из несмежных позиций). Шаг 3 гарантирует, что A [1] и B [1] состоят из пары чисел с наименьшей возможной разницей. Шаг 4 гарантирует, что (a) A [2] и B [2] состоят из пары чисел с наименьшей возможной разницей (из доступных чисел), а также (b) что разность противоположна знаку от шага 3. продолжая в том же духе, мы обеспечиваем, чтобы A [i] и B [i] содержали числа с наименьшей возможной разницей. Кроме того, переключая порядок, в котором мы отправляем элементы в A и B, мы гарантируем, что разность меняет знак для каждого последующего i.

Answer 4

Попытайтесь быть жадным об этом. Учитывая такую ​​ограниченную информацию, я не уверен, что еще можно было бы выложить там.

Answer 5

Проблема в NP-Complete.

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

Входные данные для проблемы разбиения: набор S целых чисел, размер N

Для того, чтобы преобразовать этот ввод во входные данные для нашей задачи, мы определяем A как массив всех элементов в S, а B как массив одинакового размера, с B [i] = 0 для всех i. Это преобразование является линейным во входном размере.

Понятно, что наш алгоритм, примененный к A и B, возвращает true тогда и только тогда, когда существует разбиение S на 2 подмножества, так что суммы равны.

Answer 6

Я не уверен, что это обеспечит минимально возможное расстояние, но первое, что приходит мне в голову, это что-то вроде этого:

int diff=0;
    for (int i = 0; i<len; i++){
        int x = a[i] - b[i];
        if (abs(diff - x) > abs(diff + x)){
             swap(a,b,i);
             diff-=x;
        }else{
             diff+=x;
        }

    }

при условии, что у вас есть функция подкачки, которая берет два массива и обменивает элементы в позиции i :)

вычисляя и складывая разницу между двумя значениями в позиции i, вы получаете инкрементную разницу между суммами элементов двух массивов.
на каждом шаге вы проверяете, лучше ли добавить (a [i] -b [i]) или (b [i] -a [i]). если b [i] -a [i] это так, вы меняете элементы в позиции i в массивах.

Может быть, это будет не самый лучший способ, но это должно быть началом:)