The problem I am trying to solve is called crate stacking. Here is the description: Flagging
You are given a set of n types of rectangular three-dimensional boxes, where the ith box has a height h (i), a width w (i) and a depth d (i) (all real numbers). You want to create a stack of boxes that is as high as possible, but you can only stack the box on top of another block if the dimensions of the two-dimensional base of the bottom window are strictly larger than the 2-D dimensions in the top box. Of course, you can rotate the box so that any part of it functions as its base. It is also allowed to use multiple instances of the same type.
I thought of the following solution: Let one cell be represented as (h, w, d). Then we can imagine the sequence of all boxes of the type (h1, w1, d1), (h2, w2, d2), (h3, w3, d3). In order to take care of the part that we can use for any rotation using the above sequence, I will generate all possible permutations for the block. Thus, for a block like (7,1,2), 6 generated configurations will be created. To solve the problem, I plan to first sort the boxes by width in decoding order. Then I get a sequence of boxes, for example (h1, w1, d1), (h2, w2, d2), etc. Then I solve the problem using a concept similar to the longest descriptive subsequence. Let LDS (i) be the longest decreasing subsequence ending in i then LDS (i) = {max [LDS (k)] + height i for kwi and dk> di }
Does anyone see an error with the above?
Please let me know if this decision is implemented correctly.
source share