How are the ouputs 60,15 for me they are coming out to be 48,13

#1

can u explain me the ouputs of the testcase

#2

@neha_153 I am not able to see the test cases. Can you share that with me.

#3

2 4 4 6 7 1 2 3 4 5 6 10 12 32 3 1 2 3 4 5 6 3 4 1

#4

2
4
4 6 7 1 2 3 4 5 6 10 12 32
3
1 2 3 4 5 6 3 4 1

#5

Okay I will explain the second case where the answer is 15.
Boxes are stacked in this order.

6 X 5 X 4
5 X 4 X 6
4 X 3 X 1
2 X 3 X 1
1 X 2 X 3

Last column is height , so we get 15 for this.

Iā€™m writing the approach as well in case you have further doubts.

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

Following is the implementation of the above solution https://ide.codingblocks.com/s/280871

#6

ok so this is the unbounded case
i was considering box only once

#7

if you have any further queries let me know else mark this doubt as resolved.