Упаковка предметов в фиксированное количество бункеров

Question

Я ищу алгоритм, который решит мою проблему наиболее эффективным способом.

Описание проблемы:

У меня есть список элементов (допускаются только положительные целые числа) и фиксированное количество бинов одинаковой емкости. До сих пор я думал о алгоритме ветвления и ограничения, но я не совсем уверен, является ли он лучшим подходом в этом случае.

Пример:

Приведен список предметов:

(3, 4, 4, 2, 3, 9, 2)

и три бункера вместимостью 9 каждый Мне нужно упаковать их так: (порядок вещей не имеет значения)

[3, 4, 2], [4, 3, 2], [9]

Я думаю, что это вариант проблемы упаковки бинов (которая, как я знаю, является NP-полной), но, поскольку я не пытаюсь минимизировать количество используемых бинов, мне интересно, есть ли лучшее решение.

Answer 1

Это проблема мультибинарной упаковки:

Учитывая набор предметов, каждый определенного размера, и набор корзин, каждый также определенного размера - есть ли распределение предметов по корзинам так, чтобы ни один предмет не оставался без упаковки и емкость не превышалась?

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

см. тезис Вольфганга Стилла и Геппингена

Answer 2

Это эквивалентно проблеме упаковки бункеров, учитывая количество бункеров, максимизируя количество элементов, упакованных в бункеры.

Если оптимальное решение больше или равно количеству элементов в вашем списке, решение также является решением вашей проблемы.Если оптимальное решение меньше, чем количество элементов в вашем списке, решение вашей проблемы не существует.

Поскольку проблема упаковки в бункере NP-Hard, решение вашей проблемы за полиномиальное время также не существует.Вы можете использовать эвристику, разработанную для задачи упаковки бункера, такую ​​как наилучшая подгонка, первая подгонка и так далее.Но они не гарантируют, что будет найдено оптимальное решение.