un principe glouton.

Le problème

On dispose de pièces (en quantités non limitées) de valeurs faciales entières \( v_0 > v_1 > ... > v_n \). On cherche à payer une somme S (entière) avec le minimum de pièces possibles.

Exemple :

on veut payer S = 32 € en disposant de pièces de valeurs faciales v₀ = 10 €, v₁ = 5 €, v₂ = 2 € et v₃ = 1 € (on dispose de quantités non limitées de pièces) : on utilisera le minimum de pièces possibles en utilisant trois pièces de 10 et une pièce de 2.

Un algorithme glouton

Dans un premier temps, on met en place un algorithme glouton :

on donne une pièce de plus grande valeur faciale V possible sans dépasser la somme S.
S est mise à jour (S reçoit S-V).
on reprend au point 1 tant qu'on peut.

On supposera que l'on dispose toujours de pièces de valeur faciale 1 (ce qui garantit que toute somme entière est réalisable).

Donner une version récursive de cette fonction gloutonne.

Entrée	la somme à atteindre (entier naturel), une liste des valeurs faciales disponibles (liste d'entiers naturels).
Sortie	Une liste donnant le nombre de pièces à utiliser pour chaque valeur faciale.

un code
version itérative


 
def monnaie(somme_a_payer, liste_faces_dispo) :
    """ 
        somme_a_payer : 
        de type entier, c'est la somme à payer.
        
        liste_faces_dispo : 
        liste des valeurs faciales des pièces disponibles en ordre décroissant, 
        Le dernier élément de liste_faces_dispo vaut 1, 
        ceci garantit que le cas de base "somme == 0" 
        sera toujours atteint.
        
        liste_solution : 
        liste des nombres de pièces utilisées pour chacune des valeurs faciales
        pour payer la somme désirée.
        
        j : 
        indice permettant de parcourir la liste liste_faces_dispo.
        
        Exemple :
        Pour payer somme = 14 en disposant des valeurs faciales liste_faces_dispo = [10,5,2,1],
        on utilisera liste_solution = [1,0,2,0]  (une pièce de 10 et deux pièces de 2).
        
    """ 
    liste_solution = [0 for x in liste_faces_dispo]
    
    def money(somme, j) :
        if somme == 0 : return liste_solution 
        
        elif liste_faces_dispo[j] > somme : return money(somme, j+1)
        
        else :
            liste_solution[j] += 1
            return money(somme - liste_faces_dispo[j],  j)
        
    return money(somme_a_payer, 0)
    
    
def affiche_solution(somme_a_payer, liste_faces_dispo) :
	liste_solution = monnaie(somme_a_payer, liste_faces_dispo)
	print( "Pour payer la somme de {} \u20AC, on utilisera : ".format(somme_a_payer) )
	for i, s in enumerate(liste_solution) :
		print( "{} pièces de {} \u20AC.".format(s, liste_faces_dispo[i]) )
    
 
affiche_solution(32, [10,5,2,1])

Le principe précédent est un simple principe de division euclidienne, d'où la version itérative suivante :


def monnaie(somme_a_payer, liste_faces_dispo):
    
    liste_solution = []
    
    for m in liste_faces_dispo :
        liste_solution.append(somme_a_payer//m)
        somme_a_payer %= m
        
    return liste_solution
    
    
def affiche_solution(somme_a_payer, liste_faces_dispo) :
	liste_solution = monnaie(somme_a_payer, liste_faces_dispo)
	print( "Pour payer la somme de {} \u20AC, on utilisera : ".format(somme_a_payer) )
	for i, s in enumerate(liste_solution) :
		print( "{} pièces de {} \u20AC.".format(s, liste_faces_dispo[i]) )
    
 
affiche_solution(32, [10,5,2,1])

correction de la version gloutonne.

L'algorithme glouton utilisé précédemment donne-t-il toujours une solution optimale ?

un exemple non optimal
une liste faciale optimale

Il est facile de voir que l'algorithme ne mène pas toujours à une solution optimale.

Prenons par exemple la situation suivante : on dispose de pièces de valeurs faciales 18, 7, 1. Pour payer 21 €, l'algorithme trouvera une solution en quatre pièces : une de 18 et trois pièces de 1. Mais il est clair qu'une solution avec trois pièces existe : trois pièces de 7.

Avec un système classique : des pièces de 10, de 5 de 2 et de 1, l'algorithme est optimal.

Justification.

Une solution optimale utilise :

au plus une pièce de 5 € (sinon on remplace 2 pièces de 5 € par une pièce de 10 €),
au plus 2 pièces de 2 € (sinon on remplace 3 pièces de 2 € par une de 5 € + une de 1 € ),
au plus 1 pièce de 1 € (sinon on remplace 2 pièces de 1 € par une pièce de 2 €).

La somme payée avec les pièces de 1 €, 2 €, 5 € est donc d’au plus 1 + 2 × 2 + 5 = 10 €.
Elle ne vaut pas 10 € (sinon on remplace par une pièce de 10 €).
Elle vaut donc au plus 9 €.
Soit q le nombre de pièces de 10 € utilisées dans une solution optimale. On a : somme à payer = 10 q + somme payée par les pièces de 1, 2, 5.
Comme cette somme payée par les pièces de 1, 2, 5 vaut au plus 9, on a \( q = \lfloor \frac{\text{somme à payer}}{10} \rfloor \) (quotient dans la division par 10 de la somme à payer), c'est à dire le nombre calculé par l’algorithme glouton.

Le même raisonnement montre que le nombre de pièces de 5, de 2, de 1 d'une solution du problème est également le nombre de pièces déterminé par l'algorithme, qui est donc correct dans ce cas.

programme pour les cas où la procédure gloutonne n'est pas correcte.

Donner une fonction python récursive valable également lorsque le principe glouton ne l'est plus.

Entrée	la somme à atteindre (entier naturel), une liste des valeurs faciales disponibles (liste d'entiers naturels).
Sortie	Une liste donnant le nombre de pièces à utiliser pour chaque valeur faciale.

code partiel
un code complet
avec mémorisation

Dans ce premier code, on ne calcule que le nombre minimal de pièces sans donner le nombre à utiliser pour chacune des faces.


def nombre_de_pieces_utilisees(somme_a_payer, liste_faces) :
    # avec somme_a_payer pièces de 1, on peut 
    # réaliser la somme :
    nombre_min = somme_a_payer  
    
    if somme_a_payer in liste_faces : return 1
    else :
        for p in [f for f in liste_faces if f <= somme_a_payer] :
            nombre_pieces = 1 + nombre_de_pieces_utilisees(somme_a_payer - p,  liste_faces)
            if nombre_pieces < nombre_min :  nombre_min = nombre_pieces
    return nombre_min
        
        
def affiche_reponse(somme_a_payer, liste_faces) :
	
	print( "Avec les valeurs faciales {},".format(liste_faces) ) 
	print(" on paie la somme {} avec un minimum de {} pièces.".format(somme_a_payer, nombre_de_pieces_utilisees(somme_a_payer, liste_faces)) )      
 
 
affiche_reponse(21,[18,7,2,1])

Dans ce second code, on calcule et affiche le détail.

On constate que le second calcul est assez long : à vous de comprendre pourquoi et de proposer une amélioration.


def monnaie(somme_a_payer, liste_faces) :
    
    # réalisation de la somme_a_payer avec des pièces de 1 : 
    nombre_min = somme_a_payer 
    solution = []
   
    if somme_a_payer in liste_faces : 
        return ( 1, [somme_a_payer] )
    else :
        
        for p in [f for f in liste_faces if f <= somme_a_payer] :
            a = monnaie(somme_a_payer - p,  liste_faces)
            nombre_pieces = 1 + a[0]
            pieces_utilisees = a[1] + [p]
            
            if nombre_pieces < nombre_min :  
                nombre_min = nombre_pieces
                solution = pieces_utilisees
                
    return (nombre_min, solution)

def affiche_solution(somme_a_payer, liste_faces) :
    solution = monnaie(somme_a_payer, liste_faces)
    print("Pour payer la somme {} avec les valeurs faciales {},".format(somme_a_payer, liste_faces))
    print("on utilise un total de {} pièces.".format(solution[0]))
    for x in liste_faces :
        if x in solution[1] :
            print( "{} pièces de {} \u20AC.".format( solution[1].count(x), x ) )
            
            
affiche_solution(21, [18,7,1])
print()
affiche_solution(32, [10, 5, 2, 1])

La lenteur du code précédent est notamment due au fait que l'on calcule plusieurs fois les mêmes valeurs lors des appels récursifs.

Dressons par exemple le début de l'arbre des appels avec la somme 21 et la liste de pièces disponibles [10,5,1] :
début arbre des appels
On constate déjà sur ce début d'arbre que la fonction sera appelée plusieurs fois avec la valeur 11.

Une façon d'améliorer cela est de mémoriser les calculs déjà faits afin de ne pas les refaire (voir le sujet fibonacci à ce sujet).


def money(somme_a_payer, liste_faces) :

	# dictionnaire d'enregistrement des calculs déjà effectués :
	resultats = {}
	
	def monnaie(somme_a_payer, liste_faces) :
		
		# réalisation de la somme_a_payer avec des pièces de 1 : 
		nombre_min = somme_a_payer 
		solution = []
		
		if  somme_a_payer in resultats :
			return resultats[somme_a_payer]
			
		else :
			if somme_a_payer in liste_faces : 
				resultats[somme_a_payer] = ( 1, [somme_a_payer] )
				return resultats[somme_a_payer]
			else :
				
				for p in [f for f in liste_faces if f <= somme_a_payer] :
					a = monnaie(somme_a_payer - p,  liste_faces)
					nombre_pieces = 1 + a[0]
					pieces_utilisees = a[1] + [p]
					
					if nombre_pieces < nombre_min :  
						nombre_min = nombre_pieces
						solution = pieces_utilisees
						 
			resultats[somme_a_payer] = (nombre_min, solution)	
			return resultats[somme_a_payer]
		
	return monnaie(somme_a_payer, liste_faces)

def affiche_solution(somme_a_payer, liste_faces) :
    solution = money(somme_a_payer, liste_faces)
    print("Pour payer la somme {} avec les valeurs faciales {},".format(somme_a_payer, liste_faces))
    print("on utilise un total de {} pièces.".format(solution[0]))
    for x in liste_faces :
        if x in solution[1] :
            print( "{} pièces de {} \u20AC.".format( solution[1].count(x), x ) )
            
            
affiche_solution(21, [18,7,1])
print()
affiche_solution(32, [10, 5, 2, 1])