# Exemple 1:
# Question 1 :
# Stratégie gloutonne :  O -> E -> B -> A -> C -> F -> D
# Distance parcourrue = 5 + sqrt(29) ~= 10,4
# 
# Question 2 :
# Stratégie optimale :  O -> D -> E -> B -> A -> C -> F
# Distance parcourrue = 2 + sqrt(5) + 4 ~= 8,2

# Exemple 2:
# Question 1 :
# 20, 19, 16, 15, 14
# Question 2 : Elle est valide.
# Question 3 : LA solution gloutonne n'est pas optimale.

# -----------------------------------------------------------------------------------------------------------------
# Exercice 1 : le problème du rendu de monnaie
# -----------------------------------------------------------------------------------------------------------------

# Question 1

def rendu_glouton(somme_a_rendre, pieces):
        solution = []
        i = 0  # i est l'indice de la pièce à tester
        while somme_a_rendre > 0:
            if pieces[i] <= somme_a_rendre: 
                solution.append(pieces[i])
                somme_a_rendre = somme_a_rendre - pieces[i]
            else:
                i = i + 1
        return solution

assert rendu_glouton(147, [500, 200, 100, 50, 20, 10, 5, 2, 1]) == [100, 20, 20, 5, 2]
assert rendu_glouton(17, [500, 200, 100, 50, 20, 10, 5, 2, 1]) == [10, 5, 2]

# Question 2

assert rendu_glouton(8, [6, 4, 1]) == [6, 1, 1]
# Notre algorithme n'est pas optimal car il rend 3 pièces : 6, 1 et 1 alors que 2 pièces auraient suffi : 4 et 4



# -----------------------------------------------------------------------------------------------------------------
# Exercice 2 : Le problème du sac à dos (version Lupin)
# -----------------------------------------------------------------------------------------------------------------

# Question 1

objets = [['A', 7, 9100], ['B', 6, 7200], ['C', 4, 4800], ['D', 3, 2700], ['E', 2, 2600], ['F', 1, 200]]

def taux_de_valeur(objet):
    return objet[2]/objet[1]
    
assert taux_de_valeur(['B', 6, 7200]) == 1200.0

# Question 2 

objets_tries =  sorted(objets, key = taux_de_valeur, reverse=True)

# Question 3

def sac_a_dos_glouton(objets, poids_max):
    
    # Fonction clé pour le tri
    # (on peut l'écrire ici ou à l'extérieur de la fonction)
    def taux_de_valeur(objet):
        return objet[2]/objet[1]
    
    # Tri des objets
    objets_tries = sorted(objets, key = taux_de_valeur, reverse=True)
    
    # Algorithme glouton
    sac = []
    poids_sac = 0
    for objet in objets_tries:
        poids_objet = objet[1]
        if poids_sac + poids_objet <= poids_max:
            sac.append(objet)
            poids_sac = poids_sac + poids_objet
    return sac
    
# Question 4

assert sac_a_dos_glouton(objets, 10) == [['A', 7, 9100], ['E', 2, 2600], ['F', 1, 200]]

# Question 5
# Avec les objets B et C, le sac a dos de 10 kilo est plein pour une valeur de 12000,
# alors que notre algorithme renvoie une solution avec une valeur de 11900.
# Notre algorithme n'est donc pas optimal.