Минимальная длина сообщения Алгоритм

Question

У меня есть пучки объектов различного размера (много объектов может иметь одинаковый размер, пример: У меня есть 54 объекта 6B, 76, 10B 79 24B и т.д.

Размер объектов 6, 8, 10 .... байтов). Мне нужно упаковать этот пакет в пару сообщений (каждое сообщение имеет максимальную длину 256 байт).

Проблема в том, как получить решение с минимальным количеством сообщений?

Есть ли какой-нибудь известный алгоритм для этого? Нужно ли мне для этого использовать нейронную сеть Хопфилда?

Answer 1

Это пример bin packing problem, который представляет собой комбинаторную задачу NP-hard. Самый простой алгоритм - «First Fit Decreasing (FFD)», в котором вы сначала сортируете свои объекты, уменьшая размер, а затем вставляете каждый объект в первое сообщение в списке с достаточным оставшимся пространством.

Answer 2

Это своего рода проблема с рюкзаком, но не проблема с рюкзаком. Это Bin packing problem, в котором предметы разных объемов упаковываются в минимальное количество ящиков, которые имеют одинаковый размер. Он NP-жесткий.

Answer 3

Первый алгоритм с уменьшением (FFD) не является оптимальным (но очень хорошим началом). Если у вас есть более выполнение времени и более время разработки, приковать его simulated annealing, поиска Табу или генетических алгоритмов. Игнорировать грубая сила или филиал и связанный: они не масштабируются за пределами проблемы с игрушкой.