Algorithmes et Structures de Données

Coin change - le nombre de façons

Supposons qu’on ait un système monétaire composé de n pièces, chacune possédant une valeur positive . On cherche à déterminer le nombre de façons d’atteindre la somme totale x en utilisant ces pièces.
Par exemple, si les valeurs des pièces sont et que l’on souhaite obtenir 5, il existe 4 moyens différents de le faire : 5, 1 + 2 + 2, 1 + 1 + 1 + 2 et 1 + 1 + 1 + 1 + 1. Contrairement au combination sum, ici l’ordre n’a pas d’importance — on ne se soucie que de l’ensemble (multiset) des pièces utilisées.

Entrée

La première ligne de l’entrée contient deux entiers n (1 ≤ n ≤ 100) et x (1 ≤ x ≤ ).
La ligne suivante contient n entiers séparés par des espaces (1 ≤ ≤ ).

Sortie

Le programme doit afficher le nombre de façons possible d’obtenir x en utilisant les pièces données. Étant donné que la réponse peut être très grande, il faut l’afficher modulo .

Exemples

Input
Output
3 5 1 2 5
4
3 9 2 3 5
3

Explication

  1. 5, 1 + 2 + 2, 1 + 1 + 1 + 2, et 1 + 1 + 1 + 1 + 1
  1. 3 + 3 + 3, 2 + 2 + 5, 2 + 2 + 2 + 3
 

Tutorial

Remarquez que si l’on stocke un état d[s], où d[s] représente le nombre de façons distinctes d’obtenir la somme s à l’aide des pièces, on risque de compter plusieurs fois les mêmes compositions. À titre d’exemple, l’ensemble 1 + 2 + 2 ne devrait être comptabilisé qu’une seule fois, alors qu’il pourrait apparaître trois fois (1 + 2 + 2, 2 + 1 + 2, 2 + 2 + 1) si on n’y prend pas garde.
Pour résoudre ce problème, on va compter le nombre de façons d’obtenir la valeur s tout en tenant compte de toutes les pièces jusqu’à l’indice ci (c’est-à-dire de la première à la ci-ème). On peut décider de ne pas utiliser la pièce ci du tout, ou de l’utiliser plusieurs fois — tout cela est inclus dans l’état. On définit donc d[s][ci] comme le nombre de façons d’obtenir la somme s en considérant toutes les pièces jusqu’à l’indice ci.
 
Deux types de transitions permettent de déterminer d[s][ci] (si la pièce courante a l’indice ci et la valeur val) :
  1. Ne pas utiliser la pièce ci → d[s][ci - 1].
  1. Utiliser la pièce ci 0, 1, 2, … k fois → d[s - val][ci].
Le nombre total de façons d’obtenir la somme s avec toutes les pièces jusqu’à ci est donc la somme de ces deux contributions.
 
c = [...]
x = ...
# Initialize d with x+1 rows and len(c) columns of 0s
d = [[0] * len(c) for _ in range(x + 1)]
On peut commencer par traiter la première pièce et mettre à jour l’état d[s][0] pour toutes les sommes possibles s à l’aide de cette première pièce. Ensuite, on passe à la deuxième pièce et on met à jour tous les états d[s][1]. Puis, on continue ainsi jusqu’à la dernière pièce.
Une fois toutes les pièces traitées, il suffit d’afficher le nombre de façons d’atteindre la somme x en regardant l’état correspondant après le traitement de la dernière pièce : d[x][len(c) - 1].
for ci, val in enumerate(c):      # Iterate over coins one-by-one
    d[0][ci] = 1                  # Possible to obtain sum of 0 with no coins
    for s in range(1, x + 1):     # Iterate over all sums 1...x inclusive
        if ci - 1 >= 0:           # (1) Not use ci at all
            d[s][ci] += d[s][ci - 1]
        if s - val >= 0:          # (2) Use ci for 0+ times
            d[s][ci] += d[s - val][ci]

print(d[x][len(c) - 1])
 
😎 Pouvez-vous imaginer une manière de garder une seule liste pour d ?
On peut traiter les pièces une à une. Ainsi, il suffit de se débarrasser des calculs concernant la pièce ci - 2 et toutes celles d’avant. À chaque itération, on n’a besoin que de l’état précédent (pièce ci - 1) et de l’état courant (pièce ci). Il est donc possible de n’avoir qu’un seul tableau pour représenter l’état de la pièce précédente et un autre pour celui de la pièce courante.
😎 Pouvez-vous imaginer une solution qui n’utilise qu’un seul et même tableau d à une dimension, sans ajouter de structure supplémentaire ?
On constate que la seule opération à effectuer à partir de l’état de la pièce précédente est l’addition de prev[s] dans d[s]. Du coup, on peut se passer complètement du tableau précédent :
# Initialize d x+1 items
d = [1] + [0] * x                 # Possible to obtain sum of 0 with no coins

for ci, val in enumerate(c):      # Iterate over coins one-by-one
    for s in range(1, x + 1):     # Iterate over all sums 1...x inclusive
        if s - val >= 0:          # (2) Use ci for 0+ times
            d[s] += d[s - val]
        d[s] %= MOD

print(d[x])
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue