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

Obtenir ta réduction

Parcours

Scheme

Exercices

Sac à dos

Difficile

Introduction

Lhakpa est guide de montagne et porteuse sherpa. Après des mois de préparation minutieuse, l'expédition pour laquelle Lhakpa travaille s'apprête à partir. Elle sera payée à hauteur de la valeur de ce qu'elle a porté jusqu'au camp de base.

Devant elle se trouvent de nombreux objets, chacun avec une valeur et un poids. Lhakpa prendrait volontiers tous ces objets, mais son sac à dos ne peut contenir qu'un poids limité.

Instructions

Ta tâche consiste à déterminer quels objets prendre pour que la valeur totale de sa sélection soit maximisée, en tenant compte de la capacité de charge du sac à dos.

Les objets seront représentés par une liste d'objets. Chaque objet aura un poids et une valeur. Toutes les valeurs données seront strictement positives. Lhakpa ne peut prendre qu'un seul exemplaire de chaque objet.

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. Dans cet exemple, Lhakpa doit prendre le deuxième et le quatrième objet pour maximiser sa valeur, qui, dans ce cas, est de 90. Elle ne peut pas obtenir plus de 90, car son sac à dos a une limite de poids de 10.

Notes spécifiques au parcours

Dans la version Scheme, les arguments sont la capacity du sac à dos, une liste des weights et une liste des values. Pas besoin de valider les entrées : les entrées des tests contiennent des valeurs valides et des listes de même longueur.