Хитрая проблема программирования, что я испытываю затруднения при получении моей головы вокруг

Подойдет ли сумма подмножества ? ;]

Это классическая задача Рюкзак , которую вы могли бы увидеть в курсе алгоритмов на уровне колледжа (по крайней мере, я тогда это видел). Лучше всего решить это на бумаге, а решение в коде должно быть относительно легко найти.

РЕДАКТИРОВАТЬ: Следует учитывать динамическое программирование .

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

Я бы отсортировал массив и дал входную сумму m , найдет первое число в массиве меньше m , назовет его n (это ваше первое возможное число для суммы) и начнет с максимально возможного дополнения ( mn ), продвигаясь вниз.

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

Если вы не нашли точное совпадение, начните со следующего числа n (индекс исходного n в индексе-1) и сделайте то же самое. Вы можете продолжать делать это, пока не найдете точное совпадение для двух чисел. Если для суммы не найдено совпадений для двух чисел, запустите процесс снова, но расширьте его, включив в него 3-е число. И так далее.

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

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

Править : Как правильно указывает Венр, мой первый подход был неправильным. Отредактированный подход, чтобы отразить это.

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

Let Used = list of numbers that you sum.
Let Unused = list of numbers that you DON'T sum.
Let tmpsum = 0.
Let S = desired sum you want to reach.

for ( each number x you read )
  toss a coin:
    if it's heads and tmpsum < S
      add x to Used
    else
      add x to Unused

while ( tmpsum != S )
  if tmpsum < S 
    MOVE one random number from Unused to Used
  else
    MOVE one random number from Used to Unused

print the Used list, containing the numbers you need to add to get S

Это будет намного быстрее, чем решение динамического программирования, особенно для случайных входов. Единственная проблема заключается в том, что вы не можете надежно определить, когда есть не является решением (вы можете позволить алгоритму работать в течение нескольких секунд, а если он не завершится, предположите, что решения нет) и что вы не можете быть уверен, что вы получите решение с минимальным количеством выбранных элементов. Опять же, вы можете добавить некоторую логику, чтобы алгоритм продолжал работать и пытался найти решение с меньшим количеством элементов, пока не будут выполнены определенные условия остановки, но это замедлит его работу. Однако, если вас интересует только работающее решение, и у вас МНОГО чисел, а желаемая сумма может быть ОЧЕНЬ большой, это, вероятно, лучше, чем алгоритм DP.

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

Я не знаю точно, как называется эта задача, но похоже, что это своего рода http://en.wikipedia.org/wiki/Knapsack_problem .

Повторение ответа других: это проблема суммы подмножества . Это может быть эффективно решено с помощью техники динамического программирования.

Следующее еще не было упомянуто: проблема является псевдо-P (или NP-полной в слабом смысле).

Существование алгоритма (основанного на динамическом программировании) полинома от S (где S - сумма) и n (количество элементов) доказывает это утверждение.

С уважением.

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

Хех, я разыграю карту "неполной спецификации" (никто не говорил, что числа не могут появляться более одного раза!) и сведу это к проблеме "внесения изменений". Отсортируйте числа в порядке убывания, найдите первое, которое меньше желаемой суммы, затем вычтите его из суммы (деление и остатки могут ускорить этот процесс). Повторяйте до тех пор, пока сумма не станет равна 0 или пока не будет найдено число, меньшее суммы.

Для полноты, вам нужно будет отслеживать количество слагаемых в каждой сумме, и, конечно, генерировать дополнительные последовательности, отслеживая первое используемое число, пропуская его, и повторяя процесс с дополнительными числами. Это решит проблему (7 + 2 + 1) над (6 + 4).