[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!

 

[Turri]

Also meine Lösung basiert auf der Spoiler-Variante die Alexander genutzt hat.
Auf gebrochene Gewichte funktioniert meine Variante jetzt auch schon.
Hatte von Anfang an mit Kommazahlen gerechnet.

Ich hatte ja mal das Ergebnis bei 250 Leckereien hier reingestellt.
Mich würden ja mal andere Ergebnisse interessieren, um zu vergleichen (mit genau den 250 Leckereien),
Damit ich mal sehe wie gut meine implementierte Variante arbeitet bzw. ob andere ein anderes Ergebnis haben.

 

[Jellysheep]

Bei 250 Eiern kann dir Enumerator weiterhelfen, der hat seinen Computer schon eine Nacht lang rechnen lassen.
Ich kann dir aber das Ergebnis meiner Abzählmethode für 100 Eier zeigen, das kannst du mal vergleichen:

=> Optimale Kombination:
Vollmilch-Eierlikör-Schokohase; Joghurt-Trüffel-Krokant-Goldhase; Butter-Schmunzeleier;
(Gewicht: 494 g, Brennwert: 3393 kcal)

(Ob es richtig ist, weiß ich auch nicht genau... Wir können ja mal schauen, ob jemand eine bessere Lösung hat)

Das Problem bei meiner Variante ist, dass die rekursive Funktion (in der optimierten Version * ) bei hundert Eiern schon 22.827.664 mal aufgerufen wird.
(Das dauert 16 Sekunden lang, ohne Optimierung viel, viel länger)
Bei 250 Eiern wird es dann vermutlich viel mehr.

* Die meisten zu schweren Kombinationen werden nicht gezählt.

[EDIT]
Bei 250 Eiern sind es locker über eine Millionen Aufrufe der Funktion.
[EDIT2]
Es sind sogar über drei Millionen.
[EDIT3]
Die Berechnung ist durch, es waren über 8 Mio. Aufrufe.

 

[Matthias Reitinger]

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*

Das würde ich nur zu gerne, denn dann wären mir der Turing-Award und die Fields-Medaille (mindestens) sicher Damit hätte man nämlich nebenbei P=NP gezeigt.

Jellysheep hat ja schon ein Beispiel genannt, bei dem dieses Verfahren nicht das optimale Ergebnis liefert. Dass es bei den Datensätzen hier trotzdem oft das Optimum findet, liegt vermutlich daran, dass sich die Kalorien/Masse-Verhältnisse der einzelnen Objekte nur wenig unterscheiden. Man kann aber trotzdem leicht Datensätze konstruieren, bei denen der einfache Algorithmus beliebig weit daneben liegt. Z.B. diesen hier:

500
Gold-Osterhase
251 1255
Silber-Osterhase
250 1249
Silber-Osterhase
250 1249

Optimal wäre die Auswahl der beiden Silber-Osterhasen (500g und 2498kcal), der Näherungsalgorithmus wählt hier aber nur den Gold-Osterhasen (251g und 1255kcal) aus und liefert damit eine knapp 50% schlechtere Kalorienausbeute.

Grüße,
Matthias

 

[OnlyFoo]

Hat denn nun noch jemand im Millisekunden/Sekundenbereich die garantiert richtigen Ergebnisse?

 

[Alexander Schuc]

Hatte noch keine Zeit dazu, aber es ist mein erklärtes Ziel..

 

[Chumper]

Meins auch, ich habe auch schon einen guten Ansatz, nur ob der hält was er verspricht wird sich zeigen...

 

[Jellysheep]

@OnlyFoo: Wie lange braucht dein Programm mit den 250 Eiern?
@Turri: Ich habe die gleiche Lösung wie du. Aber mein Programm ist ein bisschen schneller.
Welche Methode verwendest du? Dynamische Programmierung?

Mit drei (edit: inzwischen vier) Optimierungen im Code komme ich mit der "Abzählmethode" (alle Kombinationen überprüfen) bei den 100 Eiern auf 0 ms.
Hier mein Ergebnis:

Beste Kombination:
Vollmilch-Eierlikör-Schokohase; Joghurt-Trüffel-Krokant-Goldhase; Keks-Vollmilcheier;
Gewicht: 494 g
Brennwert: 3393 kcal

Hat jemand eine sinnvollere Lösung?
@OnlyFoo: Wie sieht die Lösung deiner dynamischen Programmierung für 100 Eier aus?

Für 250 Eier braucht das Programm auch nur 0 ms , hier das Ergebnis (das Gleiche wie das von Turri):

Beste Kombination:
Waffel-Keks-Buttereier; Marzipan-Sahne-Butter-Schlemmerhase; Keks-Trüffelhase; Keks-Platineier;
Gewicht: 498 g
Brennwert: 3442 kcal

Hat hier noch jemand ein anderes Ergebnis?

@OnlyFoo: Der Generator ist wirklich toll!

 

[Turri]

Hallo JellySheep,

ich verwende die selbe Lösung wie Alex.
Ich erstelle mir ein Gewicht-Kalorien-Verhältnis und sortiere danach absteigend.
Dann wird in Lisa's Korb eingefügt bis er so voll wie möglich ist.
Ich nutze keine dynamische Programmierung.

MfG Turri

PS: 0ms scheint mir etwas zu optimal

 

[OnlyFoo]

@OnlyFoo: Wie lange braucht dein Programm mit den 250 Eiern?
@OnlyFoo: Wie sieht die Lösung deiner dynamischen Programmierung für 100 Eier aus?
@OnlyFoo: Der Generator ist wirklich toll!

Hey, hier meine Ergebnisse. die 100k.txt enthält 100000 Eier, hab sie auch mal in den Anhang gehängt,
kannst du ja mal zum Vergleich testen. Ergebnisse kommen bei mir immer in der Reihenfolge, wie sie auch im Original waren.. Die Zeiten sind immer inkl. einlesen der Daten von der Standardeingabe.

0 ms find ich auch etwas optimistisch - klingt eher nach Messungenauigkeiten - probier doch auch mal mit größeren Eiermengen

olli@desktop:/tmp$ ./a.out < 100leckereien.txt 
Optimale Auswahl: Vollmilch-Eierlikör-Schokohase, Joghurt-Trüffel-Krokant-Goldhase, Trüffel-Butter-Eierlikör-Ostereier
Masse: 494 g
Nährwert: 3393 kcal
Rechenzeit: 3ms
olli@desktop:/tmp$ ./a.out < 250leckereien.txt 
Optimale Auswahl: Marzipan-Sahne-Butter-Schlemmerhase, Keks-Trüffelhase, Keks-Platineier, Waffel-Keks-Buttereier
Masse: 498 g
Nährwert: 3442 kcal
Rechenzeit: 7ms
olli@desktop:/tmp$ ./a.out < 100k.txt
Optimale Auswahl: ei-2383, ei-23359, ei-40669, ei-47555, ei-62142, ei-62736, ei-65451, ei-66390, ei-77632, ei-79046
Masse: 500 g
Nährwert: 9983 kcal
Rechenzeit
  einlesen:    327 ms
  auswählen:  1859 ms
  gesamt:     2186 ms
olli@desktop:/tmp$ cat /proc/cpuinfo
vendor_id       : GenuineIntel
model name      : Intel(R) Pentium(R) 4 CPU 3.06GHz
cpu MHz         : 3073.850
cache size      : 512 KB
bogomips        : 6147.67

Ist jetzt wohlgemerkt auf meinem langsamen Heimrechner

Edit: Dafür werden aber etwa 600mb RAM benötigt...
Edit3: Nochmal etwas schneller gemacht...

 

[rd4eva]

Hmm sowas bescheuertes PHP steigt schon bei 10000 Eiern mit einem müden "Out of Memory" aus.

Kann ich leider nur folgende Ergebnisse teilen:

1000 Eier :

Ausgewählte leckerlies : ei-224,ei-442,ei-740,ei-268,ei-246,ei-726,ei-419,ei-581,ei-115,
Maximal Gewicht : 500
Gesamtgewicht : 500
Gesamtkalorien : 8748

Ausfuehrungszeit in sekunden : 2.0044429302216

250 Leckereien

Ausgewählte leckerlies : Waffel-Keks-Buttereier,Keks-Trüffelhase,Keks-Platineier,Marzipan-Sahne-Butter-Schlemmerhase,
Maximal Gewicht : 500
Gesamtgewicht : 498
Gesamtkalorien : 3442

Ausfuehrungszeit in sekunden : 0.61961889266968

100 Leckereien

Ausgewählte leckerlies : Joghurt-Trüffel-Krokant-Goldhase,Vollmilch-Eierlikör-Schokohase,Trüffel-Butter-Eierlikör-Ostereier,
Maximal Gewicht : 500
Gesamtgewicht : 494
Gesamtkalorien : 3393

Ausfuehrungszeit in sekunden : 0.19754695892334

Achja ich habe mich ein bisl mit memoization ausgetobt