Мне нужна альтернатива алгоритму упаковки первого подходящего уменьшающегося контейнера, который всегда находит оптимальное решение

Question

Я реализовал алгоритм упаковки бинов «Первая подгонка-уменьшение», чтобы разбить список чисел на две «корзины» одинакового размера. Алгоритм почти всегда находит оптимальное расположение упаковки, но иногда это не так.

Например:

Набор чисел 4, 3, 2, 4, 3, 2, очевидно, можно разбить на следующую схему: 1) 4, 3, 2 2) 4, 3, 2

Алгоритм уменьшения первой аппроксимации не находит решения.

При таких обстоятельствах недопустимо НЕ находить правильное решение, если оно существует.

Оригинальная головоломка состоит в том, чтобы разбить последовательность чисел на два набора с одинаковой суммой.

Это простая проблема с упаковкой бункеров или я использовал неправильный алгоритм?

Answer 1

Упаковка бункера завершена.

При таких обстоятельствах недопустимо НЕ находить правильное решение, если оно существует.

Попробуйте алгоритм Branch and Bound , но, как и все точные алгоритмы, он не масштабируется до средних или больших проблем.

Первое приближение-уменьшение - это хороший начальный детерминистический алгоритм, но вы можете добиться гораздо большего успеха, связав его с помощью метаэвристики , такой как Имитация отжига, Поиск по Табу или Генетические алгоритмы . Есть пара библиотек с открытым исходным кодом, которые могут сделать это для вас, например, Drools Planner (java).