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

Asked
Viewd2372

-1

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

Например:

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

Первый алгоритм уменьшения соответствия не находит решения.

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

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

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

1 ответов

2

Упаковка контейнеров завершена.

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

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

First-Fit-Decreasing - хороший начальный детерминированный алгоритм, но вы можете добиться большего, если объедините его в цепочку с помощью метаэвристики , например Simulated Annealing , Tabu Search или Генетические алгоритмы .Есть несколько библиотек с открытым исходным кодом, которые могут сделать это за вас, например Drools Planner (java).