@JonasR: Wieso war meines nicht massstabsgetreu? Du brauchst nur ein paar Verzeichnisse mit entsprechend grossen Dateien. Zum Beispiel Filme von Youtube, Datendateien von Spielen, oder verlustfrei komprimierte Musik, und es können mehr CDs heraus kommen als nötig wären.
@Brainsucker: Du könntest beide Werte gleich setzen. Wenn Dir das tatsächlich zu viel Speicher verbraucht, kannst Du den Speicherverbrauch der Matrix zwei mal halbieren. Einmal in dem Du den Algorithmus umschreibst, dass nur einer der beiden, dann ja gleichen Werte verwendet wird. Dann wird die Matrix symmetrisch, d.h. man muss nur noch die Hälfte davon tatsächlich speichern.
An Gleitpunktzahlen wirst Du das nicht anpassen können. Du kannst höchstens schauen wie weit Du die Einheit runter setzen kannst. Und ab wann das überhaupt noch Sinn macht. Ich denke eine Grössenordnung sollte man herunter gehen können, also die Grösseneinheit auf 100 KB setzen.
Suche 'erweiterte' Funktionen für Listen
Was später noch dazu kam sind die 800 Datein die aber in dem Falle egal sind.Brainsucker hat geschrieben:...Dateien mit unterschiedlichsten Größen (zwischen 6-14 MB)... Da handelsübliche CDs meißt auf 700 MB begrenz sind...
Es ist nämlich schon ein Unterschied ob ich Datein zwischen 2-3 MB auf 10 MB packen will oder 6-14 MB auf 700.
Zum Multiple Knapsack Problem sollte es eigentlich genug Approximationen mit garantierten Schranken geben. Ich würde mal behaupten, dass es, wie oben schon vorgeschlagen, ausreichen sollte die Dateien absteigend der Größe nach zu sortieren und dann immer auf die CD zu packen auf der noch am wenigsten Platz verfügbar ist. Wenn ich darauf tippen sollte, was der Worst Case wäre, dann würde ich darauf tippen, dass maximal doppelt so viele CDs verwendet werden würden wie durch das Optimum möglich. Ob das bei nicht-künstlichen Daten eintritt würde ich aber bezweifeln.
Das Leben ist wie ein Tennisball.
Also gehen wir mal davon aus alle Files sind 13 MB groß damit wir immer einen maximalen Freiraum auf der CD haben.
Es würden auf 700MB 53,85 Files passen, also reale 53 Files. (700 / 13)
Die CD wäre bis auf 11 MB ausgelastet. (13 * 53)
An ausgelasteten CDs wird es am Ende 15 Stück geben mit insgesamt 795 Files. (800 / 53) und (15 * 53)
Eine CD hätte also noch 5 Files mit insgesamt 65 MB.
Ich weiß es ist eine ziemlich künstliche Rechnung, aber ich denke es zeigt, das selbst wenn ich auf jeder CD, aufgrund schlechter Sortierung, noch eine Gewisse Menge an Platz freihabe, ist der Maximal zusätzlich benötigte Platz bei solch kleinen Dateigrößen zu vernachlässigen.
Es würden auf 700MB 53,85 Files passen, also reale 53 Files. (700 / 13)
Die CD wäre bis auf 11 MB ausgelastet. (13 * 53)
An ausgelasteten CDs wird es am Ende 15 Stück geben mit insgesamt 795 Files. (800 / 53) und (15 * 53)
Eine CD hätte also noch 5 Files mit insgesamt 65 MB.
Ich weiß es ist eine ziemlich künstliche Rechnung, aber ich denke es zeigt, das selbst wenn ich auf jeder CD, aufgrund schlechter Sortierung, noch eine Gewisse Menge an Platz freihabe, ist der Maximal zusätzlich benötigte Platz bei solch kleinen Dateigrößen zu vernachlässigen.
@Brainsucker:
Wie kommst Du auf die 2^50? Wenn Du wirklich alle Anordnungen betrachten wollen würdest, sind das 50!, also noch ein paar mehr...
Wobei die nicht alle von Interesse sind, da es der CD egal ist, an welcher Position die Datei X gespeichert wird.
Um den tatsächlichen kombinatorischen Aufwand zu finden, müsstest Du Dir eher überlegen, wie groß Dein gesamter Datenbestand ist (in CDs), wie groß eine Datei ist (gemittelt) und wie oft die Aufteilung auf CDs eine gemittelte Datei "schneiden" würde - der Überstand für weitere CDs. Dann hättest Du eine gemittelte Abschätzung des Aufwandes, der deutlich kleiner sein sollte als n!, nämlich k^n für k CDs und n Dateien.
Edit:
Wie JonasR im letzten Beitrag schon geschrieben hat - ich glaube auch, dass jedweder Optimierungsversuch bei Deiner Ausgangslage an Dateien (7-14MB) nicht viel bringt und Du vllt. eine CD einsparen kannst, was bei 16CDs (worst case 800 Dateien * 14MB) selbst gegenüber sturem Runterschreiben in z.B. alphabetischer Ordnung nicht viel bringt während Du die andere Ordnung definitiv verlieren würdest.
Edit2:
Oh mann, Kombinatorik ist doch schon eine Weile her. Also k^n ist immernoch zu groß, da hier die Reihenfolge der CDs nocht drinsteckt. Um die noch rauszunehmen, kommt man wohl eher bei k^n/k! raus. Bitte korrigiere mich jmd., der Kombinatorik noch besser aufm Schirm hat.
Wie kommst Du auf die 2^50? Wenn Du wirklich alle Anordnungen betrachten wollen würdest, sind das 50!, also noch ein paar mehr...
Wobei die nicht alle von Interesse sind, da es der CD egal ist, an welcher Position die Datei X gespeichert wird.
Um den tatsächlichen kombinatorischen Aufwand zu finden, müsstest Du Dir eher überlegen, wie groß Dein gesamter Datenbestand ist (in CDs), wie groß eine Datei ist (gemittelt) und wie oft die Aufteilung auf CDs eine gemittelte Datei "schneiden" würde - der Überstand für weitere CDs. Dann hättest Du eine gemittelte Abschätzung des Aufwandes, der deutlich kleiner sein sollte als n!, nämlich k^n für k CDs und n Dateien.
Edit:
Wie JonasR im letzten Beitrag schon geschrieben hat - ich glaube auch, dass jedweder Optimierungsversuch bei Deiner Ausgangslage an Dateien (7-14MB) nicht viel bringt und Du vllt. eine CD einsparen kannst, was bei 16CDs (worst case 800 Dateien * 14MB) selbst gegenüber sturem Runterschreiben in z.B. alphabetischer Ordnung nicht viel bringt während Du die andere Ordnung definitiv verlieren würdest.
Edit2:
Oh mann, Kombinatorik ist doch schon eine Weile her. Also k^n ist immernoch zu groß, da hier die Reihenfolge der CDs nocht drinsteckt. Um die noch rauszunehmen, kommt man wohl eher bei k^n/k! raus. Bitte korrigiere mich jmd., der Kombinatorik noch besser aufm Schirm hat.