Best Way To Loop Through And Combine Products

I'm looking for your personal thoughts on the best way to do this as there a number of ways that I can see to get to the same end. I have a store front that has multiple different

Solution 1:

There is no getting away from this being a classic example of the bin-packing problem and while I am no mathematician either, a lot of people who are have given this considerable thought. So:

There is no known optimal solution to this problem that can be computed in polynomial time and it would appear the size of your inputs can be quite large. Therefore, you should adopt one of the following heuristics:

1. First Fit Algorithm: Process the booklets one by one placing it in the first box that has enough capacity to hold the booklet. If there are no such boxes, a new box must be started and added to the list of boxes available.
2. Best Fit Algorithm: Process the booklets one by one placing it in the box where it fits the tightest (has the smallest capacity left). If there are no boxes that can hold the booklet, a new box must be started and added to the list of boxes available.
3. First Fit Decreasing Algorithm: First order the booklets by decreasing height and then perform the First Fit Algorithm. In your example you would be packing up the "Book 2" booklets first.
4. Best Fit Decreasing Algorithm: First order the booklets by decreasing height and then perform the Best Fit Algorithm.

But, of course, your orders consist of N items of of a certain type of booklet. We will take the prescription "one at a time" in the above algorithms loosely. So if you are doing, for example, the First Fit Algorithm, then when you find the first box that has the capacity to hold the booklet, it is easy enough to calculate the maximum number of those booklets, M, that box could hold and process up to min(M, N_LEFT) booklets at one time where N_LEFT is the number of booklets of that size you still have left to pack up. Likewise for any of the other three algorithms.

You can survey other bin-packing heuristics of which the above are just a sample four. I can't say one is necessarily superior to the others in all cases. I think any reasonable implementation of any of them will be satisfactory for your purposes. Anyway, this is my take.

Solution 2:

This is a bin-packing problem. The best optimal algorithm is Korf's. If this is too slow for the amount of data you have, there are various algorithms that provide good approximate answers faster.