Décomposer une somme en pièces de monnaie en python

bonjour,

qu'as-tu essayé?

Bonjour, pour le moment j'avais essayé quelque chose du genre:

def nb_rendus(somme, monnaie):
    solution = 0
    for piece in monnaie:
        if piece < somme:
            solution += 1
    for piece in monnaie:
        monnaie2 = monnaie[:]
        somme2 = somme
        while somme2 > 0 and len(monnaie2) != 0:
            somme2 -= monnaie2[-1]
            monnaie2 = monnaie2[:-1]
            solution += 1
    return solution

Je me doute que ça doit être très loin de la solution, mais j'avoue que pour le coup je rame un peu :-(

Je précise qu'on doit calculer avec nb_rendus(81, [1,5,10,25,50]), et en toute logique, on devrait obtenir le meme résultat dans la version récursive et itérative.

Merci d'avance pour votre aide, bien a vous

Bonjour,

Intuitivement, ton problème revient à explorer un arbre de recherche (on verra plus loin que c'est même un peu plus subtil), pour lequel la racine signifie que tu n'as encore utilisé aucune pièce/billet et chaque feuille correspond à une décomposition de somme étant donnés les pièces et billets disponibles. Chaque nœud correspond à une situation intermédiaire

Dans la version récursive, tu distingues le cas où la dernière pièce/le dernier billet ne fait pas partie de la décomposition (nb_rendus(somme, monnaie[-1])) et le cas où il/elle en fait partie (nb_rendus(somme-monnaie[-1], monnaie)). Tout se passe comme si tu partais des feuilles. C'est parfaitement correct, mais tu pourrais aussi raisonner en partant de la racine.

Modèle : Afin de rendre les choses plus claires, je vais supposer qu'on fait l'exploration en partant de la racine, à l'image d'un Branch and Bound au travers d'un arbre. Chaque nœud correspond à un contexte.

• Dans ton cas, un contexte est caractérisé par un couple (P, s), où :
  • P est la liste des pièces (non nécessairement distinctes) P (dont chaque élément est une valeur parmi {1, 2, 5, 10, 20, 50, 100, 200, 500}) encore disponibles
  • s est la somme des pièces déjà sélectionnées.
• Chaque contexte (P, s) engendre autant de sous-contextes qu'il contient de pièces ; pour chaque pièce p dans P on crée un sous context dédié (P', s') = (P - {p}, s + p).

Jusqu'à maintenant je parlais d'un arbre mais nous verrons plus loin que le "vrai bon" modèle repose plutôt sur une structure de DAG induite par un treillis d'inclusion (l'inclusion est un ordre partiel et donc induit un treills : P' est inclus dans P).

Parcours de l'espace de recherche : Étant donné ce modèle, on peut explorer toutes les décompositions possibles cet arbre de recherche en utilisant un parcours d'arbre (tree traversal). Comme le montre le lien précédent, il existe plusieurs ordres standards pour visiter un arbre (parmi beaucoup d'autres ordres). Dans ton cas, l'ordre de visite n'a aucune importance.

Coupes : On sait que si les pièces/billets consommés somment à une valeur supérieure à somme, alors rien de ce qu'on pourra faire par la suite n'aidera à trouver une décomposition (on sait déjà que c'est fichu). On n'a donc aucun intérêt à continuer à explorer ce qui se passe dans ce contexte (on parle de coupe). Rien ne t'oblige à faire une coupe, mais c'est évidemment très important pour accélérer le programme.

Retour au problème initial : Maintenant, revenons à la question initiale. Explorer un arbre en partant de sa racine est assez naturel : on fait une récursion sur les enfants du nœud courant, et l'appel récursif initial est appliqué au nœud racine. La question posée dans le message initial revient donc à explorer un arbre avec un algorithme itératif.

Exploration itérative naïve : La manière la plus naïve d'explorer un arbre de profondeur 3, on écrirait quelque chose du genre :

contexte = ...
for i in choix_possibles(contexte):
  contexte_i = ... # dépend de contexte et de i
  for j in choix_possibles(contexte_i):
    contexte_ij = ... # dépend de contexte_i et de j
    for k in choix_possibles(contexte_ij):
      contexte_ijk = ... # dépend de contexte_ij et de k

On voit rapidement qu'une telle structure d'algorithme pose plusieurs problèmes

• il faut connaître la profondeur maximale de l'arbre (et dans ton cas on ne l'a connaît pas)
• l'implémentation dépend de cette profondeur (ce qui est très mauvais !)

Exploration itérative réaliste :

Pour contourner le problème de manière itérative, on a recours à une structure auxiliaire (une file, une pile, ou un ensemble) qui montre les contextes qu'il reste à explorer. En admettant qu'on parte de la racine :

• Ici, on initialise la structure auxiliaire avec le contexte initial (E0, s0) 
  • E0 = la liste des pièces / billets disponibles
  • s0 = 0
• À chaque itération, on retire de la structure auxiliaire un contexte arbitraire (E, s) où E est l'ensemble des pièces disponibles et s la somme actuellement accumulées.
  • Pour chaque pièce / billet p actuellement disponible
    • On construit le nouveau contexte obtenu en sélectionnant cette pièce ou ce billet :
      • E' = E \ p
      • s' = s + p
    • On insère (E', s') dans la structure auxiliaire

Passage à l'échelle

1) Le premier problème inhérente à P. On veut pouvoir stocker plusieurs exemplaires d'une même pièce (donc set n'est pas adapté), mais on veut se rendre compte que [2, 1, 1], [1, 2, 1] et [1, 1, 2] correspondent toutes les trois à la même situation (donc list n'est adapté non plus).

En programmation, la structure adéquate est un multiset. Contrairement à set, multiset n'existe pas nativement en python, mais on peut assez facilement avoir une structure qui se comporte comme un multiset :

class multiset(list):
    def __init__(self, values):
        super().__init__(sorted(values))
    def add(self, x):
        self.append(x) 
        self.sort()

def test_multiset():
    s1 = multiset([1, 1, 2])
    s2 = multiset([1, 2, 1])
    print(s1, s2) # [1, 1, 2] [1, 1, 2]
    assert s1 == s2, f"{s1} == {s2}"

    s1.add(4)
    s1.add(4)
    s1.add(3)
    print(s1, s2)  # [1, 1, 2, 3, 4, 4] [1, 1, 2]
    assert s1 != s2, f"{s1} != {s2}"

    s1.remove(4)
    s1.remove(4)
    s1.remove(3)
    print(s1, s2)  # [1, 1, 2] [1, 1, 2]
    assert s1 == s2, f"{s1} == {s2}"

test_multiset()

Remarque : une implémentation plus efficace serait de faire une dichotomie pour trouver où insérer/supprimer x mais ici ce n'est pas le cœur de la question donc je fais l'implémentation la plus simple possible.

2) Le second problème de passage à l'échelle est inhérent à l'exploration du treillis.

En effet, On peut croiser au cours des itérations plusieurs situations identiques mais découvertes au travers de différents choix. Par exemple si P = [1, 1, 2], peu importe que je consomme la première pièce de 1 euro ou la deuxième pièce de 1 euros : dans les deux cas j'aboutis à P' = [1, 2]. Dit autrement, on peut aboutir à un même nœud (ici celui qui correspond à P=[1,2]) via différents chemins depuis la racine.

Pour régler ce problème, on pourrait utiliser set en tant que structure auxiliaire (notée dans le code to_process) afin d'éviter de mettre en plusieurs exemplaire un même contexte. Cependant, ça pose plusieurs problème. D'une part, un set nécessite des éléments hashable (ce qui oblige à préciser la méthode multiset.__hash__). D'autre part, cela ne résout pas complètement le problème de redondance, comme le montre le programme qui suit :

from pprint import pprint

class multiset(list):
    def __init__(self, values):
        super().__init__(sorted(values))
    def add(self, x):
        self.append(x)
        self.sort()
    def __hash__(self):
        return hash(tuple(self))

def sub_multisets(s: multiset):
    to_process = set()
    to_process.add(s)
    while to_process:
        s = to_process.pop()
        yield s
        for x in s:
            sub_s = multiset(s.copy())
            sub_s.remove(x)
            to_process.add(sub_s)
                      
ms = multiset([1, 1, 2, 5])
pprint(sorted(sub_multisets(ms)))

Résultat : on voit que certains sous multisets sont découverts plusieurs fois :-(

[[],
 [],
 [1],
 [1],
 [1],
 [1, 1],
 [1, 1, 2],
 [1, 1, 2, 5],
 [1, 1, 5],
 [1, 2],
 [1, 2, 5],
 [1, 5],
 [1, 5],
 [2],
 [2],
 [2, 5],
 [5]]

En effet, peut redécouvrir un contexte donné si on a fini de le traité mais qu'on le redécouvre plus tard. Pour régler ce problème de redondance, c'est très simple : on mémorise quels contextes sont déjà traités ou en cours de traitement. Si on les rencontre à nouveau, on les ignore. Note que c'est sur cette idée toute simple que sont construits :

• la programmation dynamique (qui permettent de mettre en cache les résultat intermédiaire d'un calcul récursif)
• les color maps dans un parcours de graphe (qui permettent de marquer les sommets déjà visités ou en cours de visite) 

En suivant cette logique, notre fonction sub_multisets devient :

from pprint import pprint

class multiset(list):
    def __init__(self, values):
        super().__init__(sorted(values))
    def add(self, x):
        self.append(x)
        self.sort()
    def __hash__(self):
        return hash(tuple(self))

def sub_multisets(s: multiset):
    seen = set()
    to_process = set()
    to_process.add(s)
    while to_process:
        s = to_process.pop()
        seen.add(s)
        yield s
        for x in s:
            sub_s = multiset(s.copy())
            sub_s.remove(x)
            if sub_s not in seen:
                to_process.add(sub_s)
              
ms = multiset([1, 1, 2, 5])
pprint(sorted(sub_multisets(ms)))

Résultat : chaque sous-multiset n'est vu découvert qu'une fois

[[],
 [1],
 [1, 1],
 [1, 1, 2],
 [1, 1, 2, 5],
 [1, 1, 5],
 [1, 2],
 [1, 2, 5],
 [1, 5],
 [2],
 [2, 5],
 [5]]

Retour à la question initiale

Pour répondre à ton problème, il suffit de s'inspirer de l'exploration conduite par sub_multisets ; en particulier il faut :

• adapter les contextes mémorisés dans to_process (pour prendre en compte la somme accumulée)
• contrôler si un sous-multiset est digne d'intérêt :
  • si la somme accumulée dépasse somme, on peut l'ignorer (critère de coupe) ;
  • si on a déjà vu ce contexte, on peut l'ignorer (cf sub_multiset) ;
• contrôler si la somme accumulée coïncide avec somme. Dans ce cas, l'ensemble de départ privé du multiset courant est une décomposition.

Bonne chance

@Yg_be:
Si j'ai bien compris ton idée, il y aura des sommes de C[i]*P[i] ... qui ne seront pas égales à la somme désirée.
On peut le faire avec ce que j'appelle un "compteur kilométrique"
On peut modifier facilement pour obtenir ces combinaisons au lieu du nombre.
 

somme = 81
monnaie = [1, 5, 10, 25, 50]
limites = [somme // c for c in monnaie]
n = len(monnaie)
comptes = [0] * n
i = 0
resultat = 0
while True:
    #essai = sum(monnaie[k] * comptes[k] for k in range(n))
    essai = sum(m * c for m, c in zip(monnaie, comptes))
    if essai == somme:
        resultat += 1
    i = 0
    while i < n and comptes[i] == limites[i]:
        comptes[i] = 0
        i += 1
    if i >= n: break
    comptes[i] += 1
print(resultat)

En m'inspirant de ce qui a été mentionné plus haut au sujet des arbres de décision, je considère ce qui suit:
D'abord je trie les devises en ordre descendant de valeur.

• Si je prends 50, j'ai deux possibilités: 0 et 1
• Pour 50 valant 1, j'aurai que 25 peut valoir 0 et 1 seulement
• Pour 50 valant 0, j'aurai que 25 peut valoir 0 , 1, 2, 3 etc.

Je remarque que les possibilités sont des entiers consécutifs commençant à 0.
Pour éviter de maintenir un tableau des valeurs limites, je pourrais donner les valeurs possibles en ordre descendant.
Voici ce que ça donne:
 

somme = 81
monnaie = [1, 5, 10, 25, 50]
monnaie.sort(reverse=True)
n = len(monnaie)
arbre = [0] * n
resultat = 0
i = 0
while True:
    while i < n:
        arbre[i] = somme // monnaie[i]
        somme = somme % monnaie[i]
        i += 1
    i -= 1
    somme += arbre[i] * monnaie[i]   # Restaurer l'ancienne valeur, on est sur une feuille.
    resultat += 1
    i -= 1
    while i >= 0 and arbre[i] == 0: i -= 1
    if i < 0: break
    somme += monnaie[i]
    arbre[i] -= 1
    i+=1
print(resultat)

J'ai trouvé une solution encore plus rapide sur un autre forum (ça n'est pas de moi):
 

def nb_rendu(somme, monnaie):
    dp = [0] * (somme + 1)
    dp[0] = 1
    for piece in monnaie:
        for montant in range(piece, somme + 1):
            dp[montant] += dp[montant - piece]
    return dp[somme]
 
somme =900
monnaie=range(1,10)
print(nb_rendu(somme, monnaie))