Minimum message length algorithm

Question

I have bundles of objects different size ( lot of objects can have same size, example: I have 54 object of 6B, 76 of 10B, 79 of 24B etc.

The size of the objects are 6, 8 ,10 .... bytes ). I need to pack that bundle in couple messages ( each message has maximum length 256 bytes).

Problem is how to get the solution with the minimum number of messages?

Is there any known algorithm for this? Do I need Hopfield neural network for this?

Answer 1

This is an example of the bin packing problem which is a combinatorial NP-hard problem. The simplest algorithm is "First Fit Decreasing (FFD)" in which you would first sort your objects by decreasing size, and then insert each object into the first message in the list with sufficient remaining space.

Answer 2

This is a kind of knapsack problem, but not the knapsack problem. It's the Bin packing problem, in which items of different volumes are packing into the minimum number of bins, which are all the same size. It is NP-hard.

Answer 3

The First Fit Decreasing (FFD) algorithm isn't optimal (but a very good start). If you have more execution time and more development time, chain it with simulated annealing, tabu search or genetic algorithms. Ignore brute force or branch and bound: they don't scale beyond a toy problem.