Algorithms

Moderators: None (Apply to moderate this forum)
Number of posts: 786

This Forum Only

Need your intelligence and knowledge!! Posted by kcakir on 1 Mar 2009 at 11:00 AM
Hi to all!
I search an algorithm to that problem:
You have N rectangles N is may be between 0 and 1000. You must arrange them with the least area. You are given the dimensions of all rectangles (may be square you know from math all squares are rectangle ).
and they want the minimum area includes all rectangles and coordinates of left corner of each rectangle assuming (0,0) the upper left corner.

Re: Need your intelligence and knowledge!! Posted by schmiley397 on 1 Mar 2009 at 7:40 PM
I believe that is a famous NP-complete problem. NP-complete roughly means that if you want the best solution (the one that gives the smallest area) you'll have to try every combination possible, which is probably unthinkable with 1000 rectangles.
However there might be good suboptimal algorithms. They would depend on your rectangles. Can they be of any size? Or just multiples of a smallest unit (1x2, 2x3 ...)?
Re: Need your intelligence and knowledge!! Posted by kcakir on 2 Mar 2009 at 1:03 AM
There isnt any relation between dimensions.but there is a limit for dimensions. they can be 1000000 maximum.
Re: Need your intelligence and knowledge!! Posted by kcakir on 2 Mar 2009 at 1:09 AM
And i forgot to say the last area will be a rectangle also. Briefly we will make the smallest rectangle with rectangles.

Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic