Ich muss eine Anwendung schreiben, die eine Liste von Dateien (einige große, einige kleine) aufnimmt und sie so effizient wie möglich auf DVDs (oder CDs oder was auch immer) anordnet. Der Hauptpunkt dieser Anwendung besteht darin, soviel von der ersten Scheibe zu verbrauchen, bevor man auf die zweite Scheibe geht, die zweite Scheibe so weit wie möglich aufzufüllen, bevor man auf die dritte Scheibe etc. geht.
(Hinweis: Die Anwendung muss nicht das eigentliche Brennen auf der DVD machen, es muss nur die bestmögliche Anpassung herausfinden).
Ich dachte zuerst, ich hätte einen guten Spielplan, indem ich eine Permutation der Dateien erzeuge und dann jede Kombination überprüfe, um zu sehen, was am besten passt. (Meine Bitte um Hilfe dazu finden Sie HIER )
Aber je mehr Dateien es gibt, desto länger dauert es ... exponentiell. Daher wollte ich einige Ihrer Meinungen darüber, wie Sie das am besten erreichen können.
Irgendwelche Ideen? Und wie immer wird C # -Code immer geschätzt.
Einfacher Algorithmus:
Was Ihnen bevorsteht, hängt mit dem Rucksackproblem zusammen. Die verlinkte Wikipedia-Seite enthält viele weitere Informationen, einschließlich Lösungsvorschläge.
Für alle, die noch an dieser Frage interessiert sind ... Ich schrieb ein Dienstprogramm, das ich für einen ähnlichen Zweck der Anpassung von Dateien in eine Reihe von Disks / Discs verwendet. Es verwendet eine Befehlszeilen- / dateibasierte Schnittstelle. Versionen sind in C, C ++ und & amp; Java (nicht C #).
Weitere Informationen finden Sie in der Datei diskfit.tgz: Doc / diskfit.txt.
(AGPL3)
Wir könnten die Frage als 0-1-Multi-Rucksack charakterisieren, oder lineare Behälterverpackung. (Danke Jon-Skeet für den Link über Rucksack Problem.)
Dthorpe löst lineare Bin Packing, für genau genug Bins / Festplatten passend alle Dateien [schön O (n) oder O (n lg n) schnell - auch in Tabellenkalkulation ohne ein Skript schreiben müssen].
Grundsätzlich gibt diskfit (oben verlinktes Dienstprogramm) qualifizierte Dateisätze aus basierend auf 0-1 Single-Rucksack, und der Benutzer wählt Dateisets für eine Festplatte aus, die in den Festplattensatz assembliert werden sollen. Unterstützung des Benutzers (aber nicht vollständig automatisieren) für beide:
Vollständige programmatische Auswahl des kompletten Diskettensatzes, wäre ein zusätzliches Feature. Es wäre nicht ausreichend, 0-1 Single-Rucksack-Lösung anzuwenden, automatisch Disc für Disc [gierig]. (Betrachten Sie 3 Tornister mit Kapazität 6 und verfügbare Gegenstände mit gleichem Wert und Gewichte von: {1, 1, 2, 2, 3, 4, 5}. Die Anwendung von 0-1 Rucksack auf den ersten Rucksack isoliert würde wählen {1, 1, 2, 2}, um den Summenwert 4 zu erhalten - nach dem wir nicht alle passen können verbleibende 3 Gegenstände in der verbleibenden Sekunde & amp; dritte Rucksäcke - während wir wissen, dass wir alle Gegenstände in den 3 Rucksäcken als passen können {1, 2, 3} & amp; {1, 5} & amp; {2, 4}.)
Das ist zwar ein cooles Problem, das Sie in einem Programm für bestimmte Anwendungen lösen müssen ... aber in Ihrer Anwendung sollten Sie WinRAR oder ein anderes Archivierungsprogramm verwenden, das das Archiv in Dateibereiche mit bestimmten Größen aufteilen kann. Sie könnten jeden Chunk die Größe einer DVD machen und dann einfach wegbrennen.
BEARBEITEN: Ein Problem, das Sie bekommen könnten, ist, dass wenn Sie eine Datei größer als die Größe Ihrer Medien haben, Sie diese Datei nicht brennen können.
Wie wäre es, wenn Sie zunächst so viele der größten Dateien wie möglich auf eine DVD schreiben und dann so viele kleine Dateien wie möglich auffüllen (beginnend mit dem kleinsten).
Wiederholen Sie diesen Vorgang mit den verbleibenden Dateien für jede Festplatte.
Ich bin mir nicht sicher, ob es Ihnen eine perfekte Abdeckung / Verteilung geben wird, aber ich denke, es könnte einen Weg zur Lösung Ihrer Bedürfnisse bringen.
Verwenden Sie backtracking, um den optimalen Satz von Dateien auf DVD 1 zu brennen, schließen Sie sie dann aus der Liste aus und verwenden Sie backtracking für die restlichen Dateien, um die optimale Füllung für DVD 2 usw. zu erhalten.
Ich habe viele Tools gefunden, die dieses Problem lösen sollen, aber alle versuchen, die GESAMTE Anzahl der verwendeten CDs zu minimieren, während ich mich nur für die SINGLE-Untergruppe von Dateien interessierte, die am besten zu einer EINZEL-CD passen.
Also habe ich mein eigenes Tool mit dem Titel " ss " (von " Teilmengensumme "Algorithmus, der basiert auf). Das Tool ist immer noch fehlerhaft und kann keine Verzeichnisse wiederherstellen, aber es funktioniert für mich. :)
Dieses Problem ist das Problem beim Einpacken von Behältern und ist NP-vollständig, was bedeutet, dass Sie eine wirklich optimale Lösung benötigen brauchen exponentielle Zeit. Es gibt jedoch Methoden, die weniger als optimale Lösungen liefern, aber viel schneller laufen.
Nehmen wir an, wir haben eine unbegrenzte Liste von Festplatten. Nehmen Sie jede Datei absteigend in der Größe, und fügen Sie dann jede Datei auf die erste Festplatte, die es passt. Dies heißt First fit abnehmend und nimmt 11/9 OPT + 6/9 Festplatten im schlimmsten Fall. Wenn Sie Dateien in zufälliger Reihenfolge auswählen, benötigen Sie stattdessen 11/9 OPT + 1 Festplatten.
Es gibt Algorithmen, die die Dinge dichter packen, siehe oben den Wikipedia-Link für weitere Details.