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.
