Оптимальное решение для создания кучи ящиков

Ответ 1

В отличие от более умного ответа, я бы попробовал разветвление и привязку, построив башню снизу вверх. Учитывая частично построенную башню, вы можете установить границу на высоте завершенной башни. Если частично построенная башня может выдерживать дополнительный вес X, вы можете определить, сколько ящиков вы могли бы добавить до того, как дополнительный вес больше X - просто выберите оставшиеся боксы в порядке увеличения веса, игнорируя их силу. Если есть коробки с нулевым весом, отложите их на стадии предварительной обработки и засуньте их сверху. Менее точная граница будет равна X, деленная на вес самой легкой неиспользуемой коробки.

Учитывая такую ​​привязку, используйте поиск назад, чтобы построить свою башню, отбросив все частичные ответы, которые невозможно было продлить, чтобы создать более высокую башню, чем лучший ответ, найденный до сих пор.

Ответ 2

Вы можете решить эту проблему с помощью динамического программирования.

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

Обратите внимание, что для вычисления N(w,b) вы помещаете коробку b внизу. Затем вы вычисляете максимальное количество ящиков, которые вы можете положить поверх него. Ну, это легко сделать, если вы пройдете через возможные поля, которые можно разместить над ним.

У вас есть отношение повторения:

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

Ваш ответ следующий: max{ N(W,b) } где W=sum(weight[i]).

Ответ 3

Здесь алгоритм в 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/>");
}