Алгоритм - найти минимальное вычитание между суммой двух массивов

Question

Я сейчас на охоте и выполняю множество алгоритмических упражнений.Вот моя проблема:

---

Учитывая два массива: a и b одинаковой длины, предмет должен составить | sum (a) -sum (б) |минимальный, путем замены элементов между a и b .

---

Вот мое мнение:

предположим, что мы поменяем местами a [i] и b [j], установите Delt = sum (a) - sum (b), x = a [i] -b [j]
, затем Delt2 = сумма (a) -a [i] + b [j] - (сумма (b) -b [j] + a [i]) = Delt - 2 * x,
затем изменить = | Delt |- | Delt2 |, который пропорционален | Delt | ^ 2 - | Delt2 | ^ 2 = 4 * x * (Delt-x),

На основании вышеизложенного я получил следующий код:

---

Delt = sum(a) - sum(b);
done = false;
while(!done)
{
    done = true;
    for i = [0, n)
    { 
        for j = [0,n)
        {
            x = a[i]-b[j];
            change = x*(Delt-x);
            if(change >0)
            {
                 swap(a[i], b[j]);
                 Delt = Delt - 2*x;
                 done = false;
            }
        }
    }
}

---

Однако есть ли у кого-нибудь гораздо лучшее решение?Если вы получили, пожалуйста, скажите мне, и я был бы очень благодарен за вас!

Answer 1

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

NP-Hardness доказательство:
Предположим, что существовал алгоритм A, который решает эту проблему в полиномевремя, мы можем решить проблему разбиения за полиномиальное время.

Partition(S):
for i in range(|S|):
   S += {0}
   result <- A(S\2,S\2) //arbitrary split S into 2 parts
   if result is a partition: //simple to check, since partition is NP.
     return true.
return false //no partition

Корректность:
Если существует раздел, обозначим как (S1, S2) [предположим, что в S2 больше элементов], на итерации | S2 | - | S1 |[т.е. при добавлении | S2 | - | S1 |нули].Входные данные для A будут содержать достаточно нулей, поэтому мы можем вернуть два массива одинаковой длины: S2, S1 + {0,0, ..., 0}, которые будут разделением на S, и алгоритм выдаст true,
Если алгоритм возвращает true и итерацию k, у нас было два массива: S2, S1, с одинаковым количеством элементов и одинаковыми значениями.удалив k нулей из массивов, мы получим раздел к исходному S, поэтому у S был раздел.

Полином:
предположим, A занимает P(n)время, алгоритм, который мы создали, займет n*P(n) время, которое также является полиномиальным.

Вывод:
Если эта проблема разрешима за полиномиальное время, то и проблема Partion-Problemи, следовательно, P = NP.Исходя из этого: эта проблема NP-Hard.

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

РЕДАКТИРОВАТЬ : как упомянуто @jpalecek: простосоздавая уменьшение: S->S+(0,0,...,0) [k умножить на 0], можно напрямую доказать NP-твердость путем уменьшения.полином является тривиальным, и корректность очень похожа на доказательство корректности вышеупомянутого разбиения: [если есть раздел, возможно добавление «балансирующих» нулей;другое направление просто обрезает эти нули]

Answer 2

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

Не могу сделать это в моей голове, но я почти уверен, что есть конструктивное решение. Я думаю, что если вы сначала отсортируете их, а затем раздадите их по некоторому правилу Нечто подобное If value > 0 and if sum(a)>sum(b) then insert to a else into b