The box stacking algorithm

Question

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?

Sneftel · Accepted Answer · 2013-11-15 16:14:41Z

4

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.

edited Nov 15, 2013 at 16:14

answered Nov 15, 2013 at 16:08

Sneftel

41.9k13 gold badges78 silver badges112 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

tweaking · Accepted Answer · 2013-11-20 18:25:26Z

0

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.

answered Nov 20, 2013 at 18:25

tweaking

3504 silver badges6 bronze badges

Collectives™ on Stack Overflow

The box stacking algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related