Knapsack Problem
Leçon 7 sur 15 du cours Défis de récursivité - Maîtrisez la pensée récursive de Coddy.
Défi
MoyenLe problème du sac à dos est un problème célèbre.
Dans ce problème, vous avez un sac à dos qui a un poids prédéfini qu'il peut supporter et des objets où chaque objet a un poids et une valeur.
Votre tâche est d'emporter le plus de valeur possible dans les limites du poids du sac à dos.
Par exemple,
values - [20, 5, 40, 10, 15]
weights - [1, 2, 8, 3, 7]
Poids du sac à dos - 10
La solution est de prendre les objets avec les poids 1 et 8 et les valeurs 20 et 40.
La valeur maximale est 60, et le poids total est 9 (ce qui est inférieur ou égal à 10, signifiant qu'il s'agit d'un poids valide).
Écrivez une fonction nommée knapsack qui reçoit un entier W et deux tableaux d'entiers values et weights et renvoie la solution au problème du sac à dos en utilisant les valeurs d'entrée (la valeur maximale que le sac à dos peut contenir).
Essayez vous-même
#include <stdio.h>
#include <stdlib.h>
int knapsack(int W, int* values, int values_size, int* weights, int weights_size) {
// Écrire le code ici
return 0;
}
Toutes les leçons de Défis de récursivité - Maîtrisez la pensée récursive
2Medium Challenges
Knapsack ProblemNumber of SquaresInterleaving ResultSum CombinationsFind TripletSplit Array