•  09-10-2019
  •  | 
  •  

Frage

Ich möchte ein kleines Hilfsprogramm schreiben, um meine digitalisierten Hörbüchern Sammlung zu organisieren.

Ich habe eine Reihe von Ordnern, die ich brauche, um CDs zu schreiben. Die Ordner können nicht geteilt werden. Jeder Ordner auf einer Festplatte geht

Ich mag die Scheiben am effizientesten füllen:

  1. Minimieren Sie die Anzahl der Platten, und
  2. Die Anzahl der Scheiben gleich ist, maximiert die Lagerung zur Verfügung der am wenigsten gefüllten Scheibe (80 + 20 verbleibende Platz ist besser als 50 + 50).

Welche Algorithmus soll ich verwenden?

War es hilfreich?

Lösung

Das nennt man den Bin Packing Problem und NP-schwer ist, so gibt es keine einfacher Algorithmus, es zu lösen.

Die Lösung fand ich am besten funktioniert (ich einen Programmierwettbewerb mit einer Frage lief fast identisch mit diesem), war die Ordner nach Größe zu bestellen und die größten Ordner setzen, dass nach wie vor paßt auf die Scheibe, bis sie voll ist oder alle verbleibenden Ordner zu groß ist, in dem verbleibenden Raum zu passen.

Das löst das Problem schnell, da nach der Art des Rest des Algorithmus ist O (n).

Im Wettbewerb lief ich, dies in 74 Scheiben in Folge statt der 79, dass eine naive Lösung für unseren größten Testdatensatz erreichen würde.

Andere Tipps

Wenn Sie möchten, Dateien packen / Ordner auf eine CD-R Scheibe, als Sie diese optimal in pseudo-polynominal Zeit tun könnten. Um dies zu tun, müssen Sie rund Größen von Dateien / Ordner in Sektoren und zählen Sektoren auf der CD-R.

Danach erhalten wir diskrete 1-D Tornister Packungsproblem , die schön dynamische Programmierung verwendet wird, mit Komplexität gelöst werden können O (n)

Um genauer zu sein:

  • O (n) = O (nW) , Ursache W ist konstant in Ihrem Fall - W Anzahl der Sektoren auf CD R.
  • n Anzahl der Dateien / Ordner.

Für eine bessere Leistung kann man immer über-ungefähre Größe von Sektoren, beispielsweise Setup:

  • Über angenähert Sektorgröße 70k
  • was macht 700M / 70k = 10k alle Sektoren auf CD-R
  • , die in Sekunden, wenn Menge Dateien kleiner als (1G / 10k = 100 k) 100k berechnen sollten - n <100'000
  • in Minuten, wenn n <10'000'000

Was ist mehr:

  • kann Lösung schön parallel geschaltet werden.

Vielleicht diesen Algorithmus in gierige Weise die Anwendung „ein CD-Paket, das nächste CD-Paket“ wird die Arbeit tun?

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top