programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Rob Spoor
• Tim Cooke
• Junilu Lacar
Sheriffs:
• Henry Wong
• Liutauras Vilda
• Jeanne Boyarsky
Saloon Keepers:
• Jesse Silverman
• Tim Holloway
• Stephan van Hulst
• Tim Moores
• Carey Brown
Bartenders:
• Al Hobbs
• Mikalai Zaikin
• Piet Souris

# assignment problem

Ranch Hand
Posts: 135
• • Number of slices to send:
Optional 'thank-you' note:
• • Hi,
i've got a task, which i have no idea how to solve, this task sounds like this :
" you have N rectangles. and need to construct a rectangle of a maximum perimeter using given rectangles (only a part of given rectangles may be used) "
my problem is that i have no idea where to start from i tried to search the web, but i don't even know the name of the algorithm that must be used to solve the problem.
any help appreciated

Ranch Hand
Posts: 504
• • Number of slices to send:
Optional 'thank-you' note:
• • Hi Andrew, these are just my ideas: Given an atomic rectangle with sides b(height) and a(width):
a
----------
| |
| |b
----------
where a>b. The atomic perimeter P=2*(a+b). If you stack another rectangle side-by-side (which means their height to the right is common), the resulting rectangle perimeter is:
P1=2*(a+b)+2*a or 2*(a+b+a) or 2*(2a+b).
2a
-------------------
| | |
| | |b
-------------------
If you stack a new rectangle on top of the existing one like this:
a
----------
| |
| |
---------- 2b
| |
| |
----------
The resulting perimeter is:
P2=2*(a+b)+2*b or 2*(2b+a).
Let's examine which structure is more beneficial in terms of getting the max perimeter. We will subtract the second case perimeter from the first case one:
P1-P2=2(2a+b)-2(2b+a)=2(2a+b-2b-a)=2(a-b)
Given a>b from the beginning, the result is positive and the first perimeter proved to be greater. Now, there are only two ways you can stack rectangles that we've examined above, so other combinations are impossible.
The rest is simple. You have N rectangles. You can use only part of them (I'd say, up to N-1 rectangles). We've seen that the max perimeter for 2 rectangles is P=2*(2a+b). For 3 rectangles the perimeter is 2(3a+b), and for N-1 rectangles the max perimeter is P=2*((N-1)*a+b)
I hope this helps ideas wise. The output looks not what I drew, but I'm not in control. [ November 16, 2003: Message edited by: Vad Fogel ] You showed up just in time for the waffles! And this tiny ad: Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton