Оптимальное решение для создания кучи коробок - PullRequest
Новая
       12

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

10 голосов
/ 11 августа 2011

У меня проблема с одним алгоритмом.

Имеется n ящиков, каждый из которых имеет фиксированный вес и силу (оба даны в кг). Сила коробки говорит нам, какой максимальный вес она может выдержать. Мы должны сформировать самую высокую кучу из заданных ящиков (каждая из них имеет одинаковую высоту). Вы должны предложить алгоритм, который всегда даст оптимальное решение, которое является самой длинной последовательностью из k блоков (k <= n). </p>

Ну, это решение, которое я уже нашел:

  1. Во-первых, мы сортируем все коробки по весу (самые тяжелые идут снизу) и формируем их кучу.
  2. Во-вторых, мы сортируем эту кучу по силе (самая сильная идет внизу).
  3. Затем для каждого ящика, начиная с дна, мы стараемся опустить его вниз, если это позволяет его сила.
  4. В конце концов, мы должны выяснить, сколько ящиков нужно снять сверху, что приводит к тому, что некоторые ящики ниже несут гораздо больший вес, чем могли бы.

Кажется, что этот алгоритм работает довольно хорошо, но я не уверен, дает ли он всегда оптимальное решение - возможно, нет. Мне было интересно узнать о динамическом решении, аналогичном решению проблемы с рюкзаком, но я не уверен, что это можно решить таким образом. На мой взгляд, нет оптимальной подструктуры для моей проблемы.

Заранее спасибо за любую помощь. :)

Ответы [ 3 ]

3 голосов
/ 12 августа 2011

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

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

0 голосов
/ 11 августа 2011

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

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

0 голосов
/ 11 августа 2011

Вот алгоритм в 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/>");
}
...