Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Dynamic Programming — Box Stacking Problem

Objec­tive: You are given a set of n types of rec­tan­gu­lar 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real num­bers). You want to cre­ate a stack of boxes which is as tall as pos­si­ble, but you can only stack a box on top of another box if the dimen­sions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side func­tions as its base. It is also allow­able to use mul­ti­ple instances of the same type of box.

Source : http://people.csail.mit.edu/bdean/6.046/dp/ ,

Box Stacking 1

Approach:

So we have n boxes. first thing we will con­cen­trate about box rota­tions since we each rota­tion will cre­ate more pos­si­bil­i­ties for mak­ing stack, remem­ber we have unlim­ited num­ber of boxes.

Box Rota­tions:

Though we say that we can rotate a box but if you look closely we have one 3 unique pos­si­bil­i­ties which will have dif­fer­ent base area.

Box Stacking - Rotations

So for each given box we will gen­er­ate all the pos­si­bil­i­ties. Since we have unlim­ited boxes we will use all the boxes to make the stack of max­i­mum height.

Now this prob­lem has reduced to the vari­a­tion of Longest Increas­ing Sub­se­quence.

Now to cre­ate the stack of max­i­mum height we need to place the box with max base area at the bot­tom and on top of that box with 2nd best base area and so on.

Sort the boxes in descend­ing order based on the their base area. (I have solved this prob­lem in java so i have  over­rid­den the com­pareTo(). Click here to read more about how to sort java objects. )

Now we have all the boxes in sorted order. We will take one box at a time ( in descend­ing order) . A box can be placed on another box only when the upper box is strictly larger than the lower box means width and depth of the upper box is greater than the lower box.

Let’s say

optHeight[i] =  Maximum stack height created by i boxes.  

For every box we have two options either it can be placed of one of the boxes if it is smaller than those boxes or start a new stack with that box. So we will be cre­at­ing mul­ti­ple stacks. At the end we will return the height of biggest stack.

Let’s see how the recur­sive equa­tion will look like

Box Stacking - Recurrence Equation

See the com­plete code:

Out­put:

All possible combination of boxes after rotation

11 20 40
20 11 40
40 11 20
5 8 9
4 7 9
8 5 9
9 5 8
7 4 9
9 4 7
1 2 3
2 1 3
3 1 2

Max height which can be obtained :78

You may also like...