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

Here's an algorithm in Javascript

// Array of boxes [weight,strength] 
var AB=[[1,2],[3,4],[7,3],[1,10],[10,1],[4,8], [1,10]];

// for each item make set of items Potentially Above
// can leave this out and just say all others are Potentially Above
var w=0,s=1;// indices for weight, strength 
for(var i=0; i<AB.length;i++){
    var B = AB[i];
    B.pa=[];// array of potentially above boxes
    for(var j=0; j<AB.length;j++){
        if(i!=j && AB[j][w]<=B[s]){// not the same box and box B can support it
            B.pa.push(j);// at to array of potentially above boxes
        }
    }
}
// Display the weights that each box can support
for(var i=0; i<AB.length;i++){
    var B = AB[i];
    c("Item"+i+" Weight="+B[w]+", Strength="+B[s]+", Weights= "+B.pa );
}

var stacksMax=[];
var heightMax=0;

var stack = [];// height of boxes in stack
var height=0;
var canCarryWt=1e99;//Infinity;// the ground can carry anything
// Try each box in turn as the lowest  box
for(var i=0; i<AB.length;i++){
    stack = Array(AB.length);// array of heights
    height=0;
    testBox(i);
} 

// Test a box for the boxes it can support (recursive)  
function testBox(i){
    if(!stack[i]){// avoid cyclic 
        var B=AB[i];
        if(canCarryWt>=B[w]){// cadd add this box
            var couldCarryWt=canCarryWt;
            canCarryWt = Math.min(canCarryWt-B[w],B[s]); 
            stack[i]=++height;

            // test sub items
            for(var j=0;j<B.pa.length;j++){
                testBox(B.pa[j]);
            }

             // test height for being the highest
             if(height>heightMax){
                 stacksMax = [];// clear all the stacks 
                 heightMax = height;
             }
             if(height==heightMax){
                 // add a copy of stack to stacksMax
                 stacksMax.push(stack.slice());
              }
              // reset values
              height--;
              canCarryWt=couldCarryWt;
              stack[i]=0;
          }  
     }
 }

// Sort and Display
var topFirst=true;
var sortedStack=Array(heightMax)
for(var k=0; k<stacksMax.length; k++){
    // Sort items 
     stack=stacksMax[k];
     for(var i=0;i<stack.length;i++){
         if(stack[i]){
            if(topFirst){// nb heights are 1..
                sortedStack[heightMax-stack[i]]=i;
             }
             else{
                 sortedStack[stack[i]-1]=i;// -1 for 0array
             }
        }
    }
    // Display 
    drawHorizRule();
    var weightSupported=0;
    for(i=0;i<heightMax;i++) {
        var B= AB[sortedStack[i]];
    var status = (B[s]>= weightSupported)?"OK":"ERROR";
        c("Height"+i+" Box="+sortedStack[i] + ",["+B[w]+","+B[s] + "] "+status);
        weightSupported+=B[w];
    }
}
// Display functions
function c(s){
    // this depends on your environment
}
function drawHorizRule(){  
    c("<hr/>");
}

Answer 2

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.

Answer 3

You can solve this using dynamic programming.

weight[i] := weight of box i
strength[i] := strength of box i
N(w,b) := maximum number of boxes you can stack <= weight w with box b on bottom

Notice that to calculate N(w,b), you put box b on the bottom. Then you calculate the maximum number of boxes you can put on top of it. Well this is easily done if you loop through the possible boxes that can be placed above it.

You then have the recurrence relation:

N(w,b) = 1+max{ N( min(w-weight[b],strength[b]),i ) }

Your answer is then: max{ N(W,b) } where W=sum(weight[i]).