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 :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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 :

1 2 3

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!

Schöne Aufgabe, hat Spaß gemacht, Ideen für Erweiterungen?

Schon fertig?
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

Wirklich schönes Quiz...

Zitat von Jellysheep

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

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.

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

Sooo...endlich mach ich auch einmal mit...

Fertig

Zitat von Turri

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

- 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

Damit ist die Ausgabe des Programmes mit Erweiterung gemeint:

Zitat von Jellysheep

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.

Zitat von Jellysheep

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...

[EDIT]

Zitat von Jellysheep

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?

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...

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.
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.

Hallo,

ich hab mal noch ein paar Zufallsdatensätze erstellt (mit 20, 30, 50, 100 und 250 Sorten), die ihr zum Testen und Vergleichen verwenden könnt.

Grüße,
Matthias

Zitat von Jellysheep

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 :

1 2 3 4

Optimale Auswahl: Waffel-Keks-Buttereier, Keks-Trüffelhase, Keks-Platineier, Marzipan-Sahne-Butter-Schlemmerhase Masse: 498g Nährwert: 3442kcal Rechenzeit: 3ms

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

Code python:

1 2 3 4 5 6

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 )