CODEWITHSUNDEEP
dynamic-programming
TimeToCodeTheRoad
TimeToCodeTheRoad

Reputation: 7312

Tallest possible tower built using stacking boxes

The problem I am trying to solve is called box stacking. Here is the description: Box Stacking

You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions 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 functions as its base. It is also allowable to use multiple instances of the same type of box.

I have thought of the following solution: Let one box be represented as (h,w,d). Then we can represent the sequence of all boxes like (h1, w1, d1), (h2,w2,d2), (h3,w3,d3). To take care of the part that we can use any rotation, using the above sequence, I will generate all possible permutation for a block. Thus, for a block like (7,1,2) there will be 6 generated configurations. To solve the problem, I plan to sort the boxes first in terms of their width in decresing order. Then, I will get a sequence of boxes like (h1, w1, d1), (h2,w2,d2) and so on Then I solve the problem using a concept similar to longest descresing subsequence Let LDS(i) be the longest decreasing subsequence ending at i Then LDS(i)= { max[LDS(k)] + height of i for kwi and dk>di}

Does anyone see an error with the the above?

Please let me know if the above solution is correct

Upvotes: 4

Views: 3728

Answers (1)

Lajos Veres
Lajos Veres

Reputation: 13725

Your solution seems to be similar to this: http://www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/

But the last phrase seems to be unclear/unprecize. You compare only one dimension.

Upvotes: 0

Related Questions