Problem: Given a list L of objects of possible sizes from set S={1,2,4,8} and unlimited supply of bins of sizes 16 each and we have to use minimum possible numbers of bins to pack all objects of L.
I am also searching for an optimal (or near optimal) solution using dynamic programming or otherwise in the following scenarios when
- L is not given offline, instead we are asked to fit objects one by one without knowing future requests(1-D online vector bin packing).
- sizes can be from SXS and bins are of capacity (16,16) each. (2-D vector bin packing).
Assumption: Optimal packing means the best possible packing from all possible packing i.e the packing with the minimum numbers of bins used.
Actually generalized vector bin packing is NP-hard, but I think due standard sizes from finite set, more efficient and better solutions may exist.
My approach: Clearly, 1-D offline can packed in <=optimal+1 using clever pairing of objects .
But I am stuck for the other 2 aspects asked above.
I know about First Fit,Best Fit, First Fit Decreasing algorithms but I am searching for this problem specific solution.
Best Answer
For the 1-Dimensional offline case, suppose you sort all objects from large to small. Due to the sizes, no nasty cutoffs will occur, and all bins except for maybe the last one will be filled to full capacity. I guess this is what you mean with the clever pairing.
For the online case, if you keep 4 different bins, one for each size, then you will be able to fill every bin completely except for maybe 4 bins. If the list is large enough, this will be very close to an optimal solution. Are the size of the list L and the probability of each size occuring known in advance?