Highest pile of boxes (algorithm)

Question

I have big problem with this task:

You have a n (n <= 1000) boxes. Each of them have some strength and weight. Strength of box is a maximal weight of boxes which you can put on this box. What is maximal high of pile, that you can make with this boxes?

In other words if I have a boxes (x1, y1), (x2, y2), .. , (xk, yk), where x_i is a strength of box, I can build a pile if and only if:

x2 >= y1

x3 >= y1+y2

...

xk >= y1+y2+...+y_(k-1)

Do you have some idea how solve it? I heard that we must find some sorting of this boxes, such that if we can do a pile with boxes (a1, a2, ... ak) then always a1 < a2 < ... < ak. I see that, if we will sort that this boxes, we can find a answer by easy dynamic programming. But as I said, I don't know how sort it :\ Thanks in advance.

Answer 1

Because the lowest box must support the most weight, you need the strongest box as lowest box. With the same reasoning you need the wekaest box on the top.

So sort your boxes with "strength" as a sort key and put the strongest at the bottom, the weakest at the top.

Now for each box calculate the weight it does support in its current position.

If some box has more weight than it can support, then remove the heaviest box above this box.

Repeat until all boxes left in the pile are ok.

EDIT

This solution is not correct (see comments) I leave it here for reference.

Answer 2

Here is an idea that is adapted from the A* approach. However, instead of finding a minimum length path, we want to find a maximum height pile.

Let's start with some theoretical analysis. Consider, we already have a pile with strength s1 and we put another box on top of that with weight w2 and strength s2. The strength of the resulting pile will be min(s1 - w2, s2).

We start with an empty pile state (height, strength, boxes) = (0, infinity, empty). Furthermore, for any pile state, we need an upper bound how many more boxes we can put on that pile. One way to calculate this bound is to use the quotient of the pile's strength and the minimum box weight (of the boxes that are not on that pile). To calculate this heuristic efficiently, initially sorting the boxes by their weight can be desirable.

The rest is a simple application of the A* algorithm. From all states in the available set, choose the one with the highest expected pile (= height + heuristic). If this pile is higher than your currently highest pile, save this state. Calculate the resulting pile states for each box that is not yet on the pile and remove the current state from the available set. Then iterate.

You have found the highest pile if none of the pile states in the available sets have an expected pile height higher than the currently highest pile.

This approach lets you ignore pile states that obviously cannot contribute to the highest pile very early. Since a pile state can only be reached from exactly one other pile state, you don't need to handle the states in an open and a closed list.