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

Obtenir ta réduction

Parcours

Haskell

Exercices

Sac à dos

Moyen

Introduction

Bob est un voleur. Après des mois de préparation minutieuse, il parvient enfin à percer les systèmes de sécurité d'un magasin chic.

Devant lui se trouvent de nombreux objets, chacun ayant une valeur et un poids. Bob prendrait volontiers tous les objets, mais son sac à dos ne peut porter qu'un poids limité. Bob doit donc bien réfléchir aux objets à emporter pour que la valeur totale de sa sélection soit maximale.

Instructions

Ton objectif est de déterminer quels objets Bob doit emporter pour que la valeur totale de sa sélection soit maximisée, en tenant compte de la capacité de portage de son sac à dos.

Les objets seront représentés sous la forme d'un tableau. Chaque objet possède un poids et une valeur. Toutes les valeurs données sont strictement positives. Bob ne peut prendre chaque objet qu'une seule fois.

Par exemple :

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

Knapsack Maximum Weight: 10

Dans l'exemple ci-dessus, le premier objet a un poids de 5 et une valeur de 10, le deuxième objet a un poids de 4 et une valeur de 40, et ainsi de suite. Ici, Bob doit prendre le deuxième et le quatrième objet pour maximiser sa valeur, qui vaut, dans ce cas, 90. Il ne peut pas obtenir plus de 90, car son sac à dos a une limite de poids de 10.