#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Nov 15 21:33:20 2023

@author: leprince
"""

from numpy import inf


listePieces = [1,2,5,10,20,50,100,200,500]


def renduMonnaieGlouton(listePieces,S):
    #on suppose que S est un entier
    nombrePieces = len(listePieces)
    listeRendu = [0 for i in range(nombrePieces)]
    SommeRestant = S
    i = nombrePieces - 1
    while i >= 0 and ... : #i>=0 superflu si on est sûr 
                                      # que l'on peut rendre pile S
                                      #ce qui est le cas ici
        val = listePieces[i]
        k = 0 # nombre de pièces de valeur val 
              # que l'on peut mettre dans SommeRestant
        while ....
            .....
        listeRendu[i] = ....
        SommeRestant = ....
        i -= 1
    return listeRendu

print(renduMonnaieGlouton(listePieces,45))


def renduMonnaieMemo(listePieces,SommeTotale):
    nombrePieces = len(listePieces)
    dico = {}
    
    def remplitDico(i,S):
        """ i entier >0 ; S entier>=0
        Résoud le problème (et place la solution dans dico[(i,S)])
        pour la somme S avec la liste de pièces listePieces[:i]
        """
        if not ...:
            if S == 0:
                dico[(i,S)] = ...
            elif i == 1 : 
                dico[(i,S)] =...
            else:  
                val = listePieces[i-1]
                nombrePiecesMini = inf
                k = 0
                while S-k*val >=0 :
                    remplitDico(...,...)
                    if ... :
                       nombrePiecesMini = ....
                    k += 1
                dico[(i,S)] = ....
    remplitDico(....,....)
    return dico[(nombrePieces,SommeTotale)]
                    
print(renduMonnaieMemo(listePieces,345))

def renduMonnaieMemoAvecListe(listePieces,SommeTotale):
    ...
    
    
    
    
    return dico[(nombrePieces-1,SommeTotale)]
                    
print(renduMonnaieMemoAvecListe(listePieces,345))


#test sur un exemple ou l'algorithme glouton 
#ne donne pas la meilleure solution

listePieces2 = [1,4,6]
print(renduMonnaieGlouton(listePieces2,8))
print(renduMonnaieMemoAvecListe(listePieces2,8))