Algorithme glouton

Algorithmique - Mathématiques NSI

Exercice 1 : Algorithme glouton et problème du sac à dos

On considère un sac à dos dans lequel on souhaite mettre des objets différents caractérisés par un poids et une valeur pécunière.

Le sac à dos peut supporter un poids maximal de 46 kg. Sélectionner les objets dans la liste suivante, de manière à ce que :
  • - La somme des poids des objets sélectionnés soit inférieure à 46 kg.
  • - La somme des valeurs des objets sélectionnés soit la plus grande possible.

Essais restants : 2

Exercice 2 : Algorithme glouton et rendu de monnaie

Une caisse dispose des pièces et des billets suivants : 100;50;25;20;1.
On a autant de pièces et de billets que nécessaire.

Lors d'un achat, un caissier doit rendre 43 € à un client.

En utilisant l'algorithme glouton, compléter le tableau ci-dessous, qui répertorie les pièces et billets rendus par le caissier pour que le nombre d'éléments soit minimum :

{"header_left": ["Pi\u00e8ces et billets", "Nombre d'\u00e9l\u00e9ments rendus"], "data": [[100, 50, 25, 20, 1], ["?", "?", "?", "?", "?"]]}

Exercice 3 : Algorithme glouton et problème du sac à dos

On considère un sac à dos dans lequel on souhaite mettre des objets différents caractérisés par un poids et une valeur pécunière.

Le sac à dos peut supporter un poids maximal de 52 kg. Sélectionner les objets dans la liste suivante, de manière à ce que :
  • - La somme des poids des objets sélectionnés soit inférieure à 52 kg.
  • - La somme des valeurs des objets sélectionnés soit la plus grande possible.

Essais restants : 2

Exercice 4 : Algorithme glouton et rendu de monnaie

Une caisse dispose des pièces et des billets suivants : 100;75;40;20;1.
On a autant de pièces et de billets que nécessaire.

Lors d'un achat, un caissier doit rendre 217 € à un client.

En utilisant l'algorithme glouton, compléter le tableau ci-dessous, qui répertorie les pièces et billets rendus par le caissier pour que le nombre d'éléments soit minimum :

{"header_left": ["Pi\u00e8ces et billets", "Nombre d'\u00e9l\u00e9ments rendus"], "data": [[100, 75, 40, 20, 1], ["?", "?", "?", "?", "?"]]}

Exercice 5 : Algorithme glouton et problème du sac à dos

On considère un sac à dos dans lequel on souhaite mettre des objets différents caractérisés par un poids et une valeur pécunière.

Le sac à dos peut supporter un poids maximal de 26 kg. Sélectionner les objets dans la liste suivante, de manière à ce que :
  • - La somme des poids des objets sélectionnés soit inférieure à 26 kg.
  • - La somme des valeurs des objets sélectionnés soit la plus grande possible.

Essais restants : 2

Revenir au choix du niveau
Kwyk vous donne accès à plus de 8 000 exercices auto-corrigés en Mathématiques.
Nos exercices sont conformes aux programmes de l'Éducation Nationale de la 6e à la Terminale. Grâce à Kwyk, les élèves s'entraînent sur du calcul mental, des exercices d'arithmétique et de géométrie, des problèmes et des exercices d'application, des exercices d'algorithmique et de python, des annales du brevet des collèges et du baccalauréat. Nos exercices sont proposés sous forme de réponse libre et/ou de QCM.

Afin d'assurer un entraînement efficace et pertinent aux élèves, chaque exercice est généré avec des valeurs aléatoires. Les élèves peuvent s'entraîner grâce aux devoirs donnés sur Kwyk par leurs professeurs et aux devoirs générés par notre outil utilisant l'IA mais aussi grâce aux différents modules de travail en autonomie mis à disposition sur leur espace personnel. Pour les niveaux du collège, les élèves ont également accès à des cours constitués d'une partie théorique et d'une partie pratique.
Avec Kwyk, vous mettez toutes les chances du côté des élèves pour que les différents théorèmes, propriétés et définitions n'aient plus aucun secret pour eux.

En 2024, plus de 40 000 000 d'exercices ont été réalisés sur Kwyk en Mathématiques.
Exercices de Mathématiques : préparer les examens
Brevet des collèges | Baccalauréat
S'entraîner dans d'autres matières
Français | Physique-Chimie
False