アルゴリズム - ビンパッキング、ビンを配置してn個のオブジェクトをパックする

ここには書籍 "Algorithm Design Manual"の消費品があります。アルゴリズム - ビンパッキング、ビンを配置してn個のオブジェクトをパックする

ビンパッキングの問題では、それぞれが0kgと1kgの間の重量のn個の金属オブジェクトが与えられます。私たちの目標は、n個のオブジェクトを保持するビンの最小数を見つけることです。各ビンは最大1キログラムを保持します。

ビンパッキングのヒューリスティックは、次のとおりです。オブジェクトが与えられた順番であると考えてください。オブジェクトを挿入した後に、ルームの最小量の部分的に塗りつぶされたビンにを置きます。です。そのようなビンが存在しない場合は、新しいビンを開始してください。 O（nlogn）時間に、最良適合ヒューリスティック（n個の重みw1、w2、...、wnを入力として使用し、使用bin数をとして出力）を実装するアルゴリズムを設計します。

[OK]を、この切手は難しくないようです。私の最初の理解は、ベストフィットヒューリスティックアプローチでは、私はたびに空き容量が最小のビンを探し、オブジェクトを入れようとします。オブジェクトが最小のスペースでビンに収まらない場合は、ビン。

私はビンを保管するためのBSTを構築することができます。オブジェクトをビンに入れるたびに、そのビンをツリーから削除し、ビンの使用可能なスペースを更新してビンをツリーに再挿入できます。これは、すべてのオブジェクト配置のO（logN）をメインにします。

はしかし、私は、「オブジェクトが挿入された後、余分な部屋の最小量を部分的に満たされたビンに置き、各オブジェクトについて」消費税のボールドとイタリックの部分に気づきました。

これは、空き容量が最小のビンを探しているのではなく、現在のオブジェクトを配置すると、オブジェクトを配置した後に得られる空き領域が最小になるようなものを探しています。

たとえば、bin1の現在のスペースが0.5の場合、bin2は0.7です。現在、bin1は最小です。しかし、現在のオブジェクトが0.6の場合、新しいビンを作成するのではなく、ビン1にオブジェクトを配置することはできません。ビン2を見つけてビン2 - オブジェクト= 0.7 - 0.5 = 0.2としてオブジェクトを配置する必要があります。

私は正しいですか？声明の大胆な部分は、私が思ったように本当に意味がありますか？あるいは、「最小のスペースを持つビンを見つけたら、オブジェクトを置くことができたら、ビンを見つけたら、ビンを見つける」と同じくらい簡単ですか？

おかげ

編集：太字部分の私の新しい理解のための私のJavaコードの一部を追加します。

あなたがスペースを残りの順にソートビンのソートされた配列（というか赤黒木のようなソートされたバイナリツリー）を保持し、それぞれの新しい重量のために空きスペースのベストフィットでビンを見つける必要がある

public void arrangeBin(float[] w) { 
    BST bst = new BST(); 
    bst.root = new Node(); 

    int binCount = 0; 
    for (int i = 0;i < w.length;i++) { 
     float weight = w[i]; 
     Node node = bst.root; 
     float minDiff = 1; 
     Node minNode = null; 
     while(node!=null) { 
     if (node.space > weight) { 
      float diff = node.space - weight; 
      if (minDiff > diff) { 
       minDiff = diff; 
       minNode = node; 
       node = node.left; 
      } 
     } 
     else 
      node = node.right; 
     } 
     if (minNode == null) { 
     binCount++; 
     Node node = new Node(); 
     node.space -= weight; 
     bst.insert(node); 
     } 
     else { 
     minNode.space -= weight; 
     bst.delete(minNode); 
     bst.insert(minNode); 
     } 
    } 
}

出典

2012-03-27 Jackson Tale

実行時間がO（N2）になります。あなたがO（nlogn）を達成したいなら、あなたは私の答えで提案したようなものを使うべきです。それ以外は正しいように見えます。 – WeaselFox

@ WedelFox、私はbstを維持した –