Page 1 of 1
Boxes Into Boxes [Algorithm]
Posted: May 28th, 2009, 9:07 pm
by achele
I was reminded of this problem by the problem here (
http://www.wilmott.com/messageview.cfm? ... adid=70684) but this is more of a theoretical computer science/algorithms question...You have n boxes that are taking too much space in your garage, and you want to consolidate them to reduce space. Your plan is to produce groups of boxes by placing boxes inside of each other. A box can have at most one box immediately inside of it, and a box by itself is still considered a group. You want to nest the boxes in such a way that minimizes the number of groups created. Find an efficient algorithm that determines how you should group the boxes.
Boxes Into Boxes [Algorithm]
Posted: May 29th, 2009, 7:36 am
by trippel
Your description is quite unspecific. You do not state what the sizes of the boxes are (real numbers, are there any restrictions, ...). If you are interested in stuff like that and practice algorithm traning, go for
www.spoj.pl. It is a good Online Judge, accepting major programming languages. You will finde similar task there!
Boxes Into Boxes [Algorithm]
Posted: May 30th, 2009, 5:59 am
by achele
You can determine whether one box can fit in another in constant time. That's all you really need to know to to solve the problem in polynomial time. It's meant to be open ended, though there is a particularly efficient method for solving the problem.
Boxes Into Boxes [Algorithm]
Posted: June 2nd, 2009, 1:25 pm
by ghan
It seems that it can be done in O(n^2) time.