Überblick
Jeff Shattocks Antwort ist richtig, dass dies einem kombinatorischen Optimierungsproblem entspricht (oder isomorph, wie es Mathematiker schreiben), aber es entspricht dem 1-dimensionalen Bin-Pack-Problem, nicht dem Rucksack-Problem .
Zum Glück habe ich etwas Code, den Sie teilen können, um dieses Problem für Sie oder andere Personen zu lösen, die Zugriff auf einen Windows-Computer haben, auf dem mindestens die Version 3.5 von .NET Framework installiert ist.
Eine grobe Lösung
Laden Sie zunächst LINQPad herunter und installieren Sie es .
Zweitens laden Sie die gerade geschriebene LINQPad-Abfrage herunter - hier ist der Linq (ha) der Rohdatei. Speichern Sie es als .linq- Datei und öffnen Sie es in LINQPad.
Ändern Sie die Parameter:
Hier ist der Teil im LINQPad-Abfragecode, den Sie ändern sollten:
int binSizeMb = 4476; // This is the (floor of the) total size of a DVD+R reported by CDBurnerXP. string rootFileFolderPath = @"F:\2006 - Polyester Pimpstrap Intergalactic Extravaganza multicam";
Ändern Sie binSizeMbdie Größe Ihrer "Ablage", z. B. CD, DVD, z. int binSizeMb = 650;für eine CD.
Hinweis - Der binSizeMbWert wird als das interpretiert, was manchmal als Mebibyte bezeichnet wird . Im Gegensatz zu meiner Kindheit, wenn alle Byte-Multiples "binär" waren, bezieht sich "MB" manchmal auf ein dezimales Megabyte oder genau 1.000.000 Byte, im Gegensatz zu den 1.048.576 Byte eines Mebibytes (MiB), das in meinem Code verwendet wird . Wenn Sie dies ändern möchten, ändern Sie die Zeile const int bytesPerMb = 1048576;im Code in const int bytesPerMb = 1000000;.
Wechseln Sie rootFileFolderPathzum vollständigen Pfad des Ordners, der die Dateien enthält, die Sie in Ablagen packen möchten, z. string rootFileFolderPath = @"C:\MySecretBinFilesFolder";.
Führen Sie die Abfrage aus, indem Sie entweder oben links auf der Registerkarte "Abfrage" F5auf die Schaltfläche Ausführen klicken oder darauf klicken .
Ergebnisse
Der Abfragecode listet alle Dateien im rootFileFolderPathOrdner rekursiv auf, das heißt, er enthält auch Dateien in allen Unterordnern.
Dann werden 'Bins' für die Dateien erstellt, so dass die Gesamtgröße aller Dateien in jedem Bin kleiner oder gleich der angegebenen Bin-Größe ist.
Im LINQPad-Ergebnisbereich sehen Sie zwei Listen.
Die erste Liste enthält alle gefundenen Dateien. Sie werden in absteigender Reihenfolge nach Größe aufgelistet.
Die zweite Liste enthält die durch "Packen der Dateien" erstellten Ablagen mit einer Liste der Dateien und deren Größe sowie der verbleibenden Größe der Ablage.
Hier ist ein Screenshot mit der zweiten Liste und den ersten beiden erstellten Behältern:
Cursor-Analyse
Laut Wikipedia sollte der von mir verwendete Algorithmus - die First Fit Decreasing (FFD) -Strategie - nicht zu schlecht sein; Wikipedia sagt:
Im Jahr 2007 wurde bewiesen, dass der gebundene 11/9 OPT + 6/9 für FFD eng ist.
„OPT“ bezieht sich auf die optimale Strategie (als etwas Unerreichbares, nicht als bestimmte Strategie).
Aufgrund meiner etwas unscharfen Erinnerungen an die mathematischen Ausdrücke sollte dies bedeuten, dass die FFD-Strategie im schlechtesten Fall die ~ 1,22-fache Anzahl von Behältern in eine optimale Strategie packen sollte. Daher könnte diese Strategie die Artikel in fünf anstelle von vier Fächern einpacken. Ich vermute, dass die Leistung wahrscheinlich sehr nahe am Optimum liegt, außer bei bestimmten pathologischen Artikelgrößen.
Der gleiche Wikipedia-Artikel besagt auch, dass es einen "exakten Algorithmus" gibt . Ich kann beschließen, das auch zu implementieren. Ich muss zuerst den Artikel lesen, der den Algorithmus beschreibt.