Code Competition "Das Rucksackproblem" 05/2017 | IT-Talents

Dein letzter Login ist schon eine Weile her.

Bitte überprüfe, ob alle Angaben in Deinem Profil noch aktuell sind.


Das Rucksackproblem

Wie packst Du Deinen Rucksack am besten?

{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?

{POST}

Jetzt Lösung abgeben

Win!

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

Facts

Partner

Zeitlicher Ablauf

Abgabetermin:
31. Mai 2017 - 23:59Uhr

Auswertung:
Juni 2017

Siegerehrung:
Juli 2017

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.

Help!

Du hast Fragen? Immer her damit!
 
Jan-Dirk
Tel.: +49 521 / 911 730 52
E-Mail: talente@it-talents.de

Schnell-Login für unsere Mitglieder

Tipp: Halte Dein Profil aktuell.

Lass' uns wissen, falls sich etwas Neues bei Dir ergibt.

Tipp: Vervollständige Dein Profil für noch bessere Karrierechancen.

Bist Du Schüler, Student oder bereits berufstätig? Teile uns Deinen aktuellen Status mit, damit wir Dir sinnvolle Aufgaben anbieten können.

Jetzt Status angeben

Wann stehst Du der IT-Branche zur Verfügung?

Bitte Monat und Jahr angeben.

{{ perspectiveForm.availableFrom.$error.dynamic }}

Neuer Versuch

Wo möchtest Du durchstarten?

{{ location.geolocation.name }}×
Bitte mindestens ein Ort angeben.

Als {{currentUser.status.title}} bist Du bereit für:


Lade Beschäftigungsarten

Bitte wähle den Zeitpunkt, Ort und min. eine Beschäftigungsart aus.