Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

Sichere dir deinen Rabatt

Tracks

Haskell

Übungen

Rucksack

Mittel

Einführung

Bob ist ein Dieb. Nach monatelanger, sorgfältiger Planung gelingt es ihm endlich, die Sicherheitssysteme eines schicken Ladens zu knacken.

Vor ihm liegen viele Gegenstände, jeder mit einem Wert und einem Gewicht. Bob würde am liebsten alle Gegenstände mitnehmen, aber sein Rucksack kann nur begrenzt Gewicht tragen. Bob muss sorgfältig abwägen, welche Gegenstände er einpackt, damit der Gesamtwert seiner Auswahl möglichst groß ist.

Anleitung

Deine Aufgabe ist es, herauszufinden, welche Gegenstände Bob mitnehmen soll, damit der Gesamtwert seiner Auswahl maximiert wird und dabei das Fassungsvermögen des Rucksacks berücksichtigt wird.

Die Gegenstände werden als Liste von Gegenständen dargestellt. Jeder Gegenstand hat ein Gewicht und einen Wert. Alle angegebenen Werte sind strikt positiv. Bob kann von jedem Gegenstand nur einen einzigen mitnehmen.

Zum Beispiel:

Items: [
  { "weight": 5, "value": 10 },
  { "weight": 4, "value": 40 },
  { "weight": 6, "value": 30 },
  { "weight": 4, "value": 50 }
]

Knapsack Maximum Weight: 10

Im obigen Beispiel hat der erste Gegenstand das Gewicht 5 und den Wert 10, der zweite Gegenstand hat das Gewicht 4 und den Wert 40, und so weiter. In diesem Beispiel sollte Bob den zweiten und den vierten Gegenstand mitnehmen, um den Wert seiner Auswahl zu maximieren, der in diesem Fall 90 beträgt. Er kann nicht mehr als 90 erreichen, da sein Rucksack ein Gewichtslimit von 10 hat.