创建一堆盒子的最佳解决方案

Question

我有一个算法的问题.

给出n个盒子,每个盒子具有固定的重量和强度(均以kg给出).Box的力量告诉我们它能承受的最大重量是多少.我们必须形成最高堆的给定盒子(每个盒子具有相同的高度).您应该提出一种始终给出最优解的算法,这是k盒的最长序列(k <= n).

嗯,这是我已经想到的解决方案:

1. 首先,我们按重量对所有箱子进行分类(最重的是在底部)并形成一堆.
2. 其次,我们按强度排序(最强的是在底部).
3. 然后,对于每个盒子,从底部开始,我们尝试将其拉到底部,只要它的强度能够实现.
4. 最后,我们必须弄清楚必须从顶部移除多少箱子,这导致下面的某些箱子承载的重量超过他们的重量.

看起来这个算法工作得很好,但我不确定它是否总是给出最优解 - 可能它没有.我一直在想动态解决方案,类似于背包问题的解决方案,但我不确定它是否可以通过这种方式解决.对于我的问题,似乎没有最佳的子结构.

预先感谢您的任何帮助.:)

Answer 1

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