Gloutons : 2. TD #

pdf pour impression

1. Le problème du sac à dos #

Un cambrioleur possède un sac à dos d’une contenance maximum de 30 kg. Au cours d’un de ses cambriolages, il a la possibilité de dérober 4 objets A, B, C et D. Voici un tableau qui résume les caractéristiques de ces objets :

On ajoute les contraintes suivantes :

• le sac à dos a une contenance de 30 kg
• le cambrioleur cherche à obtenir un gain maximum.

1. Déterminez les objets que le cambrioleur aura intérêt à dérober.

2. Quel critère pourrait-on choisir pour trier les objets ? Proposer un algorithme glouton pour résoudre le problème du sac à dos.

3. Retourne-t-il la solution optimale ?

4. Reprendre le problème avec les objets suivants :

   objet	A	B	C	D
   masse	35 kg	41 kg	28 kg	39 kg
   valeur marchande	70 €	40 €	30 €	30 €

   a. Si le sac peut contenir 100 kg, b. Si le sac peut contenir 85 kg.

5. Écrire une fonction Python qui calcule les valeurs massiques d’une liste d’objets passés en paramètre.

6. Écrire une fonction Python qui renvoie le contenu d’un sac à dos depuis une liste d’objets et une contenance de sac à dos passés en paramètres. Cette fonction utilisera l’algorithme glouton présenté plus haut.

2. Le rendu de monnaie. #

On considère un jeu de pièce et une somme à rendre. Nous allons étudier deux situations générales, pour lesquelles l’algorithme glouton retourne la solution optimale ou non.

1. On considère un jeu de pièce similaire à l’euro : 1 cts, 2 cts, 5 cts, 10 cts, 20 cts, 50 cts, 1 €, 2 €, 5 €, 10 €, 20 €, 50 €, 100 €, 200 €.

   Rappeler l’algorithme glouton qui renvoie les pièces à rendre sous la forme d’une liste à partir d’un jeu de pièces et d’un montant passés en paramètres.

2. Donner les étapes pour le rendu de 71€73

3. Écrire une fonction Python qui traite le problème exposé à la question précédente.

Cette fonction retourne toujours une réponse mais celle-ci n’est pas forcement la meilleure.

3. Proposer un algorithme qui teste toutes les combinaisons possibles et renvoie la meilleure.

4. Comparer les complexités de deux algorithmes : glouton et exhaustif.

3. Somme de $n$ nombres maximale #

On cherche à sélectionner cinq nombres de la liste suivante en maximisant leur somme et en s’interdisant de choisir deux nombres voisins.

Ainsi, si la liste contient la séquence 1, 2, 3, et qu’on choisit 2, il ne sera plus possible de choisir 1 ou 3.

Liste = 15, 4, 20, 17, 11, 8, 11, 16, 7, 14, 2, 7, 5, 17, 19, 18, 4, 5, 13, 8

1. Décrire une stratégie gloutonne pour résoudre ce problème.
2. Mettre en oeuvre cette stratégie sur cet exemple.
3. Vérifier que 20, 18, 17, 16, 15 est une solution acceptable.
4. Comparer ces solutions.

4. Retour sur le voyageur de commerce #

à traiter après avoir étudié le problème en TP machine

On rappelle rapidement le principe du problème :

Un voyageur a ciblé plusieurs villes qu’il souhaite visiter. Il cherche un itinéraire passant par toutes ces villes, depuis un point de départ et revenant à la ville de départ. Il ne doit passer qu’une et une seule fois par chaque ville.

Par exemple : Nancy, Metz, Paris, Reims, Troye, Nancy est un trajet possible.

1. Décrire la stratégie gloutonne.
2. Mettre en oeuvre la stratégie et mesurer la distance parcourue.
3. Comparer à : Nancy, Metz, Reims, Paris, Troyes, Nancy.
4. Estimer le nombre de trajets possibles (départ & retour à Nancy).

5. Le parc d’attractions #

Vous visitez un parc d’attractions proposant des spectables à différents horaires. Voici les horaires des spectacles :

Vous avez remarqué qu’il n’était pas possible d’assister à tous les spectacles puisque certains ont lieu à des moments communs; Vous souhaitez assister à un maximum de spectacles. Quels spectacles choisir ?

Voici deux stratégies gloutonnes possibles :

• Stratégie 1 : choisir le spéctacle dont l’heure de début arrive le plus tot parmi les spectacles dont l’heure de début est postérieure à l’heure de fin des spectacles déjà choisis. Cette stratégie minimise le temps d’attente.
• Stratégie 2 : choisir le spectacle dont l’heure de fin arrive le plus tôt parmi les spectacles dont l’heure de début est postérieure à l’heure de fin des spectacles déjà choisis. Cette stratégie maximise le temps restant aux autres spectacles.

1. Appliquer ces deux stratégies aux données.
2. Laquelle est la meilleure ?

Remarque théorique : la seconde stratégie gloutone donne toujours la meilleure solution.