Какой алгоритм я должен использовать, чтобы найти ближайшее решение для данного общего использования в списке целых чисел?

Question

Моя проблема в том, что это:

Допустим, у меня есть произвольный список целых чисел A [2013, 54, 3, 32 1, 23 ...]

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

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

Answer 1

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

Например, если ваш набор работает $ \ {2,3,5,8,13,21, 34 \} $ а вы целью $ 32 $ , начните с $ 21 $ (самое большое значение, меньше, чем $ 32 $ ), затем добавьте 8 $ $ (потому что это большое значение, меньше, чем $ 32-21= 11 $ < / span>), а затем добавьте $ 3 $ .

Жадный алгоритм быстрый и простой, но не всегда даст вам лучшее решение. Например, если ваш набор - $ \ {1, 5, 23, 26 \} $ а вы цели $ 30 $ Тогда жадный алгоритм дает 26 $ + 1= 27 $ , тогда как лучшее решение составляет 23 $ + 5 + 1= 29 $ .

Answer 2

Проблема - это NP-Complete, но полиномиальный в значении данного числа, с довольно низкой полиномиальной степенью. Только трудно, если число номеров большие.

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

Теперь, если у вас есть предметы с суммой Close to s, вы можете попытаться улучшить это. Например, если ваша сумма слишком мала на 117, но самый маленький неиспользуемый товар 317, вы попробуете, если у вас есть элемент X в вашем списке, и элемент y не в списке, где y около 200 меньше, чем x - Смейте x против y, добавьте элемент размера 317. Даже простой алгоритм, скорее всего, найдет вам хорошие улучшения.

совершенно другой метод: пусть требуемая сумма будет S, очень большой S (как и многие триллионы). Тогда вы можете выбрать S 'SAY около 1000 000, умножьте все номера, связанные с (S' / S), найдите элементы с суммой, близкой к 1 000 000, а затем выберите оригинальные элементы. Попробуйте на несколько сумм, которые находятся вблизи 1 000 000.

Answer 3

Благодаря комментариям @yuval я привел к проблеме knaxackack, которая именно то, что я искал.

Хотя я не понимал большую часть решения, предложенных этой NP-полной проблемой в Википедии, я думал о быстром, но совершенно ненадежном подходе:

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

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