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

Question

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

Алгоритм First Fit Decreasing (FFD) не оптимален (но очень хороший старт). Если у вас есть больше времени выполнения и больше времени разработки , объедините его в цепочку с имитированным отжигом , tabu search или генетические алгоритмы . Игнорировать грубая сила или ветвь и предел : они не выходят за рамки игрушечной проблемы.