10

1 つのアルゴリズムに問題があります。

n 個の箱が与えられ、それぞれの箱の重量と強度は固定されています (どちらも kg で与えられます)。ボックスの強度は、ボックスが耐えられる最大重量を示しています。与えられたボックスの最大の山を形成する必要があります (それぞれのボックスの高さは同じです)。k 個のボックス (k <= n) の最長シーケンスである最適解を常に与えるアルゴリズムを提案する必要があります。

まあ、それは私がすでに考え出した解決策です：

  1. まず、すべての箱を重さで分類し (最も重いものを一番下に置きます)、それらの山を形成します。
  2. 次に、その山を強さで分類します (最も強いものが一番下になります)。
  3. 次に、各ボックスについて、底から始めて、その強度が可能な限り、底まで引き下げようとします。
  4. 最終的に、上からいくつの箱を取り除かなければならないかを計算する必要があります。これにより、下にあるいくつかの箱が、本来の重量よりもはるかに重いものを運ぶという状況が発生します。

このアルゴリズムは非常にうまく機能しているように見えますが、常に最適な解が得られるかどうかはわかりません。おそらくそうではないでしょう。ナップザック問題の解法に似た動的解法について疑問に思っていましたが、この方法で解けるかどうか確信が持てません。私の問題に最適な下部構造はないようです。

よろしくお願いします。:)

4

3 に答える 3

3

より賢明な答えのデフォルトでは、私は分岐してバインドし、塔を下から上に構築します。部分的に建設された塔がある場合、完成した塔の高さに制限を設けることができます。部分的に組み立てられたタワーが X の余分な重量に耐えることができる場合、余分な重量が X を超える前に追加できるボックスの数を計算できます。残りのボックスを、強度を無視して、重量が増加する順に選択します。重量がゼロの箱がある場合は、前処理段階でそれらを脇に置き、後で上に押し込みます。X を未使用の最軽量の箱の重量で割った値を、精度の低い境界とします。

このような境界が与えられたら、バックトラッキング検索を使用してタワーを構築し、これまでに見つかった最良の回答よりも高いタワーを生成するために拡張できなかった部分的な回答をすべて破棄します。

于 2011-08-11T20:07:32.937 に答える
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 に答える
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 に答える