Bin packing - exact np-hard exponential algorithm

Question

I wrote a heuristic algorithm for the bin packing problem using best-fit aproach, itens S=(i1,...,in), bins size T, and a want to create a real exact exponential algorithm witch calculates the optimal solution(minimum numbers of bins to pack all the itens), but I have no idea how to check every possibility of packing, I'm doing in C.

Somebody can tell me any ideas what structs I have to use? How can I test all de combinations of itens? It has to be a recursive algorithm? Have some book ou article that may help me?

sorry for my bad english

Answer 1

The algorithm given will find one packing, usually one that is quite good, but not necessarily optimal, so it does not solve the problem.

For NP complete problems, algorithms that solve them are usually easiest to describe recursively (iterative descriptions mostly end up making explicit all the book-keeping that is hidden by recursion). For bin packing, you may start with a minimum number of bins (upper Gaussian of sum of object sizes divided by bin size, but you can even start with 1), try all combinations of assignments of objects to bins, check for each such assignment that it is legal (sum of bin content sizes <= bin size for each bin), return accepting (or outputing the found assignment) if it is, or increase number of bins if no assignment was found.

You asked for structures, here is one idea: Each bin should somehow describe the objects contained (list or array) and you need a list (or array) of all your bins. With these fairly simple structures, a recursive algorithm looks like this: To try out all possible assignments you run a loop for each object that will try assigning it to each available bin. Either you wait for all objects to be assigned before checking legality, or (as a minor optimization) you only assign an object to the bins it fits in before going on to the next object (that's the recursion that ends when the last object has been assigned), going back to the previous object if no such bin is found or (for the first object) increasing the number of bins before trying again.

Hope this helps.