Создайте сумму 1000, 2000 и т. Д. Из набора чисел

Question

Хорошо, вот в чем проблема:

Мне нужно найти любое количество целочисленных групп из 50-100 наборов элементов, которые в сумме составляют 1000, 2000, ..., 10000.

Ввод: список целых чисел

Целое число может быть только в одном списке.

Есть идеи по алгоритму?

Answer 1

Поиск в Google по «проблеме ранца» должен принести вам немало хитов (хотя они вряд ли будут очень обнадеживающими - это довольно хорошо известная проблема, полная NP-проблем).

Редактировать: если вы хотите получить техническую информацию, то, что вы описываете, похоже, является проблемой с подмножеством сумм - что является частным случаем проблемы с ранцем. Конечно, это при условии, что я правильно понимаю ваше описание, которое, как я признаю, может вызвать некоторые вопросы.

Вы можете найти Алгоритм 3.94 в Справочник по прикладной криптографии полезным.

Answer 2

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

Answer 3

Это проблема с рюкзаком. Есть ли какие-то ограничения на целые числа, из которых вы можете выбирать? Они делятся? Все ли они ниже некоторой заданной стоимости? При наличии таких ограничений могут быть способы решения проблемы за полиномиальное время - Google предоставит вам ответы.