Сведение проблемы подмножества сумм только к положительным числам

Question

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

Answer 1

Технически у вас не может быть такой же проблемы с положительными целыми числами, потому что любое подмножество положительных целых чисел (кроме пустого подмножества) будет иметь сумму больше 0.

Вы можете иметь немного другую проблему с положительными целыми числами (и положительной суммой подмножества). Если вы добавите одно положительное число X к каждому элементу в A, таким образом формируя A+, так что в A+ есть только положительные элементы, то вы будете искать подмножество B в A+, для которого сумма его элементов равна X * числу его (B's) элементы. Однако это отличается от исходной проблемы суммы подмножеств тем, что нужно искать динамическую (в зависимости от количества элементов в подмножестве) сумму.

Возможно, вы захотите посмотреть здесь: http://www.or.deis.unibo.it/alberto/mssp_g_f.ps которая в основном является бесплатной версией этого: http://www.sciencedirect.com/science/article/pii/S0020019000000107 как указано здесь: https://mathoverflow.net/questions/92504/multiple-disjoint-subset-sum-problem