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

Fermé
Mel13713 Messages postés 3 Date d'inscription dimanche 19 novembre 2017 Statut Membre Dernière intervention 16 mars 2023 - Modifié le 17 mars 2023 à 16:53
mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024 - 22 mars 2023 à 13:51

Bonjour,

J'aurais besoin d'aide pour un exercice que ne comprend pas du tout en python. Le but est de créer une fonction nb_rendus(somme, monnaie)monnaie est une liste contenant les pièces possibles et somme est une somme a atteindre. La fonction doit retourner le nombre de façons possibles d'atteindre cette somme avec les éléments de monnaie.

Par exemple, pour atteindre 7 avec des pièces de 1 et de 2 on peut faire:

1+1+1+1+1+1+1
2+1+1+1+1+1
2+2+1+1+1
2+2+2+1

donc nb_rendus(7, [1,2]) retourne 4. J'ai déjà la version récursive :

def nb_rendus1(somme, monnaie):
    if somme < 0 or len(monnaie) == 0:
        return 0
    if somme > 0:
        return nb_rendus(somme, monnaie[:-1]) + nb_rendus(somme-monnaie[-1], monnaie)
    return 1

... mais il me faut la version itérative, et après des heures de recherche, je peine à la trouver...

Merci d'avance pour votre aide :)

A voir également:

6 réponses

yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024 1 471
16 mars 2023 à 13:48

bonjour,

qu'as-tu essayé?

0
Mel13713 Messages postés 3 Date d'inscription dimanche 19 novembre 2017 Statut Membre Dernière intervention 16 mars 2023
Modifié le 17 mars 2023 à 13:08

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

0
yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024 1 471
16 mars 2023 à 16:59

J'imagine que le but de l'exercice, c'est que tu trouves un algorithme.

Comment ferais-tu si tu devais faire ce calcul sans ordi?

0
mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024 7 755
17 mars 2023 à 16:27

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

0
yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024 1 471
17 mars 2023 à 20:05

Tout cela me semble bien compliqué.

Nommons S la somme à atteindre, n le nombre de pièces différentes, et Px la valeur de la pièce x.

On recherche le nombre de combinaisons de n nombres naturels, nommons les Cx tels que:

S = C1*P1 + .... + Cn*Pn

On peut facilement déterminer que Cx <= S / Px

Il suffit ensuite de calculer les sommes de toutes ces combinaisons, et de compter le nombre de sommes qui sont égales à la somme à atteindre.

Il n'est nul besoin de memoriser les combinaisons déjà testées, comme il est facile de les tester en séquence.

0
mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024 7 755 > yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024
20 mars 2023 à 15:32

Quelques réponses à tes commentaires :

  • Il suffit ensuite de calculer les sommes de toutes ces combinaisons, et de compter le nombre de sommes qui sont égales à la somme à atteindre : comment ? il faut bien les énumérer. Note que l'implémentation que je propose se base sur des générateurs donc à la manière d'itertools.combinations_with_replacements.
  • Il n'est nul besoin de memoriser les combinaisons déjà testées, comme il est facile de les tester en séquence : Ensuite tu as deux choix possibles :
  1. soit tu n'en gardes pas trace, tu vas consommer moins de mémoire (mais en vrai il n'y en a pas tant que ça à mémoriser) et tu vas avoir beaucoup de redondances (donc solliciter davantage ton CPU) - c'est ce que fait la première version de sub_multiset.
  2. soit tu gardes en mémoire ce que tu as déjà vu pour couper tôt ton exploration - c'est que fait la seconde version de sub_multiset.
0
yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024 1 471 > mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024
20 mars 2023 à 20:41

En effet, il faut énumérer.

Comme il est impossible de tomber à nouveau sur une combinaison déjà rencontrée, il est totalement inutile de les mémoriser.

0
mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024 7 755 > yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024
21 mars 2023 à 16:07

Réponse courte : Ma réponse #4 ne répond pas au même problème (elle traite un cas plus compliqué, celui où tu es limité pour chaque type de pièce) et donc conduit a un autre programme. C'est sans doute pour ça que tu as jugé (à raison) ma solution "bien compliquée" et que certains des problèmes que j'évoque ne se pose pas dans la version simplifiée du problème.

Réponse détaillée :

  • Dans #4, j'ai cru que le nombre de chaque pièces était limité (par exemple, défini par ce que contenait ton porte-monnaie). Or l'exercice considère qu'on peut utiliser un nombre arbitrairement grand de pièces. La classe multiset (qui servait à garder trace des pièces restantes dans le porte monnaie) est donc inutile, on peut se contenter de mémoriser la distribution des pièces utilisées (comme tu le fais dans #7).
  • Comme il est impossible de tomber à nouveau sur une combinaison déjà rencontrée, il est totalement inutile de les mémoriser. Il est surtout inutile de les traiter à nouveau, et si tu veux éviter ça, tu dois
    • soit garantir que les solutions que tu vas explorer ne sont jamais redondantes (ce n'est pas le cas dans #4 et ce qui est peut-être le cas dans #6)
    • soit mémoriser ce que tu as déjà exploré si tu ne veux pas le ré-explorer.
      • Exemple : si ton porte monnaie contient deux pièces de 1€ et une pièce de 2€, comme les deux pièces de 1€ sont indiscernables, utiliser l'une ou l'autre ne change rien à la situation (tu dépenses 1€ de plus, et tu n'as plus qu'une pièce de 1€ et de 2€ dans ton porte monnaie). Toutes ces problématiques disparaissent quand tu considères que ton porte monnaie ne te limite jamais dans un type de pièce pour atteindre la somme cible (voir le premier point de la réponse détaillée).
0
yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024 1 471 > mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024
21 mars 2023 à 16:57

Je pense que ton espace de solutions est beaucoup trop complexe.  Pour moi, une solution est un tuple de n nombres naturels, n étant le nombre de pièces de monnaie différentes.

Il est donc très simple d'explorer cet espace de manière à éviter de tomber sur un élément déjà exploré, ce qui correspond, je suppose, à "garantir que les solutions que tu vas explorer ne sont jamais redondantes".

0

@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)
0
yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024 1 471
18 mars 2023 à 14:53

On peut optimiser en arrêtant d'incrémenter un des nombres quand la somme est dépassée.

p=[1,5,10,25,50]
s=81
def nb_rendus(somme, monnaie):
    if somme < 0 or len(monnaie) == 0:
        return 0
    if somme > 0:
        return nb_rendus(somme, monnaie[:-1]) + nb_rendus(somme-monnaie[-1], monnaie)
    return 1
def res(l,x,y):
    t=0
    for i in range(l):
        t += x[i]*y[i]
    return t
print(nb_rendus(s,p))
n=len(p)
r=0
c=[0 for i in range(n)]
maxes=[s//p[i] for i in range(n)]
col=n-1
tropgrand=False
b=0
while True:
    if c[col]<maxes[col] and not tropgrand:
        c[col] +=1
    else:
        col -= 1
        while c[col]==maxes[col]:
            if col==0:
                print("fini",r,b)
                exit()
            col -= 1
        c[col] +=1
        col += 1
        for i in range(col,n):
            c[i]=0
        col=n-1
    b+=1
    tot=res(n,c,p)
    tropgrand = True
    if tot==s:
        r +=1
    elif tot < s:
        tropgrand=False
0
mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024 7 755 > yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024
20 mars 2023 à 15:35

Bonjour, oui c'est la notion de coupe dont je parlais (voir #4). Mais note que l'implémentation que tu proposes dans #7 est récursive, or la question initiale demande comment résoudre le problème avec un algorithme itératif.

0
yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024 1 471 > mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024
20 mars 2023 à 20:42

La suggestion en #7 n'est pas récursive.  Elle inclut la solution récursive (nb_rendus) afin de pouvoir comparer les résultats des deux méthodes.

0
mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024 7 755 > yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024
21 mars 2023 à 15:55

Ah oui ok.

Voilà ce que j'ai cru comprendre :

  • b stocke le nombre de décomposition considérées
  • c stocke le nombre de pièce de chaque valeur sélectionnées
  • col identifie quel est le prochain type de pièce qu'on va utiliser
  • maxes stocke le nombre maximale de pièces d'une valeur données que tu peux utiliser pour ne pas dépasser la somme cible s
  • n stocke le nombre de type de pièces
  • p stocke les valeurs des pièces
  • res(n, c, p) permet donc de calcule la somme de la sélection de pièces
  • r stocke le nombre de décomposition trouvées
  • s est la somme cible

Vu l'algorithme je crois deviner que p doit être trié dans l'ordre croissant. Si j'ai bien compris,

  • ligne 19 tu démarres avec les plus grosses pièces (valeur courante)
  • ligne 23, tant que ça ne dépasse pas s, tu continues à utiliser la valeur courante ; mais si ça dépasse, tu rends une pièce, et tu passes à la valeur plus petite

 J'ai un peu de mal à saisir ce que tu fais entre l27 et l36.

Le programme retourne à la fin (r, b) (nombre de décompositions valides, nombre de décompositions testées).

0
yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024 1 471 > mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024
21 mars 2023 à 16:39

Les pièces ne doivent pas être triées pour obtenir le bon résultat. 

Voici le code sans optimisation, il est sans doute plus compréhensible:

import itertools
p=[1,5,10,25,50]
s=81
def res(l,x,y):
    t=0
    for i in range(l):
        t += x[i]*y[i]
    return t
n=len(p)
r=0
c=[0 for i in range(n)]
maxes=[s//p[i] for i in range(n)]
col=n-1
b=0
sets=[range(maxes[i]+1) for i in range(n)]
for c in itertools.product(*sets):
    b +=1
    if res(n,c,p) == s:
        r += 1
print(r,b)

Dès qu'on veut optimiser, on ne peut plus utiliser itertools.  Comme le nombre de pièces est variable, on ne peut pas utiliser de boucles, la profondeur étant variable.  Comme on ne veut pas utiliser de récursion, le code qui vérifie toutes les combinaisons n'est pas très lisible, en effet.

0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question

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)
0
yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024 1 471
18 mars 2023 à 19:43

Cela m'a donné l'idée de laisser tomber les valeurs limites, et de plutôt arrêter d'incrémenter les valeurs quand la somme était dépassée:

p=[1,5,10,20,50]
s=81
p.sort(reverse=True)
print(s,p)
def nb_rendus(somme, monnaie):
    if somme < 0 or len(monnaie) == 0:
        return 0
    if somme > 0:
        return nb_rendus(somme, monnaie[:-1]) + nb_rendus(somme-monnaie[-1], monnaie)
    return 1
def res(l,x,y):
    global ncomp
    ncomp += 1
    t=0
    for i in range(l):
        t += x[i]*y[i]
    return t
print(nb_rendus(s,p))
n=len(p)
r=0
c=[0 for i in range(n)]
col=n-1
tropgrand=False
ncomp=0
while True:
    if  not tropgrand:
        c[col] +=1
    else:
        c[col] =0
        c[col-1] +=1
        while res(n,c,p) > s:
            col -= 1
            c[col]=0
            if col==0:
                print("exit",ncomp,r)
                exit()
            c[col-1] +=1
        col=n-1
    tot=res(n,c,p)
    tropgrand = True
    if tot==s:
        r +=1
    elif tot < s:
        tropgrand=False
0

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))
0
yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024 1 471
19 mars 2023 à 08:08

Comme d'habitude, rien ne vaut la programmation dynamique!

0
mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024 7 755 > yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024
20 mars 2023 à 15:38

Effectivement, mais note que comme la solution que je proposais dans #4, tu maintiens en mémoire toutes les combinaisons que tu as explorées. La seule limitation à l'implémentation proposée dans #10 (et c'est ce qui explique pourquoi le code est bien plus simple que dans #4) et qu'on ne tient absolument pas compte de la distribution de pièce initialement disponibles.

0
yg_be Messages postés 22818 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 28 mai 2024 1 471 > mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024
20 mars 2023 à 20:37

Aucune des solutions suggérées ne mémorise toutes les combinaisons explorées.

0