assignment problem

[Andrew Lit]

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

[Vad Fogel]

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 ]