Algorithms

Moderators: None (Apply to moderate this forum)
Number of threads: 384
Number of posts: 762

This Forum Only
Post New Thread
Single Post View       Linear View       Threaded View      f

Report
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.
Thans for your help

Report
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 ...)?
Report
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.
Report
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
© Copyright 2011 Programmersheaven.com - All rights reserved.
Reproduction in whole or in part, in any form or medium without express written permission is prohibited.
Violators of this policy may be subject to legal action. Please read our Terms Of Use and Privacy Statement for more information.
Operated by CommunityHeaven, a BootstrapLabs company.