Author |
Topic: maximum subset problem (Read 5846 times) |
|
hary
Junior Member
Posts: 107
|
 |
maximum subset problem
« on: Jan 31st, 2010, 10:26pm » |
 Quote  Modify
|
You are given a lot of cuboid boxes with different length, breadth and height. You need to find the maximum subset which can fit into each other.
|
|
 IP Logged |
|
|
|
birbal
Full Member
Gender: 
Posts: 250
|
|
Re: maximum subset problem
« Reply #1 on: Jan 31st, 2010, 11:21pm » |
Quote Modify
|
on Jan 31st, 2010, 10:26pm, hary wrote:| You are given a lot of cuboid boxes with different length, breadth and height. You need to find the maximum subset which can fit into each other. |
|
Looks similar to the box stacking problem. This can be solved with an appropriate DP construction.
See this http://people.csail.mit.edu/bdean/6.046/dp/ 
hope it will help.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: maximum subset problem
« Reply #2 on: Feb 1st, 2010, 2:58am » |
Quote Modify
|
Build a directed graph (where and edge from A to B means A fits inside B; or if you prefer the other way around, but be consistent  )
Then find the longest path in the graph. Since there can be no cycles, this can be done fairly easily using the partial order in the DAG.
And of course, you can do it without explicitly building a graph.
|
| « Last Edit: Feb 1st, 2010, 3:00am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: maximum subset problem
« Reply #3 on: Feb 1st, 2010, 3:12am » |
Quote Modify
|
on Jan 31st, 2010, 11:21pm, birbal wrote:
That gives some good ideas.
You can sort the boxes in (decreasing) order of volume in O(n log n). Because a box can only fit in a larger box.
Associate a counter with each box, initialized to one. This counts the number of boxes in the subset fitting inside each other starting with this one as the largest box.
Then start with the box at the back (the smallest), and for each larger box, if the small one fits inside change the counter of the bigger box to the maximum of the current value, and the counter-value of the small box plus 1.
Do this for all boxes from back to front. O(n2)
Then find the box with the highest counter, that will tell you how many boxes you can at most fit inside each other.
To find the maximizing subset it is useful to insert/replace backlinks during the fitting step if the smaller box increases the larger box's counter.
|
| « Last Edit: Feb 1st, 2010, 3:13am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: maximum subset problem
« Reply #4 on: Feb 1st, 2010, 12:04pm » |
Quote Modify
|
Can we make it more efficient (though not asymptotically)
Ex: For a given larger box j, we look at all the boxes i, where Vol(i) < Vol(j) and we find the max(Cap(i)) among them, where Cap(i) is capacity of the box i, number of boxes it holds. And we will say Cap(j) = Cap(i) + 1
Following the same wording as given in that MIT link.
To make it efficient:
We maintain other array of size n, where A[i] stores maximum capacity using only first i boxes.
So in the second phase of the algorithm, when we are trying to find the smaller box with largest capacity to fit into the larger box we can use the array A to terminate the loop early
|
|
IP Logged |
|
|
|
witee
Newbie
Posts: 48
|
|
Re: maximum subset problem
« Reply #5 on: Mar 17th, 2010, 3:02pm » |
Quote Modify
|
how to check whether a box fits into another box..
i mean we have to check all the permutations of 1 box's(ht,wd,len) with another box.??.or is there any other way?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: maximum subset problem
« Reply #6 on: Mar 17th, 2010, 5:02pm » |
Quote Modify
|
on Mar 17th, 2010, 3:02pm, witee wrote:how to check whether a box fits into another box..
i mean we have to check all the permutations of 1 box's(ht,wd,len) with another box.??.or is there any other way? |
|
You can sort the dimensions of both boxes. Take the length to be the longest side, height to be the shortest side, width to be the remaining side.
Then for A to fit inside B, A's length must be less than B's length, A's width less than B's width and A's height less than B's height.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: maximum subset problem
« Reply #7 on: Mar 18th, 2010, 7:17am » |
Quote Modify
|
But... did you know that a 7x5x1 box fits in a 6x6x6 box?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: maximum subset problem
« Reply #8 on: Mar 18th, 2010, 7:53am » |
Quote Modify
|
If you allow that kind of fitting, then it does become a bit more complicated, yes.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: maximum subset problem
« Reply #9 on: Mar 19th, 2010, 3:27am » |
Quote Modify
|
I'd say more than a bit. I don't know how many different positions need to be checked. And some of them are a headache (like a long box along the long diagonal of the outer box).
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: maximum subset problem
« Reply #10 on: Mar 24th, 2011, 6:45am » |
Quote Modify
|
on Feb 1st, 2010, 12:04pm, mistaken_id wrote:Can we make it more efficient (though not asymptotically)
Ex: For a given larger box j, we look at all the boxes i, where Vol(i) < Vol(j) and we find the max(Cap(i)) among them, where Cap(i) is capacity of the box i, number of boxes it holds. And we will say Cap(j) = Cap(i) + 1
Following the same wording as given in that MIT link.
To make it efficient:
We maintain other array of size n, where A[i] stores maximum capacity using only first i boxes.
So in the second phase of the algorithm, when we are trying to find the smaller box with largest capacity to fit into the larger box we can use the array A to terminate the loop early
|
|
That can be a good optimization, but the worst case time would be O(n^2).
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: maximum subset problem
« Reply #11 on: Jan 9th, 2012, 11:02am » |
Quote Modify
|
Revisiting this problem, i just got another efficient solution with which i don't see any problem. Please point out if you see any.
Following the convention suggested by towr, let length of a box be its greatest side. Sort all the boxes on length. Now for any two boxes A,B
define A < B if( A.breadth < B.breadth && A.height < B.height)
Now our problem reduces to finding the longest increasing sub-sequence, which can be done in O(n logn) i think.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
akasina9
Newbie
x = 0x2B | ~ 0x2B. x is the question
Gender:
Posts: 9
|
|
Re: maximum subset problem
« Reply #12 on: Nov 16th, 2012, 3:23am » |
Quote Modify
|
birbal's solutions seems to work in the general case. But is there any efficient solution for the case Grimbal mentioned?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print