#!/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 SommeRestant > 0: #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 k*val <= SommeRestant:
            k += 1
        listeRendu[i] = k-1
        SommeRestant -= (k-1)*val
        i -= 1
    return listeRendu

print(renduMonnaieGlouton(listePieces,345))


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 (i,S) in dico:
            if S == 0:
                dico[(i,S)] = 0
            elif i == 1 : 
                dico[(i,S)] = S
            else:  
                val = listePieces[i-1]
                nombrePiecesMini = inf
                k = 0
                while S-k*val >=0 :
                    remplitDico(i-1,S-k*val)
                    if dico[(i-1,S-k*val)] + k < nombrePiecesMini :
                       nombrePiecesMini = dico[(i-1,S-k*val)] + k
                    k += 1
                dico[(i,S)] = nombrePiecesMini
    remplitDico(nombrePieces,SommeTotale)
    return dico[(nombrePieces,SommeTotale)]
                    
print(renduMonnaieMemo(listePieces,345))

def renduMonnaieMemoAvecListe(listePieces,SommeTotale):
    nombrePieces = len(listePieces)
    dico = {}
    
    def remplitDico2(i,S):
        # i entier >0 ; S entier>=0
        if not (i,S) in dico:
            if S == 0:
                dico[(i,S)] = 0 , [0 for _ in range(nombrePieces)]
            elif i == 1 : 
                dico[(i,S)] = S , [S] + [0 for _ in range(nombrePieces-1)]
            else:  
                val = listePieces[i-1]
                nombrePiecesMini = inf
                k = 0
                while S-k*val >=0 :
                    remplitDico2(i-1,S-k*val)
                    if dico[(i-1,S-k*val)][0] + k < nombrePiecesMini :
                       nombrePiecesMini = dico[(i-1,S-k*val)][0] + k
                       kmin = k
                    k += 1
                liste = dico[(i-1,S-kmin*val)][1][:] #copie terme à terme
                liste[i-1] = kmin
                dico[(i,S)] = nombrePiecesMini , liste
                
    remplitDico2(nombrePieces,SommeTotale)
    return dico[(nombrePieces,SommeTotale)]
                    
print(renduMonnaieMemoAvecListe(listePieces,114))


#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))