[QUIZ#15] Lisas Osternest

[Alexander Schuc]

Ist mein 2 Jahre altes Notebook mit Intel Core 2 Duo @1,8 Ghz mit 2gb Ram.

 

[Matthias Reitinger]

Um die Diskussion mal wieder vom plumpen Vergleich gewisser virtueller Körperteile ;-] wegzubewegen und etwas brauchbare Zusatzinfos zu liefern: die zu lösende Aufgabe ist ein echter Klassiker. Als Mitglied der Gruppe der NP-vollständigen Probleme besteht wenig Hoffnung darauf, einen effizienten Lösungs-Algorithmus angeben zu können. Allerdings lässt sich mit Hilfe von dynamischer Programmierung ein Algorithmus formulieren, der unter bestimmten Rahmenbedingungen trotzdem recht flott unterwegs ist. Ich nehme mal an, dass die niedrigen Ausführungszeiten von Alex, OnlyFoo und Turri durch dynamische Programmierung erreicht wurden. Liege ich da richtig? Und falls nicht: wie seid ihr dann an das Problem herangegangen? Wie ändern sich eure Ausführungszeiten, wenn ihr für die Massenangaben Milligramm oder gar Mikrogramm als Einheit verwendet? Ließe sich euer Algorithmus problemlos auf nicht-ganzzahlige Massen verallgemeinern?

Grüße,
Matthias

 

[Enumerator]

Wenn ich die weiter oben umrissene Methode von wegen "kcal pro Gramm == Priorität" überdenke, komme ich einfach auf keinen effizienten Algorithmus der garantieren kann die beste Lösung auszuspucken...
Bin echt mal gespannt wie die oben genannten Zeiten zustande kommen.. Mein momentaner Ansatz hat für die 250leckereien aus Matthias Zipfile die ganze Nacht gebraucht. :-(

 

[Jellysheep]

Wenn ich die weiter oben umrissene Methode von wegen "kcal pro Gramm == Priorität" überdenke, komme ich einfach auf keinen effizienten Algorithmus der garantieren kann die beste Lösung auszuspucken...
Bin echt mal gespannt wie die oben genannten Zeiten zustande kommen.. Mein momentaner Ansatz hat für die 250leckereien aus Matthias Zipfile die ganze Nacht gebraucht. :-(

Da bin ich aber froh, meiner schafft die 250 auch nicht so schnell...
Für die 100 Eier braucht er schon 2,5 Sekunden... :-(
Ich werde jetzt aber mal die dynamische Programmierung ausprobieren, bisher hatte ich es rekursiv versucht.

 

[Alexander Schuc]

Nun, wie ich erwähnt hab, hab ich meine Lösung nur recht flott erstellt. Garantieren, dass es die beste Lösung ist, werd ich wohl nicht können. Vielleicht sollte ich es nur Näherung nennen.
Mag sich jemand meinen Ansatz ansehen, und einen mathematischen Beweis für die Korrektheit bringen? *g*

Ablauf:

Spoiler

- Einlesen
- Einträge nach dem Verhältnis Kalorien / Gewicht sortieren
- Ein Durchlauf über die sortierten Einträge. Ist für einen Eintrag noch Platz frei im Nest, dann kommt er rein, ansonsten wird er ausgelassen.

lg,..

 

[Enumerator]

Aaah, Ich hab' den Spoiler gelesen! Stecht mir die Augen aus!
Nee Du, so leicht ist es dann doch nicht: Du bekommst zwar immer ein gut gefülltes Nest, aber Lisa will das Bestmögliche - und das kannst Du Ihr nicht immer bieten.
Jaja, die Frauen.

 

[Jellysheep]

Dieser Ansatz ist, wie auf dieser Seite gezeigt, nicht ganz richtig.
Es liefert ein recht gutes Ergebnis, aber nicht das beste.

Kleines Beispiel:
Maximal 10g im Nest
Elemente 1[5g, 5kcal]; 2[4g, 2kcal]; 3[3g, 1,4kcal]; 4[2g, 0,7 kcal]
Dein Ergebnis: Kombination 1+2 => 9g und 7 kcal
Optimales Ergebnis: Kombination 1+3+4 => 10g und 7,1 kcal

Das ist jetzt kein großer Unterschied, jedoch nicht vernachlässigbar.
Aber es ist wahrscheinlich in Abhängigkeit zur Geschwindigkeit die schnellste Methode mit gutem Ergebnis.

Grüße
Jellysheep

[EDIT]
Ups, da war wohl jemand schneller. Aber nur haarscharf. ;-]

 

[Enumerator]

Ich hab' die oben beschriebene Methode mal eben in Perl nachgebaut.
Das Witzige ist: Wenn ich nicht absteigend sondern aufsteigend sortiere habe ich beim Beispiel aus der Eröffnung des Quiz das richtige Ergebniss...

 

[Alexander Schuc]

Joa, war nur auf die schnelle.. evt setz ich mich unter der Woche nochmal dran.

Aber danke fürs Beispiel zur Untermauerung. hehe

Übrigens, mit meinem Code kommt selbe raus wie beim Beispiel von Reima.. @ Enumerator
Kannst dir dann Ende der Woche eh ansehn..

 

[OnlyFoo]

Ich habs mit dynamischer Programmierung gelöst, der Algorithmus steht auf der deutschen Wikiseite zum Rucksackproblem. Somit sollten meine Ergebnisse relativ zuverlässig sein.
Das ist jedoch nicht so einfach auf gebrochene Gewichte zu erweitern, auch erhöht sich der Speicherverbrauch mit jedem Gramm das Lisa tragen kann ... aber es ist schön schnell!