Это, в основном, вариант проблемы bin-pack . Эта проблема, как известно, является NP-трудной, поэтому не ожидайте найти эффективный оптимальный алгоритм для сложных случаев (т. Е. Со многими объектами и ячейками).
Однако, если ваше количество объектов / корзин относительно невелико, вы, вероятно, будете в порядке, просто исчерпывающе ища все возможные комбинации с помощью поиска в глубину .
Это довольно легко реализовать: просто возьмите первый объект, а затем рекурсивно перезапустите алгоритм с первым объектом, размещенным в каждом из бинов по очереди (т.е. вычитая размер объекта из доступного пространства бина). Наконец, вам просто нужно отследить лучшее из найденных «решений» и вернуть его в качестве окончательного ответа, как только вы попробуете все комбинации.
Вы также можете ускорить выполнение этого алгоритма:
- Считать все объекты одинакового размера эквивалентными
- Сокращение дерева поиска (то есть возврат рано из ветви), если вы не можете превзойти текущее лучшее решение, например. когда вы уже нашли идеальную посадку
Обновлено на основе комментариев к размеру проблемы
Учитывая, что, похоже, у вас есть очень большое количество блоков, вы можете попробовать следующее:
- Подберите самые большие 10-20 кусков, используя исчерпывающий поиск, как указано выше
- Распределите остаток, используя метод наибольшего соответствия