[QUIZ#15] Lisas Osternest


Quiz #15
Lisas Osternest

Regeln
Die Regeln und der Ablauf der Quizrunde können in der entsprechenden Ankündigung eingesehen werden. Bitte lest sie euch aufmerksam durch, da sie alle wichtigen Informationen enthält. Es ist erlaubt und erwünscht, dass ihr euch direkt in diesem Thema über die Aufgabe austauscht. Also stellt bei Unklarheiten in der Aufgabenstellung oder Problemen bei der Umsetzung Fragen, versorgt uns mit nützlichen oder weiterführenden Links, diskutiert mögliche Lösungsansätze. Macht bei Beiträgen, die allzu viel verraten, aber bitte trotzdem Gebrauch vom [spoiler]-Tag.

Abgabe
Die Abgabe erfolgt wie immer im Abgabeforum. Abgabefrist ist Sonntag, der 11. April 2010 um ca. 18 Uhr.

Die Aufgabe
Es ist Ostersonntag und die kleine Lisa macht sich mit ihrem noch leeren Osternest auf die Suche nach den versteckten Leckereien. Aber oh weh, der Osterhase hat dieses Jahr wohl Überstunden geschoben! Lisa kann unmöglich alle Süßigkeiten auf einmal in ihr Nest legen, denn sonst wird es ihr viel zu schwer. Mehr als 500 g kann sie beim besten Willen nicht schleppen. Sie muss also Wohl oder Übel einige Naschereien weglassen. Lisa will aber trotzdem möglichst viel von ihrer Auswahl haben, also die Summe der Kalorien des Naschwerks in ihrem Korb maximieren.

Hilf Lisa, indem du ein Programm schreibst, welches die beste Auswahl an Süßigkeiten ermittelt.

Eingabe
Die Eingabe soll textuell erfolgen. In der ersten Zeile steht die maximal zulässige Masse der Auswahl (in Gramm). Darauf folgen die Bescheibungen der Süßigkeiten. Dabei wechseln sich je eine Zeile mit einer textuellen Beschreibung und eine Zeile mit Masse (in Gramm) und kcal-Angabe ab. Eine Leerzeile beendet die Eingabe. Beispiel:
Code:
500
Nougat-Eier
84 427
Fondant-Eier
150 540
Ostereier
189 291
Spannungs-Eier
63 330
Waffeleier
120 600
Melker Runzelhase
70 371
Lynt Platinhase
250 1360

Ausgabe
Die Ausgabe soll aus drei Teilen bestehen:
  1. Die optimale Auswahl als kommaseparierte Liste
  2. Die Masse der Auswahl (in Gramm)
  3. Der Nährwert der Auswahl (in kcal)
Beispiel:
Code:
Optimale Auswahl: Nougat-Eier, Spannungs-Eier, Melker Runzelhase, Lynt Platinhase
Masse: 467 g
Nährwert: 2488 kcal

Und jetzt ran an die Tasten und viel Spaß beim Programmieren!
 

Jellysheep

Erfahrenes Mitglied
Schon fertig? :eek:
Ich muss morgen mal schauen, wie lange ich dafür brauche...
Wie wäre es mit der Erweiterung, dass in mehreren zusätzlichen, evtl. (z.B. mit Leerzeile) abgetrennten, Zeilen ein oder mehrere einzelne Eier angegeben werden können, die praktisch in höherer Anzahl das Nest bis zum Maximalgewicht auffüllen und dabei möglichst viel kcal hinzufügen? ;)
Z.B. Eingabe:
500
Nougat-Eier
84 427
Fondant-Eier
150 540
Ostereier
189 291
Spannungs-Eier
63 330
Waffeleier
120 600
Melker Runzelhase
70 371
Lynt Platinhase
250 1360

Butter-Krokant Eier
5 117
Und Ausgabe:
Optimale Auswahl: Nougat-Eier, Spannungs-Eier, Melker Runzelhase, Lynt Platinhase, 6x Butter-Krokant Eier
Masse: 497 g
Nährwert: 3190 kcal
 

Enumerator

Mitglied Kamel
Wirklich schönes Quiz...

Wie wäre es mit der Erweiterung, dass in mehreren zusätzlichen, evtl. (z.B. mit Leerzeile) abgetrennten, Zeilen ein oder mehrere einzelne Eier angegeben werden können, die praktisch in höherer Anzahl das Nest bis zum Maximalgewicht auffüllen und dabei möglichst viel kcal hinzufügen? ;)
Besser fände ich eine optionale dritte Zahl nach Gewicht und KCal...

Gruß
Enum
 

Turri

Erfahrenes Mitglied
Hallo,

ich hätte ja mal eine Frage.

Was heisst denn optimale Auswahl, d.h. es müssen so viele Arten wie möglich verwendet werden?

Wenn ich die obigen Eingaben verwende, dann wäre ja 2x Lynt Platinhase die Auswahl.

2x 250g = 500g -> optimale Ausnutzung
Und der Platinhase hat pro g die meisten Kalorien.
 

Jellysheep

Erfahrenes Mitglied
Ich denke mal, dass von jedem Päckchen o.ä. nur eines verwendet werden darf.
Und dabei eben so viel kcal wie möglich.
 
Hallo,

ich hätte ja mal eine Frage.

Was heisst denn optimale Auswahl, d.h. es müssen so viele Arten wie möglich verwendet werden?

Wenn ich die obigen Eingaben verwende, dann wäre ja 2x Lynt Platinhase die Auswahl.

2x 250g = 500g -> optimale Ausnutzung
Und der Platinhase hat pro g die meisten Kalorien.
Es gibt aber nur einen Platinhasen, genauso wie es jede andere Süßigkeit nur einmal gibt. Lisa darf auch keine halben oder viertelten Portionen in ihren Korb tun, es ist pro Sorte also eine echte 0-1-Entscheidung (drin oder nicht drin) zu treffen.

Grüße,
Matthias
 

Chumper

Erfahrenes Mitglied
- Dann kann deine optimale Lösung aber nicht stimmen:
Optimale Auswahl: Nougat-Eier, Spannungs-Eier, Melker Runzelhase, Lynt Platinhase, 6x Butter-Krokant Eier
Masse: 497 g
Nährwert: 3190 kcal
- Hier zähle ich 6x Butter-Krokant Eier (BKE) , sollte es davon dann nicht auch nur eins geben?
- Oder ist das bei Eiern egal, theoretisch müsstest du doch das BKE 6x eingeben.

€dit:
Ich lass das mal so stehen, aber ich habe mich verguckt. Ich habe mich auf die Erweiterung von Jellysheep bezogen und damit ist das auch wieder obsolet.
Die Erweiterung finde ich aber gut
 
Zuletzt bearbeitet:

Jellysheep

Erfahrenes Mitglied
Damit ist die Ausgabe des Programmes mit Erweiterung gemeint:
Wie wäre es mit der Erweiterung, dass in mehreren zusätzlichen, evtl. (z.B. mit Leerzeile) abgetrennten, Zeilen ein oder mehrere einzelne Eier angegeben werden können, die praktisch in höherer Anzahl das Nest bis zum Maximalgewicht auffüllen und dabei möglichst viel kcal hinzufügen? ;)
So, ich bin auch gleich fertig. Wieviele verschiedene Eier können denn eure Programme verwalten?
//Edit: Ich hab es grade ausprobiert, mein Programm schafft maximal 1625 verschiedene Eier.
 
Zuletzt bearbeitet:

Enumerator

Mitglied Kamel
Wieviele verschiedene Eier können denn eure Programme verwalten?
Theoretisch irgenwas bei CHAR_BIT * sizeof(long long) - wenn meine Erinnerung an den Quellcode von Perl5 mich nicht trügt... :p

[EDIT]
Ich hab es grade ausprobiert, mein Programm schafft maximal 1625 verschiedene Eier.
Auf meinem System (32b/i386/OpenBSD) sind es nur 64. Reicht aber. Oder hast Du mehr verschiedene Sweeties in deinem Schrank? :p
 
Zuletzt bearbeitet:

Jellysheep

Erfahrenes Mitglied
:offtopic: Bei mir gibt es nur sechs Sorten an Eiern und zwei Hasen. :)
Mir würden wahrscheinlich auch nur 30 verschiedene einfallen. :)
Theoretisch irgenwas bei CHAR_BIT * sizeof(long long) - wenn meine Erinnerung an den Quellcode von Perl5 mich nicht trügt... :p
Oh, das wäre enorm viel. Da bekomme ich gleich Minderwertigkeitskomplexe. :)
Mein Programm kann inzwischen auch sehr viel, evtl. sogar so viel wie deines, aber aufgrund meiner schlechten Programmierung würde es zum Berechnen ewig dauern.
1500 verschiedene Eier brauchen bei mir schon zwei Minuten... :-(
Aber dafür habe ich eine schöne Progressbar, die die Wartezeit verkürzt. :p
Ich denke, ich werde das Programm noch in der Geschwindigkeit optimieren und dann morgen abgeben.
Ich bin schon mal gespannt, welchen Lösungsweg die anderen Teilnehmer genommen haben. :)
 

Turri

Erfahrenes Mitglied
1500 verschiedene Eier brauchen bei mir schon zwei Minuten... :-(
Kannst du mir deinen Datensatz zur Verfügung stellen?
Mir fallen keine 1500 Sorten ein. ;)

Mit 250 Leckereien von Matthias dauert mein Programm in der Debug-Version 3ms. :)
Ich habs mit C# als Konsolenanwendung gelöst.
Ist natürlich noch die Frage, ob die Lösung richtig ist.

Hier meine Lösung für die 250 Leckereien.
Code:
Optimale Auswahl: Waffel-Keks-Buttereier, Keks-Trüffelhase, Keks-Platineier, Marzipan-Sahne-Butter-Schlemmerhase
Masse: 498g
Nährwert: 3442kcal
Rechenzeit: 3ms
 

OnlyFoo

Erfahrenes Mitglied
Selbe Lösung in etwa 0.4sek mit python... 10000 Eier in unter 18 Sekunden.
Simples Oster-Hasen-Script:

Python:
import random
N = 10000
print 500
for i in range( N ):
    print "ei-%d" % random.randint(0, 10000000)
    print random.randint( 50, 100 ), random.randint( 200, 1000 )
 

Turri

Erfahrenes Mitglied
Ui cool OnlyFoo,

den Datensatzgenerator hab ich mal glatt übernommen.
Jetzt steht mein Prog mit 10000 Eiern bei 3,6s.
 

OnlyFoo

Erfahrenes Mitglied
Mit 250 Leckereien von Matthias dauert mein Programm in der Debug-Version 3ms. :)
Ich habs mit C# als Konsolenanwendung gelöst.
Ist natürlich noch die Frage, ob die Lösung richtig ist.

Jetzt steht mein Prog mit 10000 Eiern bei 3,6s.
Hab meine Version nochmal auf C++ portiert... In der debug-Version komm ich bei 250 Leckerlis auf 20ms, bei 10k jedoch auf knapp unter 800ms... Kompiliert mit -O4 bei 250: unter 1ms, bei 10k: knapp unter 300ms - da ist dann Einlesen der Datensätze bereits mit drinne... :)...
 

Turri

Erfahrenes Mitglied
Hab noch was gefunden im Code *freu*, nun komm ich in der
Release-Variante und 10.000 Datensätzen bei 75-80ms und mit
Debug-Variante und 10.000 Datensätzen bei 85-110ms raus. ^^
Inclusive dem Einlesen der Datensätze.

Bin dann wirklich mal auf die Lösungen gespannt. :)
 

Alexander Schuc

crazy-weasel
Soo.. hab mal schnell eine Lösung runtergehackt..

Eine Auswahl von 1.000.000 (1Mio) Süssigkeiten wird in ~5000ms verarbeitet, wobei das mit dem Einlesen ist. Die Auswahl selbst wird innerhalb von ~1600ms vorgenommen.

100.000 in ~450ms / ~130ms
10.000 in ~40ms / ~12ms

C# Release Build :) (..aber Debug nimmt sich nicht wirklich viel)

lg,..
 

OnlyFoo

Erfahrenes Mitglied
Auf was für Hardware? Meine Zahlen bezogen sich auf nen alten Pentium4 mit 3.06ghz :) - Aber bei den Unterschieden liegts wohl in erster Linie am Algorithmus :)
 

Neue Beiträge