Knapsack Problem
Lektion 7 von 15 im Kurs Rekursion meistern – Herausforderungen für rekursives Denken von Coddy.
Aufgabe
MittelDas Rucksackproblem (Knapsack Problem) ist ein berühmtes Problem.
In diesem Problem hast du einen Rucksack, der ein vordefiniertes Gewicht aufnehmen kann, und Gegenstände, wobei jeder Gegenstand ein Gewicht und einen Wert hat.
Deine Aufgabe ist es, so viel Wert wie möglich innerhalb der Gewichtsgrenzen des Rucksacks mitzunehmen.
Zum Beispiel,
values - [20, 5, 40, 10, 15]
weights - [1, 2, 8, 3, 7]
Gewicht des Rucksacks - 10
Die Lösung besteht darin, die Gegenstände mit den Gewichten 1 und 8 und den Werten 20 und 40 zu nehmen.
Der maximale Wert ist 60, und das Gesamtgewicht beträgt 9 (was kleiner oder gleich 10 ist, was bedeutet, dass es ein gültiges Gewicht ist).
Schreibe eine Funktion namens knapsack, die eine Ganzzahl W und zwei Arrays von Ganzzahlen values und weights erhält und die Lösung für das Rucksackproblem unter Verwendung der Eingabewerte zurückgibt (den maximalen Wert, den der Rucksack aufnehmen kann).
Probier es selbst
#include <stdio.h>
#include <stdlib.h>
int knapsack(int W, int* values, int values_size, int* weights, int weights_size) {
// Hier Code schreiben
return 0;
}
Alle Lektionen in Rekursion meistern – Herausforderungen für rekursives Denken
2Medium Challenges
Knapsack ProblemNumber of SquaresInterleaving ResultSum CombinationsFind TripletSplit Array