Box stacking problem 2D

#1

Sir, I am unable to get 60 for the sample test case provided

#2

Hello @pangatt4 please explain your approach and share your code so that we can discuss.

#3

Hello, I am using concept of Longest Increasing Subsequence:

#4

Hello @pangatt4 cross check your approach and code:
this question is a classic dp problem so don’t loose hope if you can’t think of a solution,
In this problem following are the key points to note in the problem statement:

  1. A box can be placed on top of another box only if both width and depth of the upper placed box are smaller than width and depth of the lower box respectively.
  2. We can rotate boxes such that width is smaller than depth. For example, if there is a box with dimensions {1x2x3} where 1 is height, 2×3 is base, then there can be three possibilities, {1x2x3}, {2x1x3} and {3x1x2}
  3. We can use multiple instances of boxes. What it means is, we can have two different rotations of a box as part of our maximum height stack.

Following is the solution based on DP solution of LIS problem.

  1. Generate all 3 rotations of all boxes. The size of rotation array becomes 3 times the size of original array. For simplicity, we consider depth as always smaller than or equal to width.
  2. Sort the above generated 3n boxes in decreasing order of base area.
  3. After sorting the boxes, the problem is same as LIS with following optimal substructure property. MSH(i) = Maximum possible Stack Height with box i at top of stack MSH(i) = { Max ( MSH(j) ) + height(i) } where j < i and width(j) > width(i) and depth(j) > depth(i). If there is no such j then MSH(i) = height(i)
  4. To get overall maximum height, we return max(MSH(i)) where 0 < i < n
    Here for your reference i am attaching the code:
    https://ide.codingblocks.com/s/304534
    if you have any doubt you can ask here:
    Happy Learning!!
1 Like
#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.