I believe your goal can be reduced to "packing each box so it has the smallest amount of wasted space".
(and with your shapes, it may be possible to reduce it further to "each layer of the objects in the box, should have the smallest amount of wasted space", since your objects are just 2D. Now, instead of looking at the "total number of boxes", you're looking at a smaller sub problem, which will also solve the larger problem you want. One statement will have to be better defined: "the same type of profiles shall be packed together or near by". Does "near by" mean just in the same box, or does it mean some edge must be adjacent to at least one of it's family of similarly shaped objects, or ? Now looking at each layer of objects, it should be easy to just generate all possible lay outs consistent with the "near by" rule (once you define it better), and just keep track of each layer of objects which has the least amount of wasted space. On a much more difficult solution, depth first search with Alpha Beta instead of Mini-Max, which has it's search goal set to find the smallest amount of wasted space in each box it looks at, will tear through this problem very well, also. It is not a trivial program to code, however. An idea of it can be found in any good chess or checkers program. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
