1) Problème du rendu de monnaie

L’objectif de cette partie est de programmer le problème du rendu de monnaie avec l’algorithme glouton vu en classe.

1) Créer dans une liste nommée euros le système de pièces utilisées dans les pays ayant adopté l'euro. On choisira de trier la liste dans un ordre pertinent.
2) Ecrire une fonction qui renvoie dans une liste, initialement vide, les pièces rendues. Cette fonction a pour prototype def rendu_monnaie(somme_a_rendre, systeme_monnaie).
3) En testant votre fonction sur des exemples significatifs, vérifier l’optimalité de la solution donnée par la fonction.
4) Avant sa réforme en 1971, le Royaume-Uni utilisait le système {1, 3, 6, 12, 24, 30}.
Tester le rendu de monnaie pour 49. La solution proposée est-elle optimale?

2) Problème du sac à dos

Nous disposons d’une clé USB qui est déjà bien remplie et sur laquelle il ne reste que 5 Go de libre.

Nous souhaitons copier sur cette clé des fichiers vidéos pour l’emporter en voyage. Chaque fichier a une taille et chaque vidéo a une durée. La durée n’est pas proportionnelle à la taille car les fichiers sont de formats différents, certaines vidéos sont de grande qualité, d’autres sont très compressées.

Le tableau qui suit présente les fichiers disponibles avec les durées données en minutes.

Nom	Durée en min (valeur)	Poids
Vidéo A	114	4.57 Go
Vidéo B	32	630 Mo
Vidéo C	20	1.65 Go
Vidéo D	4	85 Mo
Vidéo E	18	2,15 Go
Vidéo F	80	2,71 Go
Vidéo G	5	320 Mo

Quelles vidéos copier sur la clé USB pour que la durée des vidéos soient la plus grande possible tout en ne dépassant pas 5 Go ?

1) Comment représenter les données du tableau précédent ? On précisera le nom exact de la structure choisie.
2) Proposer un algorithme pour résoudre le problème, et le programmer en Python.