Найдите версию массива, сумма элементов которой ближе всего к нулю, когда вы можете изменить знак каждого элемента

Question

В основном заголовок, но я попытаюсь объяснить.

Представьте, что у нас есть массив, подобный [2, 3, -4, 6, -2, -1]

Цель состоит в том, чтобы найти версию этого массива, когда сумма элементов ближе всего к нулю. Действие, которое вам разрешено делать, это изменить знак любого элемента. Так, например, сумма предоставленного массива равна 4, но мы могли бы изменить знак первого элемента, чтобы массив выглядел как [-2, 3, -4, 6, -2, -1], так что теперь сумма равна 0

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

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

Answer 1

Вы не можете найти другой способ, кроме грубого принуждения, так как это проблема NP-Complete. Это эквивалентно проблеме разбиения , где вам нужно разбить массив на два набора с равной суммой. Пока кто-то не докажет или не оспорит проблему P=NP, это означает, что сложность времени будет выше, чем 2^n (где n - количество элементов в вашем наборе).

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

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

Удачи.