ALgorithmus der die Optimla Zusammenstellung von Datein errechnet...
-
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
-
Im allgemeinen findet man auch was unter greedy-Alg.
Ist auch nur ein neuer Hut für Rucksackprob.
-
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
-
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 MBwenn 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
-
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
90da verschenkt man dann einiges
-
wieso ?
in deinem beispiel löst er optimal !700-400=300
310>300
300<=300
300-300=0erstes paket fertig !
-
hmm shice... war ein fehler drinn
bei
400
350
350
baut er aber definitv mist
-
ne wieder falsch
700 - 400 = 300
350 > 300
400 auf die erste700 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 350besser 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 !
-
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.
-
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.
