CODEWITHSUNDEEP
algorithmdynamic-programming
so.very.tired
so.very.tired

Reputation: 3086

The box stacking algorithm

I have a question about the box stacking algorithm that was suggested here: http://people.csail.mit.edu/bdean/6.046/dp/

The algorithm making some wrong assumption: In the video, it says that we "sort the boxes in order of decresing base area...etc". We do it because 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. but if box B_1 has a base area that is bigger the box B_2, that doesn't mean that it also has its width and depth bigger than the width and depth of box B_2.

for example, a box with a 1x8 base dimensions has a bigger base area than a box with a 2x3 dimensions, but still: 1<2 (and 1<3), and therefor we cannot stack box B_2 onto B_1. what am I missing here?

Upvotes: 4

Views: 1765

Answers (2)

tweaking
tweaking

Reputation: 350

It is confusing how this is presented but the whole point is to find a sequence from which you can apply the LIS (least increasing subsequence) on.

Upvotes: 0

Sneftel
Sneftel

Reputation: 41542

It's a question of necessary versus sufficient conditions. It's true that you can run into situations where B_2 can't be stacked on B_1, but under those circumstances, B_1 couldn't be stacked on B_2 either, so there'd be no value in switching them in the consideration order. That is, if B_a has a larger base than B_b, we know that B_a cannot be stacked on B_b (because it has at least one dimension violating the constraint).

Put differently: In the optimal stack of boxes, all are ordered by decreasing base area. So if the list of all boxes is ordered by decreasing base area, the optimal stack is guaranteed to be a subsequence of the list of all boxes -- and so, of course, is the sequence consisting of only the first k boxes. Which means that, as required by dynamic programming, when examining box k, the optimal stack which box k can rest on has already been generated during a previous round.

Upvotes: 4

Related Questions