Algorithmus zur besten Kombination von Zahlen zu finden - Bin Packing Prob lem

Question

sagen, dass ich die folgenden Maßnahmen haben:

ich jede Kombination von Zahlen speichern kann bis zu 480 pro Einheit. Wie kann ich die Mindestanzahl an Einheiten berechnen, die erforderlich sind, damit alle Maßnahmen möglichst effizient verteilt werden?

Ich habe PHP markiert, aber es kann auch in JS sein, oder sogar Pseudo-Sprache.

Ich weiß, dass ich sagen soll, was ich schon gemacht habe, aber ich bin ziemlich fest, wie ich das angehen soll. Die erste Sache, die in den Sinn kommt, ist Rekursion, aber ich bin kein Mathe-Experte, um zu sehen, wie dies effizient getan werden kann ...

Jede Hilfe wird sehr geschätzt.

Um weiter zu erarbeiten: Ich versuche die Anzahl der Sockelleisten zu berechnen, die ich bestellen muss, basierend auf den verschiedenen Längen, die ich für die Wände brauche. Jede Leiste hat eine Länge von 480cm und ich möchte wissen, wie ich sie am besten verteilen kann. Ich muss also die wenigsten Sockelleisten kaufen. Es ist nicht so viel über einen Sockel zusätzliche Bestellung, aber das Puzzle es heraus ist interessant (zumindest für mich)

Aktualisierung mit Lösung

Trotz Menschen, die versuchten, die Frage, die ich habe zu schließen begann mit dem Bin Hantieren Problembeschreibung Verpackung und im Anschluss an die Vorstellung alle Elemente vom größten zum kleinsten sortieren und sie dann auf die bestmögliche Art und Weise fit ich diese kleine Klasse erstellt, die andere in der Zukunft helfen könnten:

<?php 
class BinPacker { 
    private $binSize; 

    public function __construct($binSize) { 
     $this->binSize = $binSize; 
    } 

    public function pack($elements) { 
     arsort($elements); 
     $bins = []; 
     $handled = []; 

     while(count($handled) < count($elements)) { 
      $bin = []; 

      foreach($elements as $label => $size) { 
       if(!in_array($label, $handled)) { 
        if(array_sum($bin) + $size < $this->binSize) { 
         $bin[$label] = $size; 
         $handled[] = $label; 
        } 
       } 
      } 

      $bins[] = $bin; 
     } 

     return $bins; 
    } 

    public function getMeta($bins) { 
     $meta = [ 
      'totalValue' => 0, 
      'totalWaste' => 0, 
      'totalBins' => count($bins), 
      'efficiency' => 0, 
      'valuePerBin' => [], 
      'wastePerBin' => [] 
     ]; 

     foreach($bins as $bin) { 
      $value = array_sum($bin); 
      $binWaste = $this->binSize - $value; 

      $meta['totalValue'] += $value; 
      $meta['totalWaste'] += $binWaste; 
      $meta['wastePerBin'][] = $binWaste; 
      $meta['valuePerBin'][] = $value; 

     } 

     $meta['efficiency'] = round((1 - $meta['totalWaste']/$meta['totalValue']) * 100, 3); 

     return $meta; 
    } 
} 

$test = [ 
    'Wall A' => 420, 
    'Wall B' => 120, 
    'Wall C' => 80, 
    'Wall D' => 114, 
    'Wall E' => 375, 
    'Wall F' => 90 
]; 

$binPacker = new BinPacker(488); 
$bins = $binPacker->pack($test); 

echo '<h2>Meta:</h2>'; 
var_dump($binPacker->getMeta($bins)); 

echo '<h2>Bin Configuration</h2>'; 
var_dump($bins); 

Welche gibt eine Ausgabe:

Meta: 

array (size=6) 
    'totalValue' => int 1199 
    'totalWaste' => int 265 
    'totalBins' => int 3 
    'efficiency' => float 77.898 
    'valuePerBin' => 
    array (size=3) 
     0 => int 420 
     1 => int 465 
     2 => int 314 
    'wastePerBin' => 
    array (size=3) 
     0 => int 68 
     1 => int 23 
     2 => int 174 

Bin Configuration 

array (size=3) 
    0 => 
    array (size=1) 
     'Wall A' => int 420 
    1 => 
    array (size=2) 
     'Wall E' => int 375 
     'Wall F' => int 90 
    2 => 
    array (size=3) 
     'Wall B' => int 120 
     'Wall D' => int 114 
     'Wall C' => int 80 

Während der Datensatz relativ klein ist, wird eine ziemlich hohe Ineffizienzrate erreicht. Aber in meiner eigenen Konfiguration, in der ich alle Wand- und Deckenmaße eingegeben habe, habe ich einen Wirkungsgrad von 94.212% erreicht (n = 129 Takte).

(Hinweis: Die Klasse sucht nicht nach mehrdeutige Etiketten, so dass, wenn Sie zum Beispiel Wall A definieren zweimal das Ergebnis falsch sein.)

Fazit: sowohl für die Decke und die Wand Fußleisten ich eine Bestellung kann weniger als mein manueller Versuch, sie effizient zu verbreiten.

Answer 1

Sieht für mich wie eine Variante der Bin Packing Problem, wo Sie versuchen, die Kombination von Elementen, die 480 (oder knapp) bilden. Dies ist ein ziemlich rechenintensives Problem und je nachdem, wie effizient/genau es sein muss, könnte es zu viel Aufwand sein, es genau zu bekommen.

Eine grobe Heuristik könnte nur sein, die Maße zu sortieren, fügen Sie die kleinsten in eine Einheit ein, bis die nächste Sie zum Übergehen bringt, dann zu einer neuen Einheit hinzufügen und wiederholen.