How much time do you have? And how much profiles you need to process? Those are the two questions that pretty much will define what algo you'll need to use.
I don't know about NP-complete stuff, but if I have to take a simple one, it'll be like this: 1. Create a "random" solution, basically a placement where you can actually fit all of your profiles in any number of box. This will prove that there is at least one feasible solution. (one example of non-feasible problem would be a profile that's too big for a box to place) You can "pre-optimize" the "random" solution to your intuition, like what you've done, placing similarly sized profiles together. 2. Implement a 2-opt or 3-opt optimization algo, this is a heuristic algorithm (which means it tries a lot of different combination to find a better one). How it works, you just need to swap one profile with another profile. Say you have a placement like ABCD, you switch them to BACD, ACBD, etc... basically just permutates it. For every switch, you'll need to evaluate the goal function value, which in your case would be the total space wasted. If it's smaller, then we'll take that solution as a better solution than the original. Repeat this swap until every combination is tried, and what you will get is almost always the best you can get. 3. You can implement a modified 2-opt algo (there are several, try wikipedia), which basically removes the double checking stuff, etc. But this will add more complexity to your code. This way, you can go up and running within hours, without the need of overhead. HTH -----Original Message----- From: [email protected] [mailto:[EMAIL PROTECTED] On Behalf Of [EMAIL PROTECTED] Sent: 16 Oktober 2007 23:07 To: Algorithm Geeks Subject: [algogeeks] Re: How to optimize packing a box with different shaped profiles dear adak & gene, thanks for the interesting thoughts you provided. obviously i'm not an algorithm expert but i'm a very experienced C# developer. so i need this thing explained with simple terms. to further define near by, profiles of the same shape have to be either packed next or on top of each other. to try each possible layout and pick the one with the least amount of wasted space seems to be pretty straight forward. this works fine if we only pack 1 box, but what if we have to pack let's say 5 boxes of different profiles? then the layout combinations spread across all the boxes. reto On Oct 16, 7:34 am, adak <[EMAIL PROTECTED]> wrote: > Obviously there is no need for the one line of code that deals with > minimizing /maximizing player's moves, in this case. > > A/B would still prune, but it would only prune out the piece > arrangements that left sub optimal piece arrangements, with more > wasted space. > > You're right, Gene, this is indeed an interesting problem. Wish I had > more time to study it. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
