aspose file tools*
The moose likes Java in General and the fly likes assignment problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "assignment problem" Watch "assignment problem" New topic
Author

assignment problem

Andrew Lit
Ranch Hand

Joined: Jul 01, 2002
Posts: 135
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
Ranch Hand

Joined: Aug 25, 2003
Posts: 504
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 ]
 
 
subject: assignment problem