Это оптимизационная версия проблемы разбиения , которая является NP-полной, хотя, согласно этой статье, «существуют эвристики, которые решают проблему во многих случаях, оптимально или приблизительно».

Раздел « Методы » этой статьи содержит несколько способов приблизительного или псевдополиномиального решения. В частности, если вы можете жить с приблизительным ответом, вы можете попробовать жадный подход:

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

Время выполнения этого подхода составляет O(n^2)и гарантирует, что вы получите результат в пределах 4/3 от точного решения.

Если у вас должно быть точное решение, а ваш набор данных достаточно мал, вы всегда можете использовать метод грубой силы, генерирующий каждую возможность (это экспоненциально O(2^n)). В зависимости от ваших требований к производительности, этого может быть достаточно.