CD optimal füllen: Wie sollte Algorithmus aussehen?
-
Hallo!
Ich habe ein allgemeines Optimierungsproblem und würde gerne erfahren, wie ihr das lösen würdet.
Es geht um folgendes:
Ich habe z.B. eine CD mit 700MB Kapazität und würde diese gerne optimal mit Dateien unterschiedlicher Größe füllen.Also mal angenommen ich habe 4 Dateien: 200MB, 450MB, 300MB, 400MB.
Wenn man alle möglichen Kombinationen durchgehen würde, also:200+450+300+400
200+300+400+450
etc. würde man auf 24 Möglichkeiten kommen, die man theoretisch durchgehen müßte.
Wie packt man dieses Problem am besten an, so das man schnellstmöglich auf das optimale Ergebnis 300+400 kommt? Da in der Praxis mit duzenden oder gar hunderten Dateien zu rechnen ist.Hat da jemand Vorschläge?
Danke!
Tsunami
-
prinzipiell ist dieses problem "gemein".
aber bei hunderten von dateien wirds leicht. dann nimmste einfach immer nur die dickste datei, solange, bis die cd voll ist. ich hab früher so disketten vollgemacht und das ergebnis war höchst zufriedenstellend.
-
volkards Lösung ist in der Praxis sicherlich die beste. Wenn du aber wirklich immer die optimale Verteilung haben willst, musst du prinzipiell alle möglichen Kombinationen durchgehen. Das kann man noch um einiges verkürzen, allerdings will ich nicht zu viel verraten, weil beim beim diesjährigen Bundeswettbewerb für Informatik eine ähnliche Aufgabenstellung dabei ist. Aber so viel sei gesagt: Sortiere die Dateigrößen und überlege, welche Kombinationen du nicht zu überprüfen brauchst.
-
So ein Programm gibts übrigens schon, ich weiß allerdings nicht, wie perfektionistisch es ist. Heißt Burn to the Brim und den Sourcecode gibts bei http://www.freewarenet.de/files/sourcecodes/bttb-2.9.0-src.zip
-
Also erst einmal danke für die ganzen Rückmeldungen!
Das im diesjährigen Bundeswettbewerb auch so eine Aufgabe gestellt wurde, wußte ich nicht. Wann ist der denn vorbei, damit man eventuell noch nähere Tips bekommt?
Hintergrund ist der, daß ich Burn to the Brim kenne und auch benutze. Allerdings möchte ich auf Linux migrieren und es gibt keine Linuxversion davon. Ich würde das Programm in C++ dann entwickeln, BttP ist allerdings in Pascal geschrieben und daher nicht so wirklich geeignet um da Codefragmente raus zu übernehmen.
-
Darf ich Euch vielleicht noch sagen, daß die Fehlerrate im Randbereich von CDRs und DVDRs nach kurzer Lagerung dramatisch zunimmt, und daher die maximale Befüllung keine gute Idee ist?
-
Uiuiui, der Datenträgerguru spricht
-
Marc++us: Hast du da irgendwelche Zahlen?
-
Tsunami schrieb:
Also erst einmal danke für die ganzen Rückmeldungen!
Das im diesjährigen Bundeswettbewerb auch so eine Aufgabe gestellt wurde, wußte ich nicht. Wann ist der denn vorbei, damit man eventuell noch nähere Tips bekommt?
Hintergrund ist der, daß ich Burn to the Brim kenne und auch benutze. Allerdings möchte ich auf Linux migrieren und es gibt keine Linuxversion davon. Ich würde das Programm in C++ dann entwickeln, BttP ist allerdings in Pascal geschrieben und daher nicht so wirklich geeignet um da Codefragmente raus zu übernehmen.
Pascal und C++ ähneln sich eigentlich ziemlich, bis das Pascal keine OOP kennt. Die Typen sind alle gleich, es gibt keine großen Unterschiede.
-
Michael E. schrieb:
Marc++us: Hast du da irgendwelche Zahlen?
Keine, die ich nicht selbst gefälscht habe.
Da muß ich Dich auf öffentliche Quellen verweisen, z.B. c't.
Kleiner Exkurs (sorry for OT):
Du kannst es Dir aber auch ganz anschaulich vorstellen, zwei Gründe verursachen dies:
a) Geometrie - das ist eine Scheibe, die hängt nach Außen durch, wird aber gleichzeitig vom Lack nach oben gezogen, daher ist sie am Außenrand auch welliger, jetzt dreht man das, folglich "wabbert" die Kante in der Höhe einfach mehr, und dadurch bekommt man stärkere Signalschwankungen. Daß sich dies sofort als höhere Fehlerrate auswirkt ist naheliegend, das muß so sein.
b) Herstellung - da man alle Schichten über Spinningverfahren aufbringt (man kippt etwas in die Mitte und schleudert es dann über die Seite ab), sind diese am Rand dünner und weniger homogen als in der Mitte. Auch das Metall nimmt in der Dicke am Rand ab, da es gemäß einer Gaußverteilung aufgebracht wird. Daher sind alle Schichten am Rand empfindlicher, näher an ihren Limits, gleichzeitig ist dort aber die Nähe zum eindringenden Sauerstoff am geringsten, wodurch die Schichten stärker strapaziert werden.
Das ganze ist bei DVDR (egal ob + oder -) natürlich noch dramatischer als bei CDR, da die Strukturen kleiner sind.
-
DEvent schrieb:
Pascal und C++ ähneln sich eigentlich ziemlich, bis das Pascal keine OOP kennt. Die Typen sind alle gleich, es gibt keine großen Unterschiede.
Dann werde ich mir den Source wohl genauer angucken müssen, obwohl mir eine Eigenentwicklung am liebsten wäre, da am besten zu warten.
Mein größtes Problem ist der Algorithmus mit dem man alle möglichen Kombinationen erstellen läßt. Da weiß ich noch nicht so richtig, wie ich das machen soll
Edit:
Burn to the Brim ist übrigens in Delphi geschrieben, hatte ich falsch in Erinnerung.
-
Alle möglichen Kombinationen ist ganz einfach. Entweder ist eine Datei in der Kombination drin oder nicht. D. h. es gibt bei n Dateien 2^n verschiedene Möglichkeiten. Die kannst du einfach durch eine Zählvariable darstellen.
Beispiel für n = 8:
Zählvariable Kombination 0000 0001 achte Datei 0000 0010 siebte Datei 0000 0011 siebte und achte Datei 0000 0100 sechste Datei ...
-
Danke für den Tip. Das ist natürlich ein neuer Denkansatz das alles als binären Zahlenstrahl abzulegen. Dann müßte ich mir nur noch einen Weg überlegen, wie ich den am besten manipuliere, damit auch wirklich alle Möglichkeiten abgegriffen werden.
Das Auswerten ist ja mit dieser Technik kein Problem mehr
-
Tsunami schrieb:
Dann müßte ich mir nur noch einen Weg überlegen, wie ich den am besten manipuliere, damit auch wirklich alle Möglichkeiten abgegriffen werden.
Es werden doch alle durchgegangen
-
Michael E. schrieb:
Es werden doch alle durchgegangen
Damit meinte ich eigentlich auch den Algorithmus, der den String verändert. Es könnte ja passieren, wenn man nicht genau aufpaßt und testet, daß man durch einen Fehler unbeabsichtigt Lücken reißt.
Aber die Idee mit dem Zahlenstrahl gefällt mir wirklich gut, danke nochmal für den Tip!
-
deine aufgabe kannst du mit dem simplex-algorithmus lösen.
grüße mm
-
Den Simplex-Algorithmus kenne ich auch, müßte man wirklich mal ausprobieren ob man damit auf Anhieb die optimale Lösung finden würde.
Wobei bei vielen Daten das Tableau sehr groß werden würde, muß ich einfach mal testen. Mache ich morgen.
-
da würd ich aber aufpassen, die Optimierungssoftware von Heute greift auf modifizierte Simplex- oder gänzlich andere schlaue Algorithmen zurück. Du könntest unter Umständen doch recht lange warten wenn du das selbst baust, wobei dein Problem ja eher winzig ist.
Aber der erste Schritt ist dann wohl das Aufstellen eines Linearen Optimierungsproblems, wenn ich mich nicht verschaut habe kann man das sogar als 0-1 LOP formulieren.
tt
-
Wie kann man denn hier das Simplex-Verfahren anwenden?
-
mezzo mix schrieb:
deine aufgabe kannst du mit dem simplex-algorithmus lösen.
eher nicht.
allenfalls infofern, daß man sogar mit einem klavier primzahlen berechnen kann, wenn man ein wenig frickelt.
-
volkard schrieb:
mezzo mix schrieb:
deine aufgabe kannst du mit dem simplex-algorithmus lösen.
eher nicht.
allenfalls infofern, daß man sogar mit einem klavier primzahlen berechnen kann, wenn man ein wenig frickelt.falls du darauf hinaus willst, daß ich "simplex-" anstatt "dualer simplex-algorithmus" geschrieben hab...
ansonsten erleuchte mich!