Задача о сумме подмножеств в общей формулировке звучит так:
Существует множество S чисел, вопрос состоит в том, будет ли сумма некоторого подмножества от S равна заданному числу Т.
Известно, что данная задача NP-полная.
Мы будем решать эквивалентную задачу, где все числа являются натуральными.
Частным случаем задачи о сумме подмножеств является задача разбиения множества чисел:
Множество чисел S необходимо разбить на два подмножества S1 и S2, где сумма S1 равна сумме S2.
(От задачи о сумме подмножеств текущая отличается только тем, что T = SUM(S1) / 2 = SUM(S2) / 2)
Хочу предложить вам простой и элегантный способ относительно быстрого решения обеих задач методом целочисленного линейного программирования (ЦЛП). Мы получим не только точный ответ на вопрос, но и найдём искомое подмножество.