algorithm - Bin-packing, arrangieren bins zu packen n objekte

Question

Hier ist eine Verbrauchssteuer aus dem Buch "Algorithm Design Manual".

Bei der Behälterverpackung haben wir n Metallobjekte mit einem Gewicht zwischen null und einem Kilogramm. Unser Ziel ist es, die kleinste Anzahl von Behältern zu finden, die die n Objekte aufnehmen, wobei jeder Behälter höchstens ein Kilogramm enthält.

Die Best-Fit-Heuristik für die Behälterverpackung ist wie folgt. Betrachten Sie die Objekte in der Reihenfolge, in der sie angegeben sind. Platzieren Sie für jedes Objekt es in den teilweise gefüllten Behälter mit der kleinsten zusätzlichen Menge Raum , nachdem das Objekt eingefügt wurde. Wenn kein solcher Behälter vorhanden ist, starten Sie einen neuen Behälter . Entwerfen Sie einen Algorithmus, der die Best-Fit-Heuristik implementiert (wobei die n Gewichte w1, w2, ..., wn als Eingabe verwendet werden und die Nummer der verwendeten Fächer ausgegeben wird) in O (nlogn) Zeit.

Ok, diese Verbrauchssteuer scheint nicht schwer. Mein erstes Verständnis ist, dass ich für den bestgeeigneten heuristischen Ansatz jedes Mal nach einem Bin mit minimalem verfügbaren Platz suche und versuche, das Objekt hineinzulegen. Wenn das Objekt nicht mit minimalem Platz in den Bin passt, erstelle ich ein neues Behälter.

Ich kann eine BST erstellen, um die Behälter zu speichern, und jedes Mal, wenn ein Objekt in einen Behälter gestellt wird, kann ich diesen Behälter aus dem Baum löschen, den verfügbaren Platz des Behälters aktualisieren und den Behälter wieder in den Baum einfügen. Dies wird O (logN) für jede Objektplatzierung sein.

Ich bemerkte jedoch den Fett- und Kursivteil der Verbrauchssteuer "Für jedes Objekt, platzieren Sie es in den teilweise gefüllten Behälter mit der kleinsten Menge an zusätzlichem Raum , nachdem das Objekt eingefügt wurde".

Das bedeutet, dass ich nicht nach einem Fach mit minimalem verfügbaren Platz suche, sondern nach einem, dass wenn ich das aktuelle Objekt einfüge, der resultierende verfügbare Platz (nach Platzierung des Objekts) minimal ist.

Wenn beispielsweise der aktuelle Speicherplatz von bin1 0,5 ist, ist bin2 0,7. Bin1 ist momentan das Minimum. Aber wenn das aktuelle Objekt 0.6 ist, dann kann das Objekt nicht in bin1 platziert werden, anstatt ein neues Bin zu erstellen, muss ich bin2 finden, um das Objekt als bin2 - object = 0.7 - 0.5 = 0.2 zu setzen, was dann minimal ist.

Bin ich richtig? Bedeutet der mutige Teil der Aussage wirklich, was ich dachte? Oder ist es so einfach wie "finde einen Behälter mit minimalem Platz, wenn das Objekt platziert werden kann, dann platziere; wenn nicht, dann erstelle einen neuen Behälter"?

Dank

Edit: Teil meines Java-Code für mein neues Verständnis des fettgedruckten Teils hinzuzufügen.

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); 
     } 
    } 
} 

Answer 1

Die kühne Aussage bedeutet wirklich, was Sie denken, dass es tut.

Die Idee wäre, den vollsten Behälter zu finden, in den das aktuelle Objekt passt, wodurch die Menge an verschwendete Fläche minimiert wird. Wenn das Objekt in keine Fächer passt, muss ein neuer Behälter erstellt werden

Answer 2

Sie benötigen ein sortiertes Array zu halten (oder eher eine sortierte binären Baum wie ein rot-schwarz-Baum) von Behältern durch verbleibende Raum sortiert und für jede neue Gewicht der Behälter mit den besten Sitz des leeren Raumes finden in ihm in O (log (n)), und wieder in den Baum einfügen auch in O (log (n)). Ihre Beobachtung scheint richtig - Sie müssen den Behälter finden, der am besten zu Ihrem neuen Gewicht passt. Hoffe das hilft.