Stack of Boxes - Dynamic Programming

Question

I am currently practicing some dynamic programming. I came across the Stack of Boxes.
The boxes are represented as:

struct Box{
    double h;
    double w;
    double d;
};

And the problem is creating the highest stack of boxes where each box in the stack is larger (in both width and depth) than the one above it. Let's assume that in this case boxes cannot be rotated.

I am storing the boxes in a std::vector<Box>. I am first doing a stable sort by width and then by depth, so that whenever I pick a box I will only need to search forward for the next box that fits.

And here is my question - Is this optimal?
I guess that every time I picked a box I need to search linear time (O(n)) in order to pick the next possible box.
Is there a different way to store the boxes that might be better in time complexity?

Any other optimizations are also welcome of course.

My full code:

//Get index of next box that fits or -1 if none
int getP(std::vector<Box>& boxes, int n){
    double n_w = boxes[n].w;
    double n_d = boxes[n].d;
    for (int i=n-1; i >= 0; i--){
        if (n_w > boxes[i].w && n_d > boxes[i].d)
            return i;
    }
    return -1;
}

//Get highest possible stack.
double stackOfBoxes(std::vector<Box>& boxes, int n, Box* bottom){
    if (n == -1)
        return 0;
    if (bottom == NULL || (bottom->d > boxes[n].d && bottom->w > boxes[n].w))
        return max(stackOfBoxes(boxes, n-1, bottom),stackOfBoxes(boxes, getP(boxes,n), &boxes[n])+boxes[n].h);
    else
        return stackOfBoxes(boxes, n-1, bottom);
}


int main(){
    std::vector<Box> boxes = { {3,1,1},{5,2,2},{10,7,7} };
    std::stable_sort(boxes.begin(), boxes.end(), sortByW);
    std::stable_sort(boxes.begin(), boxes.end(), sortByD);

    cout << stackOfBoxes(boxes, 2, NULL) << endl;
}

In the box stacking problem I know, boxes can be rotated (any side can function as the base). Is it the case for you ? — Nelfeal
– Nelfeal, Commented Aug 19, 2016 at 16:43
@Nelxiost That's an interesting case, but let assume for now that they cannot be rotated. Edited post as well. — A. Sarid
– A. Sarid, Commented Aug 19, 2016 at 16:52

Nelfeal · Accepted Answer · 2016-08-19 16:52:11Z

2

And here is my question - Is this optimal?

It is incorrect.

I tried your code with the same input, except for the depth of the third box which I made 0.5.

Here is the result. It gives 15 where the answer should be 10 since no other box can fit on top of the third one.

edited Aug 19, 2016 at 16:52

answered Aug 19, 2016 at 16:40

Nelfeal

13.3k1 gold badge23 silver badges42 bronze badges

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

1 Comment

A. Sarid Over a year ago

Thanks, I have corrected my code, see my comment to @j_random_hacker below

j_random_hacker · Accepted Answer · 2016-08-19 17:26:28Z

1

The code is actually incorrect, because you are assuming that the optimal solution to a subproblem can be extended to include the current (nth) box when it can't necessarily.

Example: {2, 50, 1}, {1, 1, 2}, {1, 3, 3}

(The above example is unchanged by the 2 sorts.) Your algorithm's getP(boxes, 3) will determine, correctly, that the second box, {1, 1, 2}, is the latest box that can precede the final {1, 3, 3} box, but by asking for the solution to the subproblem stackOfBoxes(boxes, 1), the calling code makes the assumption that any box that comes before the second box in the list (i.e., either the first box or the second) can also legally precede the final {1, 3, 3} box -- but that's not true. stackOfBoxes(boxes, 1) eventually correctly returns 2, which can only be achieved by using the first box -- but the outer stackOfBoxes(boxes, 2) call thinks it can just add the final {1, 3, 3} box on top of this, despite the fact that 50 > 3.

It helps to be extremely clear about what the return value of stackOfBoxes(boxes, n) means. From how you have written the code here, it must mean "The maximum height achievable by any valid stack (subsequence) of boxes that uses only boxes at indices <= n". This problem formulation does not unfortunately lead to optimal substructure. (There exist other formulations that do, however.)

(Thanks to Nelxiost for finding a bug in my earlier description of the bug!)

answered Aug 19, 2016 at 17:26

j_random_hacker

51.6k10 gold badges109 silver badges176 bronze badges

3 Comments

A. Sarid Over a year ago

First, thanks for the correction and the explanation. I always have to keep track of the bottom box in order to compare it with the current n box before adding it to the stack. I have corrected my code with this case, hopefully now it covers all cases. Second, my question was mainly to find if there is any other (better) way to hold and search for the next box that fits.

j_random_hacker Over a year ago

I can't spare the time and effort to try to prove that there's a bug, but if there is one, you can probably find it by generating all possible instances below a certain size (e.g. at most 4 boxes with all four dimensions in the range 1 .. 3) and comparing the result of your algorithm against a known-good brute-force algorithm for each one. If you do that, and write an English sentence defining exactly what you think stackOfBoxes(boxes, n, bottom) returns in terms of n and bottom (as I did in my answer), I'll keep looking at this.

j_random_hacker Over a year ago

One more thing: You aren't actually doing any memoisation in your (original or updated) code -- as implemented, it's just the "plain" recursion, which takes time exponential in n.

Collectives™ on Stack Overflow

Stack of Boxes - Dynamic Programming

2 Answers 2

1 Comment

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related