dynamic-programming
Problème de changement de pièce

Nombre de façons d'obtenir le total

Compte tenu des pièces de différentes dénominations et d'un total, de combien de façons pouvons-nous combiner ces pièces pour obtenir le total? Disons que nous avons des coins = {1, 2, 3} et un total = 5 , nous pouvons obtenir le total de 5 façons:

• 1 1 1 1 1
• 1 1 1 2
• 1 1 3
• 1 2 2
• 2 3

Le problème est étroitement lié au problème du sac à dos. La seule différence est que nous avons un approvisionnement illimité en pièces. Nous allons utiliser une programmation dynamique pour résoudre ce problème.

Nous utiliserons un tableau 2D dp [n] [total + 1] où n est le nombre de dénominations différentes des pièces que nous avons. Pour notre exemple, nous aurons besoin de dp [3] [6] . Ici, dp [i] [j] dénotera le nombre de façons d'obtenir j si nous avions des pièces de monnaie [0] jusqu'à des pièces [i] . Par exemple dp [1] [2] stockera si nous avions des pièces [0] et les pièces [1], dans combien de façons dont nous pourrions faire 2. Commençons:

Pour dp [0] [0], nous nous demandons si nous avions seulement 1 dénomination de pièces de monnaie, qui est des pièces de monnaie [0] = 1, combien de façons pouvons - nous obtenir 0? La réponse est 1 , c'est-à-dire si nous ne prenons aucune pièce. Si vous continuez, dp [0] [1] représentera si nous n'avions que des pièces de monnaie [0] , de combien de façons pouvons-nous obtenir 1 ? La réponse est encore 1 . De la même manière, dp [0] [2] , dp [0] [3] , dp [0] [4] , dp [0] [5] sera 1 . Notre tableau ressemblera à:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
 (3) | 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

Pour dp [1] [0], nous nous demandons si nous avions des pièces de 2 confessions, qui est si nous avions des pièces de monnaie [0] = 1 et pièces de monnaie [1] = 2, combien de façons nous pourrions faire 0? La réponse est 1 , qui consiste à ne prendre aucune pièce. Pour dp [1] [1] , puisque pièces [1] = 2 est supérieur à notre total actuel, 2 ne contribueront pas à obtenir le total. Nous allons donc exclure 2 et compter le nombre de façons dont nous pouvons obtenir le total en utilisant des pièces de monnaie [0] . Mais cette valeur est déjà stockée dans dp [0] [1] ! Nous allons donc prendre la valeur du haut. Notre première formule:

if coins[i] > j
    dp[i][j] := dp[i-1][j]
end if

Pour dp [1] [2] , de combien de façons pouvons-nous obtenir 2 , si nous avions des pièces de monnaie de dénomination 1 et 2 ? On peut faire 2 en utilisant des pièces de dénomination de 1 , ce qui est représenté par dp [0] [2] , là encore on peut prendre 1 dénomination de 2 qui est stockée dans dp [1] [2-pièces [i]] , où i = 1 . Pourquoi? Ce sera évident si nous regardons l'exemple suivant. Pour dp [1] [3] , de combien de façons pouvons-nous obtenir 3 , si nous avions des pièces de 1 et 2 ? On peut faire 3 en utilisant des pièces de dénomination 1 de 1 manière, qui sont stockées dans dp [0] [3] . Maintenant, si nous prenons 1 dénomination de 2 , nous aurons besoin de 3 - 2 = 1 pour obtenir le total. Le nombre de façons d'obtenir 1 en utilisant les pièces de la dénomination 1 et 2 est stocké dans dp [1] [1] , qui peut être écrit comme suit: dp [i] [j-pièces [i]] , où i = 1 . C'est pourquoi nous avons écrit la valeur précédente de cette manière. Notre deuxième et dernière formule sera:

if coins[i] <= j
    dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if

Ce sont les deux formules requises pour remplir tout le tableau dp . Après avoir rempli le tableau ressemblera à:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
     +---+---+---+---+---+---+---+
 (3) | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+

dp [2] [5] contiendra notre réponse requise. L'algorithme:

Procedure CoinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 1
end for
for i from 0 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j]
        else
            dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
        end if
    end for
end for
Return dp[n-1][total]

La complexité temporelle de cet algorithme est O(n * total) , où n est le nombre de dénominations de pièces que nous avons.

Nombre minimum de pièces pour obtenir le total

Si vous utilisez des pièces de différentes dénominations et un total, combien de pièces devons-nous combiner pour obtenir le total si nous utilisons un nombre minimum de pièces? Disons que nous avons des coins = {1, 5, 6, 8} et un total = 11 , nous pouvons obtenir le total en utilisant 2 pièces, soit {5, 6} . C'est en effet le nombre minimum de pièces nécessaires pour obtenir 11 . Nous supposons également qu'il y a une offre illimitée de pièces. Nous allons utiliser une programmation dynamique pour résoudre ce problème.

Nous utiliserons un tableau 2D dp [n] [total + 1] où n est le nombre de dénominations différentes des pièces que nous avons. Pour notre exemple, nous aurons besoin de dp [4] [12] . Ici, dp [i] [j] désignera le nombre minimum de pièces nécessaires pour obtenir j si nous avions des pièces de monnaie [0] jusqu'aux pièces [i] . Par exemple, dp [1] [2] stockera si nous avions des pièces de monnaie [0] et des pièces de monnaie [1] , quel est le nombre minimum de pièces que nous pouvons utiliser pour faire 2 . Commençons:

Dans un premier temps , pour la colonne 0 e, peut faire 0 en ne prenant pas des pièces du tout. Donc, toutes les valeurs de 0 ème colonne seront 0 . Pour dp [0] [1] , nous nous demandons si nous avions seulement 1 pièce de monnaie, à savoir des pièces [0] = 1 , quel est le nombre minimum de pièces nécessaires pour obtenir 1 ? La réponse est 1 . Pour dp [0] [2] , si nous n'avions que 1 , quel est le nombre minimum de pièces nécessaires pour obtenir 2 . La réponse est 2 . De même dp [0] [3] = 3 , dp [0] [4] = 4 et ainsi de suite. Une chose à mentionner ici est que, si nous n'avions pas de pièce de monnaie de dénomination 1 , il pourrait y avoir des cas où le total ne pourrait pas être atteint avec une seule pièce. Pour simplifier, nous prenons 1 dans notre exemple. Après la première itération, notre tableau dp ressemblera à ceci:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

Passons maintenant, pour dp [1] [1] , nous nous demandons si nous avions des pièces de monnaie [0] = 1 et des pièces de monnaie [1] = 5 , quel est le nombre minimum de pièces nécessaires pour obtenir 1 ? Puisque les pièces [1] sont plus grandes que notre total actuel, cela n'affectera pas notre calcul. Nous devrons exclure les pièces de monnaie [5] et obtenir 1 en utilisant uniquement des pièces de monnaie [0] . Cette valeur est stockée dans dp [0] [1] . Nous prenons donc la valeur du haut. Notre première formule est la suivante:

if coins[i] > j
    dp[i][j] := dp[i-1][j]

Cette condition sera vraie jusqu'à ce que notre total soit 5 dans dp [1] [5] , pour ce cas, nous pouvons faire 5 de deux manières:

• Nous prenons 5 dénominations de pièces [0] , qui sont stockées sur dp [0] [5] (à partir du haut).
• Nous prenons 1 dénomination des pièces [1] et ( 5 - 5 ) = 0 dénomination des pièces [0] .

Nous choisirons le minimum de ces deux. Donc dp [1] [5] = min ( dp [0] [5] , 1 + dp [1] [0] ) = 1 . Pourquoi avons-nous mentionné 0 dénomination de pièces [0] ici sera évident dans notre prochaine position.

Pour dp [1] [6] , on peut faire 6 de deux manières:

• Nous prenons 6 dénominations de pièces [0] , qui sont stockées sur le dessus.
• Nous pouvons prendre 1 dénomination de 5 , nous aurons besoin de 6 - 5 = 1 pour obtenir le total. Le nombre minimum de façons d'obtenir 1 en utilisant les pièces de la dénomination 1 et 5 est stocké dans dp [1] [1] , qui peut être écrit sous la forme dp [i] [j-pièces [i]] , où i = 1 . C'est pourquoi nous avons écrit la valeur précédente de cette façon.

Nous allons prendre le minimum de ces deux façons. Donc, notre deuxième formule sera:

if coins[i] >= j
    dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])

En utilisant ces deux formules, nous pouvons remplir toute la table. Notre résultat final sera:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 1 | 2 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

Notre résultat requis sera stocké à dp [3] [11] . La procédure sera la suivante:

Procedure coinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 0
end for
for i from 1 to (total + 1)
    dp[0][i] := i
end for
for i from 1 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j] 
        else
            dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
        end if
    end for
end for
Return dp[n-1][total]

La complexité d'exécution de cet algorithme est la suivante: O (n * total) où n est le nombre de dénominations de pièces.

Pour imprimer les pièces nécessaires, il faut vérifier:

• Si la valeur vient du haut, la pièce en cours n'est pas incluse.
• Si la valeur vient de gauche, la pièce en cours est incluse.

L'algorithme serait:

Procedure printChange(coins, dp, total):
i := coins.length - 1
j := total
min := dp[i][j]
while j is not equal to 0
    if dp[i-1][j] is equal to min
        i := i - 1
    else
        Print(coins[i])
        j := j - coins[i]
    end if
end while

Pour notre exemple, la direction sera:

Les valeurs seront 6 , 5 .