Aide pour un exercice sur un algorithme "glouton"
Bonjour, je suis étudiant à l'université et j'ai un exercice à réaliser que je ne comprends absolument pas... Pourriez-vous m'aider ? Voici l'énoncé, la moindre explication, aide serait la bienvenue !
Soit n le nombre de pièces distinctes et soit P, un tableau, dont les indices vont de 1 à n contenant la valeur des n pièces. On suppose ici que nous disposons d'un nombre illimité de chaque type de pièce. Soit L le montant dont on veut obtenir la monnaie. Dans ce problème, les valeurs des pièces sont strictement positives. Le montant à remettre est un nombre entier non négatif. On assume que le tableau P est en ordre croissant.
Nous allons utiliser une matrice C de n lignes numérotées de 1 à n et L + 1 colonnes numérotées de 0 à L où C[i,j] contient le nombre minimal de pièces pour rendre la monnaie d'un montant j si l'on se limite seulement qu'aux pièces de valeurs P1,P2, ... , Pi. Si la monnaie ne peut être rendue, C[i,j] sera égal à l'infini.
Les questions sont les suivantes :
- Donner une équation de récurrence pour C[i,j]. N'oubliez pas les cas de base. Aide : Complétez ce qui suit.
C[i,j] = ... si j = 0, ... si i = 1 et ... , ... si i = 1 et ..., ... si j < Pi, ... sinon.
- Décrivez en pseudo-code un algorithme de programmation dynamique pour calculer tous les éléments de la dernière ligne du tableau C, c’est-à-dire les C[n,j] pour 0 ≤ j ≤ L. Votre algorithme ne doit utiliser qu’un seul tableau à une dimension de longueur L + 1 et non pas un tableau à deux dimensions comme le tableau C.
- Donnez la complexité de votre algorithme en fonction de n et de L.
- Décrivez en pseudo-code un algorithme glouton capable de faire la monnaie en un nombre minimal de pièces une fois les C[n,j] calculés, pour un montant quelconque M ≤ L. Votre algorithme recevra donc en entrée la dernière ligne de la matrice C, le tableau P ainsi que le montant M. Votre algorithme donne-t-il toujours la solution optimale ?
- Donnez la complexité de l’algorithme trouvé en (d) en fonction de n.
Merci d'avance pour toute réponse qui puisse m'aider à résoudre cet exercice !
