Nehmen wir an, ich habe 7 kleine Behälter, jeder Behälter hat die folgende Anzahl an Murmeln:
%Vor%Ich weise diese kleinen Behälter zwei großen Behältern zu, die jeweils die folgende maximale Kapazität haben:
%Vor%Ich möchte JEDE Kombination finden, wie die kleinen Behälter über die großen Behälter verteilt werden können, ohne die Kapazität zu überschreiten (z. B. kleine Behälter Nr. 4, Nr. 5 im großen Behälter Nr. 2, der Rest in Nr. 1).
Einschränkungen:
Dieses Problem ist in O (n ^ m) O (2 ^ n) -Zeit (siehe unten) leicht zu lösen: versuchen Sie einfach jede Kombination und speichern Sie die Lösung, wenn die Kapazität nicht überschritten wird. Ich hätte gerne etwas schneller, das mit einer variablen Anzahl von Behältern umgehen kann. Mit welchem obskuren Graphentheorie-Algorithmus kann ich den Suchraum verkleinern?
Hier ist mein umständlicher rekursiver Versuch, Duplikate zu vermeiden und zu früh aus zu großen Summen zu beenden. Die Funktion geht davon aus, dass doppelte Elemente sowie die Behältergrößen in der Eingabe gruppiert und gezählt werden. Statt jedes Element in jedes Fach zu platzieren, wird jedes Element in nur einem von zwei Bins platziert; und jedes Element mit Duplikaten wird deutlich partitioniert.
Zum Beispiel erscheint in meinen Ergebnissen die Kombination [[[1,10,20]],[[4,5,10,30]]] einmal; während im SAS-Beispiel in Leos Antwort zweimal: einmal als IN[1]={1,3,4} IN[2]={2,5,6,7} und wieder als IN[1]={1,4,7} IN[2]={2,3,5,6} .
Kann jedoch nicht für Effizienz oder Laufruhe bürgen, da es kaum getestet wird. Vielleicht könnte das Stapeln der Aufrufe anstelle von Rekursionen den Browser leichter belasten.
JavaScript-Code:
%Vor%Ausgabe:
%Vor%Hier ist eine zweite, einfachere Version, die nur versucht, den Thread zu beenden, wenn ein Element nicht platziert werden kann:
%Vor%Ausgabe:
%Vor%Dieses Problem wird oft genug gesehen, dass die meisten Constraint Logic Programming-Systeme ein Prädikat enthalten, um es explizit zu modellieren. In OPTMODEL und CLP nennen wir es pack :
%Vor%Dieser Code produziert alle Lösungen in 0,06 Sekunden auf meinem Laptop:
%Vor%Ändern Sie einfach die ersten drei Zeilen für andere Instanzen. Wie jedoch bereits erwähnt wurde, ist dieses Problem NP-Hard. So kann es plötzlich von sehr schnell zu sehr langsam wechseln. Sie können auch die Version lösen, bei der nicht jeder kleine Artikel einem großen Behälter zugewiesen werden muss, indem Sie einen großen Dummy-Behälter mit ausreichender Kapazität für die gesamte Sammlung kleiner Artikel erstellen.
Wie Sie dem Abschnitt "Details" im Handbuch entnehmen können, sind die Algorithmen, die praktische Probleme schnell lösen, nicht einfach und ihre Implementierungsdetails machen einen großen Unterschied. Mir sind keine CLP-Bibliotheken bekannt, die in Javascript geschrieben wurden. Am besten ist es, wenn Sie CLP in einen Webdienst einbinden und diesen Dienst über Ihren JavaScript-Code aufrufen.
Tags und Links javascript algorithm math graph-theory mathematical-optimization