# Algorithmes Gloutons :

# Rendu de monnaie :
# Monnaie à rendre : entre 1 € et 100 € (100 cas à tester)
# Que se passe-t-il s'il manque 1 type de pièces parmi [1,2,5,10,20,50] ?
# Le système [1,3,5,10,30,50] est-il cononique ?
# (l'algorithme glouton est-il optimal pour les 100 cas à rendre) ?

pieces=[1,2,7,10,20,70]
total_pieces=0
for a_rendre in range(1,100+1,1):
    print("=================================")
    print("Monnaie a rendre : %s €" % a_rendre)
    reste=a_rendre
    while (reste!=0):
        for p in pieces[::-1]:
            if p<=reste:
                piece_rendue=p
                break
        reste=reste-piece_rendue
        print("Pièce rendu :",piece_rendue)
        total_pieces+=1

print("===========================================")
print("Nombre total de pièces rendu pour les 100 cas : %d pièces rendues" % total_pieces)



# Problème du sac à dos :
objets=[(4,12),(2,2),(2,1),(1,1),(10,4)]
poids_maxi=15