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. :)

Expropriate

Similar to:- #6893541 – Clearly

Can you indicate the source of this problem, providing proper attribution for your sources? – Greenebaum

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.

Chuchuah

Answer 2

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/>");
}

Clearly

The algorithm looks interesting. Do you have the original source (URL, maybe)? – Lawrencelawrencium

@Lawrencelawrencium The sort of problem is called longest path in a directed acyclic graph. – Clearly

Thanks for the info. i'll look it up. – Lawrencelawrencium

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]).

Ables

Does the answer should be max{N(W,b)}, not min{N(W,b)}, doesn't it? And one more thing. N(w,b) is the maximum number of boxes I can stack, which total weight is less than or equal w and on the bottom of them is b box? – Expropriate

1. Oh sorry, that was a typo. Nice catch. 2. Yes that is correct. – Ables

Do I take it that this assumes that there is effectively an infinite supply of boxes of each possible type? It seems to me that if you have to keep track of how many boxes of each type are still available for use, the state space of a dynamic programming approach will be unmanageable. – Chuchuah

@tskuzzy: Well, it is quite what I've thought about if consider it as a dynamic problem, so fill the table like for knapsacks. But it is said in the body of the problem that we have to give a sequence of boxes (I suppose that it could be numbers as well as pairs of weight and strength) that form a pile, not just the maximum number we can stack from given set. – Expropriate

@mcdowella: No, there are finite number (equal n) of boxes and there is nothing like a box type. Some boxes could have the same weight or strength (or even both) as well as there could be not even two same boxes. – Expropriate

@RobertMarianski: It is easy to modify the algorithm to give the sequence. For each N(w,b), also keep track of the box that was placed above b. Then you can work backwards from the solution. – Ables

@tskuzzy, I think I'm missing something, could you clarify how your boxes are ordered and why you consider only boxes with index i < b for the DP? – Olympie

@kyun: Ah, that should not be there. That was from an earlier (incorrect) algorithm that I posted. Thanks. :) – Ables

Ah good, confused me :). Now for mcdowella's problem, keeping track of state doesn't seem like such a trivial problem. In fact your DP states would now have to keep track of not only the box directly above b but all of the boxes above b in the pile. This would mean states of the form N(w,b,Set<use boxes>) which (as correctly pointed out) could lead to a state explosion. Or did I miss something again? – Olympie

I think @Chuchuah is correct and this answer is wrong. The problem does not decompose this easily, because once you choose certain boxes to form the "base", the set of available boxes changes. So the N(w,b) function is nearly useless, as it only applies when you are choosing the very first box on the bottom... Unless you can repeat boxes, which as the question suggests you clearly cannot – Lynsey

@Nemo: You're right Nemo. I'm also afraid that it isn't that easy as it was suggested by tskuzzy. – Expropriate