We have a set of messages (80 pieces) from 3 to 70 characters long. There are certain containers that can contain an arbitrary number of messages, but their total maximum length is limited to 100 characters. Please help me find the optimal (in terms of speed as well) algorithm, in which all messages can be placed in the minimum number of containers.
Answer 1, authority 100%
Answer 2, authority 50%
Pure Bin Packing Problem. It differs from the knapsack problem in words quite a bit, but in terms of solution – very much.
This problem is NP-hard – that is, a polynomial solution has not been found. Dynamic programming does not solve this problem either – so you should look for a solution either by brute force – or you can spit on the optimality of the solution and look for suboptimal heuristics.
Now about these very heuristic algorithms. Rewriting from Wikipediaso you don’t have to search.
Messages are sorted in descending order of size. Then each message is sequentially tried to be stuffed into the existing containers, if it doesn’t work out, they create a new container and put it in it.
The First Fit Decreasing (FFD) algorithm puts the next message in the first container it finds, while the Best Fit Decreasing (BFD) algorithm puts the message in the container with the least free space left after that.
In principle, this algorithm will not be particularly complicated. The largest number is taken from everything, subtracted from the maximum in order to understand how much is left for us, the maximum number is searched for, which is less than or equal to the remainder, and placed in the container. Again, we look at how much is left and again we search to “score to the ceiling.” And so with every number. It’s tedious, but it should work. Now I’m doing a PHP script to check).