Rendu de monnaie tiré de Wikipédia
« Le problème du rendu de monnaie est un problème d'algorithmique. Il s'énonce de la façon suivante : étant donné un système de monnaie (pièces et billets), comment rendre une somme donnée de façon optimale, c'est-à-dire avec le nombre minimal de pièces et billets ?
Par exemple, la meilleure façon de rendre 7 euros est de rendre un billet de cinq et une pièce de deux, même si d'autres façons existent (rendre 7 pièces de un euro, par exemple). On rencontre des problèmes similaires dans l'utilisation des boites à poids.
Ce problème est NP-complet dans le cas général, c'est-à-dire difficile à résoudre. Cependant pour certains systèmes de monnaie dits canoniques, l'algorithme glouton est optimal, c'est-à-dire qu'il suffit de rendre systématiquement la pièce ou le billet de valeur maximale — ce tant qu'il reste quelque chose à rendre. C'est la méthode employée en pratique, ce qui se justifie car la quasi-totalité des systèmes ayant cours dans le monde sont canoniques. Il n'existe pas, à ce jour, de caractérisation générale des systèmes canoniques, mais il existe une méthode efficace pour déterminer si un système donné est canonique. »
On peut trouver sur la grande toile beaucoup de solutions. Certaines solutions donnent le nombre de façons différentes d’obtenir la somme demandée.
# solution récoursive qui compte les différentes solutions
# Function to find the total number of distinct ways to get a change of `target`
# from an unlimited supply of coins in set `S`
def count(S, n, target):
# if the total is 0, return 1 (solution found)
if target == 0:
return 1
# return 0 (solution does not exist) if total becomes negative,
# no elements are left
if target < 0 or n < 0:
return 0
# Case 1. Include current coin `S[n]` in solution and recur
# with remaining change `target-S[n]` with the same number of coins
incl = count(S, n, target - S[n])
# Case 2. Exclude current coin `S[n]` from solution and recur
# for remaining coins `n-1`
excl = count(S, n - 1, target)
# return total ways by including or excluding current coin
return incl + excl
# Coin Change Problem
# `n` coins of given denominations
S = [1, 2, 3]
# total change required
target = 4
print()
print("#############################")
print()
print("S=", S)
print("target=",target)
print('The total number of ways to get the desired change is',
count(S, len(S) - 1, target))
Réponse affichée à la console :
S= [1, 2, 3]
target= 4
The total number of ways to get the desired change is 4
Process finished with exit code 0
############################
L’algorithme suivant donne une solution minimale, c’est-à-dire, le nombre de pièces minimales et une liste de pièces correspondante. Ne donne pas cependant toutes les solutions minimales.
# excellente solution
# solution avec un dictionnaire python
# donne le nombre et une solution
# currency denominations
currency = [10,9,7,6,4,3]
amount = 23
# cache contains the best currency combos for each value:
# eg cache[7]=[5,1,1]
cache = dict()
def recursive_change(currency, amount):
if amount in cache.keys():
return []+cache[amount]
# base case
if amount == 0:
return []
# If we can't make the amount with this coin, return -1
if amount < 0:
return [-1]
best_combo = [-1]
for coin in currency:
current_result = recursive_change(currency, amount-coin)
if current_result == [] or current_result[0] >= 0:
current_result.append(coin) # if we picked a coin, we
# add it to the list
if best_combo[0] < 0:
best_combo = current_result
# if we found the first coin combo that works for
# the current problem, set best so we don't compare
# to -1 below
else:
# if this isn't the first coin combo that works
# for the current problem, check to see if it's
# better than any of the other coin combos
if len(current_result) < len(best_combo):
best_combo = current_result
cache[amount] = [] +best_combo # + cache[amount]# Had to do this
# [] thing so it passes a copy
return best_combo
print("autre solution récursive")
print("currency=",currency," amount=",amount)
print("La réponse récursive est ",
recursive_change(0,currency, amount))
print("le dictionnaire 'cache'=")
print()
for key, value in cache.items():
print(key,value)
print()
La réponse :
autre solution récursive
currency= [10, 9, 7, 6, 4, 3] amount= 23
La réponse récursive est [3, 10, 10]
le dictionnaire 'cache'=
montant: 3 [3]
montant: 1 [-1]
montant: 4 [4]
montant: 2 [-1]
montant: 6 [6]
montant: 7 [7]
montant: 5 [-1]
montant: 9 [9]
montant: 10 [10]
montant: 13 [3, 10]
montant: 8 [4, 4]
montant: 11 [4, 7]
montant: 14 [4, 10]
montant: 12 [3, 9]
montant: 16 [6, 10]
montant: 17 [7, 10]
montant: 15 [6, 9]
montant: 19 [9, 10]
montant: 20 [10, 10]
montant: 23 [3, 10, 10]
#############################
Maintenant, tenez vous après votre banc, voici une solution récursive qui liste toutes les possibilités de sommes
#################################################
# rendu de monnaie
# liste toutes les solutions
def change(n, coins_available, coins_so_far):
if sum(coins_so_far) == n:
yield coins_so_far
elif sum(coins_so_far) > n:
pass
elif coins_available == []:
pass
else:
for c in change(n, coins_available[:], coins_so_far+
[coins_available[0]]):
yield c
for c in change(n, coins_available[1:], coins_so_far):
yield c
#test
n=13
coins = [1,2,3,6,7,10]
print("Voici tous les cas possibles de somme ",n)
print("avec un nombre illimité de pièces ",coins)
solutions = [s for s in change(n, coins, [])]
for s in solutions:
print(s)
print('optimal solution:', min(solutions, key=len))
Réponse :
Voici tous les cas possibles de somme 13
avec un nombre illimité de pièces [1, 2, 3, 6, 7, 10]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 3]
[1, 1, 1, 1, 1, 1, 1, 2, 2, 2]
[1, 1, 1, 1, 1, 1, 1, 3, 3]
[1, 1, 1, 1, 1, 1, 1, 6]
[1, 1, 1, 1, 1, 1, 2, 2, 3]
[1, 1, 1, 1, 1, 1, 7]
[1, 1, 1, 1, 1, 2, 2, 2, 2]
[1, 1, 1, 1, 1, 2, 3, 3]
[1, 1, 1, 1, 1, 2, 6]
[1, 1, 1, 1, 2, 2, 2, 3]
[1, 1, 1, 1, 2, 7]
[1, 1, 1, 1, 3, 3, 3]
[1, 1, 1, 1, 3, 6]
[1, 1, 1, 2, 2, 2, 2, 2]
[1, 1, 1, 2, 2, 3, 3]
[1, 1, 1, 2, 2, 6]
[1, 1, 1, 3, 7]
[1, 1, 1, 10]
[1, 1, 2, 2, 2, 2, 3]
[1, 1, 2, 2, 7]
[1, 1, 2, 3, 3, 3]
[1, 1, 2, 3, 6]
[1, 2, 2, 2, 2, 2, 2]
[1, 2, 2, 2, 3, 3]
[1, 2, 2, 2, 6]
[1, 2, 3, 7]
[1, 2, 10]
[1, 3, 3, 3, 3]
[1, 3, 3, 6]
[1, 6, 6]
[2, 2, 2, 2, 2, 3]
[2, 2, 2, 7]
[2, 2, 3, 3, 3]
[2, 2, 3, 6]
[3, 3, 7]
[3, 10]
[6, 7]
optimal solution: [3, 10]
#################################################
Solution hyper courte compte le nombre de solutions
################################################
def count(coins, n, sum):
if (sum == 0):
return 1
if (sum < 0):
return 0
if (n <= 0):
return 0
return count(coins, n - 1, sum) + count(coins, n, sum-coins[n-1])
coins = [1,2,3,6,7,10]
n = len(coins)
print("nombre de solutions: coins=",coins," sum=",n,":",count(coins,n, 13))
nombre de solutions: coins= [1, 2, 3, 6, 7, 10] sum= 6 : 41
################################################