Здравствуйте, maxkar, Вы писали:

M>Ну... В таком виде он не нужен. Совсем и полностью. SubsetSumSolver, строки 48-56. Вопрос: раз уж вы динамику применяете, почему бы на ней все и не сделать? Ответ она тоже умеет строить, это несложно. Если усложнить, ей же можно и все ответы построить.

Я не сообразил, как динамикой вытащить результат, думал в сторону сокращения перебора с помощью статистики. Идея в том, чтобы "отгадать" число элементов подмножества и перебирать средние, многопоточность в данном случае компенсирует погрешность определения мощности подмножества. Динамика осталась для проверки существования решения, для больших чисел её надо убрать.

M>Кроме того, замечены:
M> * Совершенно ненужные наследования (BitVector, Combination, CombinationSequence, SubsetSizesSequence). Первый вообще не нужен, можно в BitMatrix нужные методы сделать. Длину можно там же хранить. Второй заменяется на обычный construction method. Остальные 2 зачем-то от AbstractCollection наследуются. Хотя достаточно было бы Iterable реализовать.

BitVector, BitMatrix, CombinationSequence реиспользовал, в этой задаче с рефакторингом не заморачивался.

M> * Нарушения контрактов при наследовании (CombinationsSequence.iterator.next() — точно). Там же и еще в SubsetSizesSequence несогласован интерфейс size и размер iterable...
M> * Неоптимальный toString в BitVector

Спасибо за толковые замечания

M>А какого порядка там суммы были и с какой точностью? Если это порядка 10-ка тысяч рублей (и считать в копейках), та же динамика будет работать быстро (секунды). До сотен тысяч — пару минут. С учетом практичности данной задачи ее как раз стоит решать обычным динамическим программированием. Если не торопясь, за час вместе с прогоном и отладкой можно управиться. Ваш код писался явно гораздо дольше, его сложнее отлаживать (многопоточность) и при этом в качестве базы ту же динамику использует. Не окупаются затраты. Окупятся, только если subset sum problem решать десятками, сотнями и тысячами в один день. Может быть, при этом имело бы смысл параллелить динамику (она параллелится, но достаточно хитро и сложно), а не перебор.

Суммы были 100 — 1000 рублей, динамика с извлечением результирующего подмножества была бы в тему, только как?
Ещё можно параллелить перебор сочетаний, если погрешность мощности подмножества достаточно мала. Вычислительная сложность максимальная, когда мощность подмножества составляет половину от мощности исходного набора. В этом случае можно попытаться суммировать элементы в группы и применять алгоритм к группам.

M>P.S. CombinationsSequence.lg2(_sum) > 31 никогда не будет true, так как _sum — int.

Согласен. В первом варианте числа были в long, сопли остались
Спасибо за анализ!