# ALGO6 : TD6
###### tags: `algo` `2021`

## Exercice 1 : Algorithme glouton : le cas des euros
En euros, les valeurs de v sont (1, 2, 5, 10, 20, 50, 100, 200, 500)

1. Proposer une solution optimale et une solution non-optimale pour rendre 8 euros.
* Solution optimale :
8 = 5 + 2 + 1

* Solution non-optimale :
8 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2. Proposer une solution pour rendre 143 euros. Est-elle optimale ?
143 = 100 + 20 + 20 + 2 + 1
Cette solution est optimale car il n'est pas possible de rendre moins de monnaie.

3. Proposer un algorithme simple pour rendre la monnaie.

* On parcourt toutes les valeurs de v en partant de la plus grande.
* On compare la valeur que l'on prend avec le rendu.
* Si on peut mettre la valeur dans le rendu, on l'ajoute au rendu, sinon on passe à la prochaine valeur.
* Cet algorithme peut se répeter sur les mêmes valeurs de v pour rajouter par exemple 2 billets de 20.

rendu(value):
    T = [1, 2, 5, 10, 20, 50, 100, 200, 500]
    resultat = []
    i = T.size
    while(i >= 0 && value != 0):
        if(value - T[i] >= 0):
            jet.add(T[i])
            value -= T[i]
        else 
            i--
    return jet

* truc avec la division euclidienne c'est chelou

for i -> 0:
    nombre(1) = N / v[i]
    N = N - nombre[i] v[i]
print nombre

4. Cet algorithme rend-il une solution optimale (dans le cas du rendu d’euros) ?
* Oui car il commence par les plus grandes valeurs et retourne donc un nombre minimal de pièces.

5. Quelle est la complexité de votre algorithme ?
* On peut trouver un majorant de l'algorithme. Donc :
nombre_soustraction ≤ n/200.
* Ou bien, il faut utiliser la division euclidienne. Ce qui donne :
comp ≤ nombre(valeurs)

## Exercice 2 : Systèmes canoniques
1. On suppose que v = (1, 3, 4). L’algorithme développé à l’exercice précédent rend-il une solution optimale ?

Non, par exemple pour 6 :
* L'algo donne : [4, 1, 1]
* Résultat optimal : [3, 3]

Ou pour 9 :
* L'algo donne [4, 3, 1, 1]
* L'optimal est [3, 3, 3]

2. On suppose que v = (1, 4, 9). L’algorithme développé à l’exercice précédent rend-il une solution optimale ?

Non, par exemple pour 12 :
* L'algo donne : [9, 1, 1, 1]
* Résultat optimal : [4, 4, 4]

## Exercice 3 : Énumération
1. Soit v = {1, 5, 6, 9, 20}. Calculer un rendu de monnaie optimal pour x = 17.
* [6,6,5]

2. Écrire un algorithme prenant en entrée un entier x et un vecteur v = (v1, . . . , vn) qui retourne le nombre minimal de pièces à rendre pour obtenir x. Cette algorithme utilisera une énumération de parties.

rendu2(N, i):
    si N < 0 ou i < 0: return +inf
    si N == 0: return 0
    return min(1 + rendu2(N - V[i], i), rendu2(N, i - 1))

3. Quelle est la complexité de votre algorithme ?
O($\infty$) :scream: :tent:
Sacré complexité -> oui

4. Si ce n’est pas fait, utiliser de la programmation dynamique pour améliorer votre algorithme