[QUIZ#15] Lisas Osternest

[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