optimal bin packing problem
I have a homework assignment that I'm really stuck on. I'm not looking for code (I'm sure I could find that if I wanted, but I really want to UNDERSTAND this).
I need to make a recursive method to find the OPTIMAL solution (least number of bins used).
The professor basically gave us an algorithm to use, but it confuses the heck out of me. I seriously think I could do this other ways, but I don't think we are allowed.
Here is what was given to us (I'll post my couple of questions below):
If there are no items left, there is nothing left to pack; return the current set of bins(base case).
For the recursive case:
1) Make a (deep) copy of the list of items, and remove one item from it.
2) For every bin, make a (deep copy) of the entire set of bins, and place the item in that bin. If the item fits, recursively apply the algorithm with the same number of bins, the modified list of items (the copy made above), and the copied set of bins with the item added.
3) Do the same thing as (2) except place the item in a new (previously empty) bin in the copied set.
4) Pick the best result from steps (2) and (3) (the one with the fewest bins) and return it.
OK, the part I don't get is the "for every bin, make a (deep) copy of the entire set of bins". If the first item tested (in the first copied set of bins) fits, the algorithm is recursed.. So I don't really grasp how it would actually test the item in every other bin. I know I must be missing something here, but I've spent at least 15 hours on this and have gotten virtually nowhere on this portion of the assignment.
This is obviously supposed to be an exhaustive search, since being an NP problem that would be the only way to attain an optimal solution. I tried coding what I thought was meant by this above pseudo-algorithm, but without testing every bin, i only ended up with a first-fit result.
If someone could give me a bit of insight into what is meant by the line "for every bin, make a (deep) copy of the entire set of bins", and how it could possibly be applied so that the recursion doesn't just happen before the item is placed into following bins it would be greatly appreciated.
I don't want to post any code here because I don't want it to look like another "do my homework" post, but if someone wants to see where I'm at, I can do so. Also, before anyone says I should just ask the professor or whatever, he is Chinese with a REALLY strong accent, and so are all the assistants (really...), and I can't understand a word they say. So although I'm attending all lectures, I'm still basically teaching myself. :P
