10

我对一种算法有疑问。

给定 n 个盒子，每个盒子都有固定的重量和强度（均以 kg 为单位）。Box的强度告诉我们它可以承受的最大重量是多少。我们必须形成最高的一堆给定的盒子（每个盒子都有相同的高度）。您应该提出一种算法，该算法将始终给出最佳解决方案，即 k 个框的最长序列 (k <= n)。

好吧，这是我已经想出的解决方案：

  1. 首先，我们按重量对所有盒子进行分类（最重的在底部）并形成一堆。
  2. 其次，我们按强度对那堆进行排序（最强的在底部）。
  3. 然后，对于每个盒子，从底部开始，只要它的强度允许，我们尝试将其拉到底部。
  4. 最后，我们必须弄清楚必须从顶部移除多少个盒子，这导致下面的一些盒子承载的重量比它们所能承受的重得多。

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

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

4

3 回答 3

3

如果没有更聪明的答案，我会尝试分支和绑定，从下到上建造塔。给定一个部分建造的塔，您可以限制已完成塔的高度。如果部分建造的塔可以承受 X 的额外重量，您可以计算出在额外重量超过 X 之前您可以添加多少个盒子 - 只需按照重量增加的顺序挑选剩余的盒子，忽略它们的强度。如果有零重量的盒子，在预处理阶段将它们放在一边，稍后再将它们推到顶部。一个不太准确的界限是 X 除以最轻的未使用盒子的重量。

给定这样的界限，使用回溯搜索来构建你的塔，丢弃所有不可能扩展以产生比目前找到的最佳答案更高的塔的部分答案。

于 2011-08-11T20:07:32.937 回答
0

这是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/>");
}
于 2011-08-11T17:14:04.357 回答
0

您可以使用动态编程解决此问题。

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

于 2011-08-11T17:35:50.070 回答