Optimal solution for creating a pile of boxes

Question

I have a problem with one algorithm.

There are given n boxes, each one has fixed weight and strength (both given in kg). Box's strength tells us what is the maximum weight it can bear. We have to form the highest pile of given boxes (each of them has the same height). You should propose an algorithm that will always give an optimal solution, which is the longest sequence of k boxes (k <= n).

Well, that is a solution I have already figured out:

1. Firstly, we sort all of the boxes by their weight (heaviest goes at the bottom) and form a pile of them.
2. Secondly, we sort that pile by strength (the strongest goes at the bottom).
3. Then, for each box, starting from the bottom, we try to pull it down to the bottom as long as its strength enables it.
4. In the end, we have to figure out how many boxes must be removed from the top, which cause the situation that some boxes below carry much more weight than they could.

It seems that this algorithm works quite well, but I am not sure whether it gives always the optimal solution - probably it doesn't. I have been wondering about the dynamic solution, similar to the solution for knapsack problem, but I don't feel certain if it can be solved this way. There's seemingly no optimal substructure for my problem.

Thank you in advance for any help. :)

Answer 1

In default of a cleverer answer, I would try branch and bound, building the tower from the bottom up. Given a partially built tower, you can put a bound on the height of the completed tower. If the partially built tower can sustain an extra weight of X, you can work out how many boxes you could add before the extra weight is more than X - just pick out remaining boxes in order of increasing weight, ignoring their strength. If there are boxes of zero weight, put them aside in a pre-processing stage and shove them on the top later. A less accurate bound would be X divided by the weight of the lightest unused box.

Given such a bound, use backtracking search to build your tower, discarding all partial answers which could not possibly be extended to produce a higher tower than the best answer found so far.