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 whenL 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.
Dynamic programming in Bin packing
c++;algorithms;optimization;dynamic programming