ALgorithmus der die Optimla Zusammenstellung von Datein errechnet...

Hallo

ich hoffe jemand in diesem Forum kann mir einen kleinen Tip geben !

Also ich habe folgendes Problem ich brauche einen Algorithmus der mir die optimale Kombination von Dateien( von der Grösse aus betrachtet) in einem fest vorgegeben Medium anordnet.

Ein Bsp:

ich habe 5 Dateien:
1. 500 MB
2. 180 MB
3. 130 MB
4. 70 MB
5. 30 MB

Vorgegebene Größe : 700 MB

optimale Kombination:

1. Datei + 3. Datei + 4. Datei

Welchjer Algorithmus is dafür am besten geeigent ???

Danke für dioe Hilfe.

MfG

Nuno

hmm...

versuchs doch mal mit nem genetischen Algorithmus. ^^

ansonsten gehe rekursiv von der Ersten Datei aus. und verbinde sie mit der nächsten, der dann nächsten und so weiter, das sieht dann als ergebnis so aus

Step  1  2  3  4  5
 0     0  0  0  0  0
 1     1  0  0  0  0
 2     1  1  0  0  0
 3     1  1  1  0  0  < crasht, weil zu groß
 4     1  1  0  1  0  < auch zu groß
 5     1  1  0  0  1  < immernoch...
 6     1  0  1  0  0 
 7     1  0  1  1  0  < zu groß
 8     1  0  1  0  1 
 9     0  1  0  0  0  
10     0  1  1  0  0 
11     0  1  1  1  0
12     0  1  1  1  1

von allen möglichen Ergebnissen muss man sich nur noch das raus suchen, das am größten ist.

ist etwas blöd zu erklären, aber ich hoffe, Du kannst Dir anhand des Beispieles ausmalen, was ich meine.

cYa
DjR

Hallo..

diesen Ansatz hatte ich auch schon, das Problem iost, das ich mit 5 Dateien schon 12 Durchläufe brauche .. wenn ich nun 5000 Dateien oder 50000 Dateien habe wird das ein zu grosser rechenaufwand ... deswegen suche ich ja einen Optimierungsalgorithmus ... aber Danke trotzdem für deine Hilfe .

volkard

war das nicht das rucksackproblemchen?

HumeSikkins

war das nicht das rucksackproblemchen?

Mir war doch so, als hätte ich für ein ähnliches Problem im letzten Semester die NP-Vollständigkeit bewiesen.
Hatte ich schon wieder vergessen. Danke für die Synapsenanregung

daishi

Im allgemeinen findet man auch was unter greedy-Alg.
Ist auch nur ein neuer Hut für Rucksackprob.

japro

daishi schrieb:

Im allgemeinen findet man auch was unter greedy-Alg.
Ist auch nur ein neuer Hut für Rucksackprob.

hmm greedy ist doch einfach das wenn man immer die grösst mögliche variante wählt also in dem fall wär das 1, 2 und schon haben wir den käse das programm war zu giereig (greedy) und hat einen falschen weg gewählt

ulath

das problem ist folgendermaßen lösbar:

zuerst musst du die dateien nach ihrer dateigröße linear sortieren.
in deinem beispiel ist das schon gegeben!

1. 500 MB
2. 180 MB
3. 130 MB
4. 70 MB
5. 30 MB

wenn du nun die differenz von dem größten element mit der maximalen größe betrachtest so erhälst du:

700-500 = 200

als nächstes kannst du dann schaun ob das zweite element kleiner oder gleich groß ist wie die differenz

180<=200

wenn das passt kann man den wert des 2ten elements wieder abziehen und man erhällt die neue differenz.

200-180=20

so machst du das immer weiter bis du alle linear durchgangen bist und fängst dann von neuem an bis keine files mehr da sind.

der aufwand ist nur noch linear statt exponentiell, allerdings bekommt man nicht immer die besten lösungen-> s. bsp -> 20 mb werden verschenkt.

ich hoffe ich habe geholfen

japro

eben genau das ist greedy und das mag in dem fall hamlos erscheinen wenn da 20 mb fehlen... aber was macht man bei folgenden dateigrössen:

zu erreichen 700
dateien:
400
310
300
90

da verschenkt man dann einiges

ulath

wieso ?
in deinem beispiel löst er optimal !

700-400=300
310>300
300<=300
300-300=0

erstes paket fertig !

japro

hmm shice... war ein fehler drinn
bei
400
350
350
baut er aber definitv mist

ulath

ne wieder falsch
700 - 400 = 300
350 > 300
400 auf die erste

700 auf die zweite

aber ich weis was du meinst:

wenn z.b.

300
350
350
dann nimmt er die ersten beiden = 650
und den letzten 350

besser wäre deiner ansicht anch dann 700 und 350 .. aber ist letztendlich auch egal, da letztendlich nur 50 verloren gehen ! und nich 350 ...

also wenn die rechenleistung mehr wiegt als der speicherpllatz dann sollte man diese lösung nehmen !

daishi

japro schrieb:

daishi schrieb:

Im allgemeinen findet man auch was unter greedy-Alg.
Ist auch nur ein neuer Hut für Rucksackprob.

hmm greedy ist doch einfach das wenn man immer die grösst mögliche variante wählt also in dem fall wär das 1, 2 und schon haben wir den käse das programm war zu giereig (greedy) und hat einen falschen weg gewählt

Ok, dies ist halt ein Problem dieser Algorithmengruppe, aber wenn nach greedy gesucht wird, bekommt man auch eine Reihe anderer Lösungswege genannt, die mglw. die gewünschte Lösung bringen.

japro

ulath schrieb:

besser wäre deiner ansicht anch dann 700 und 350 .. aber ist letztendlich auch egal, da letztendlich nur 50 verloren gehen ! und nich 350 ...

jo genau bei der neuen version von word wurde darauf rücksicht genommen und ein par speed verbesserungen vorgenommen... das programm druckt jetzt nicht genau das, was du willst, aber etwas ähnliches.