Сплит Алгоритм на C++

Question

У меня есть массив с 8 элементами:

a[8] = {9, 7, 6, 2, 3, 1, 5, 4}

Я хочу разделить 8 элементов на 3 группы. Каждая группа представляет собой сумму 1 или более элемента. Сумма каждой группы наиболее похожа.

Answer 1

Вы описываете проблему k-разбиения с k=3.

К сожалению, эта проблема, как известно, является (сильной) NP-Hard, поэтому не существует известного эффективного решения (и, как правило, она не существует).

Ваша лучшая надежда - поиск методом "грубой силы": создайте все разделы на 3 группы и выберите лучший из них. Если вы имеете дело с 8 элементами - это должно быть возможно, но я боюсь, что это быстро станет слишком медленным для больших массивов.