Code Competition 05/2017: Das Rucksackproblem

{ABOUT}

Das Rucksackproblem ist eine in der Informatik bekannte Problemstellung.
Stell Dir vor, Du stehst am Check-in-Schalter von “Knapsack”-Airlines und erfährst, dass Du Deine einzelnen Gepäckstücke, die unterschiedlich wertvoll sind, in Deinem Rucksack verstauen musst. Dein Rucksack darf insgesamt maximal 15 kg wiegen, sonst geht er nicht mehr als Handgepäck durch und wird abgewiesen. Es ist klar, das Du nicht alle Gepäckstücke wirst mitnehmen können. Du musst nun eine Lösung finden, wie Du Deinen Rucksack am besten packst, um die wichtigsten Gepäckstücke mitzunehmen.

Gegeben sind also n Gepäckstücke mit den Eigenschaften Gewicht und Wert. Außerdem gegeben ist eine Grenze (15kg), die nicht überschritten werden darf. Gesucht ist die bestmögliche Kombination von Gegenständen, die das Grenzgewicht nicht überschreitet und den höchsten Gesamtwert hat.

Als Herangehensweise bieten sich hier näherungsweise Lösungen optimal an, da eine exakte Lösung für größere n aufgrund der Laufzeitkomplexität von O(2^n) ungeeignet ist.

{INPUT}

Deine Abgabe soll:

• Das Rucksackproblem mit den Variablen n = Anzahl der Gegenstände und m = Maximalgewicht des Rucksacks gelöst werden
• Die Werte der Variablen sollen über die Konsole oder eine Eingabemaske sinnvoll gesetzt werden können (die Werte der Eigenschaften der Gegenstände können generiert werden).

Dein Algorithmus soll:

• x Gegenstände in einen Rucksack packen und dabei den bestmöglichen Gesamtwert erreichen.
• Jeder Gegenstand hat die Eigenschaften Gewicht g (in kg) und Wert w (in Euro)
• Der Rucksack darf nur ein Maximalgewicht von m (in kg) haben
• Sowohl bei Gewicht (kg) als auch beim Wert (Euro) handelt es sich um positive ganze Zahlen.

{REVIEW}

Worauf achten wir bei der Bewertung Deiner Abgabe?

• Funktionalität: Lässt sich das Programm bedienen? Tut die Anwendung oder die Funktion, was sie soll? Wie umfangreich sind die Funktionen?
• Code-Qualität: Ist der Code sinnvoll strukturiert und effizient?
• Code-Lesbarkeit / Dokumentation: Lässt sich der Quellcode nachvollziehen? Ist der Code kommentiert?
• Setup: Ist das System einfach einzurichten / aufzusetzen? (z.B. mittels guter Dokumentation, Docker, Vagrant, Skripte, o.ä.)
• Welche Zusatzfeatures wurden eingebaut?

Wie bewerten wir?

1. Platz:
   400 €
2. Platz:
   300 €
3. Platz:
   200 €

Abgabe

Programmiersprachen:
Java, C, C++, C#, JavaScript, Python, Haskell, PHP/HTML/MySQL, Swift sowie alle gängigen Programmiersprachen.
Die Entscheidung, ob Du die Aufgabenstellung mit einer Webseite, einer App oder einer Desktopanwendung löst, ist Dir überlassen. Die Verwendung von Frameworks ist erlaubt.