Если дано n целых чисел, найдите m, у которого абсолютное значение суммы минимально - PullRequest
4 голосов
/ 29 мая 2011

У меня есть n целых чисел;включены как положительные, так и отрицательные значения.Каков хороший алгоритм для поиска m целых чисел из этого списка, чтобы абсолютное значение суммы этих m целых чисел было наименьшим возможным?

Ответы [ 2 ]

5 голосов
/ 29 мая 2011

Задача NP-сложна, поскольку эффективное ее решение позволило бы эффективно решить задачу о решении подмножества сумм .

Учитывая это, вы не найдете эффективного алгоритма длярешайте ее, если не уверены, что P = NP.

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

2 голосов
/ 29 мая 2011

Если «хорошо» означает «правильно», тогда просто попробуйте все возможности.Это займет у вас n choose m времени.Очень медленно.К сожалению, это лучшее, что вы можете сделать в целом, потому что для любого набора целых чисел вы всегда можете добавить еще одно, которое является отрицательным от суммы m-1 других - и все остальные могут иметь одинаковый знак, поэтомуу вас нет возможности искать.

Если «хорошо» означает «быстро и обычно работает нормально», то есть несколько способов продолжить.Например:

Предположим, что вы можете решить задачу для m=2, и предположим, что в дальнейшем вы сможете решить ее как для положительного, так и для отрицательного ответа (а затем возьмите меньшее из двух).Теперь предположим, что вы хотите решить m=4.Решите для m=2, затем выкиньте эти два числа и решите снова ... должно быть очевидно, что делать дальше!А как насчет m=6?

Теперь предположим, что вы можете решить проблему для m=3 и m=2.Думаю, что вы можете получить достойный ответ для m=5?

Наконец, обратите внимание, что если вы сортируете числа, вы можете решить для m=2 за один проход, а для m=3 у вас раздражает квадратичный поискчтобы сделать, но, по крайней мере, вы можете сделать это только около четверти списка дважды (маленькие половины положительных и отрицательных чисел) и искать номер противоположного знака для отмены.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...