#sum #subset #minimum
Вопрос:
Я должен найти минимальную разницу в сумме подмножеств. Я могу решить эту проблему, когда оба подмножества суммируются во всем наборе (это хорошо известная проблема с разделением, использующая DP), но в этом случае подмножества могут быть полностью случайными, например:
Минимальная разница в сумме подмножеств для {3,4,5} будет равна 1, потому что мы можем выбрать {3} и {4}, а их разница равна 1 (в то время как проблема разбиения займет {3,4} и {5} и вернет (3 4)-5 = 2).
Другой пример: {1,2,10,15} — минимальная разница в подмножествах будет равна 1 из-за {1} {2} — проблема с разделением выберет {1,2,10} {15} и вернет 15-13=2.
Я думаю, что это немного похоже на нахождение максимальной суммы подмножеств, сформированной путем разбиения любого подмножества массива на 2 раздела с проблемой равной суммы, которая решается с помощью DP на geeksforgeeks. Кто-нибудь может помочь с изменением этих алгоритмов?