Aller au contenu

Algorithme de rendu de monnaie en programmation dynamique

Objectif⚓︎

On cherche à rendre une somme donnée en utilisant le moins de pièces possible parmi un ensemble donné de valeurs de pièces. Cet algorithme permet de calculer non seulement le nombre minimal de pièces mais aussi quelles pièces choisir.

L'approche utilisée ici est celle de la programmation dynamique dite bottom-up, qui construit une table pour trouver les solutions optimales à tous les sous-problèmes jusqu'à la somme cible.

1. Construction de la table de programmation dynamique (bottom-up)⚓︎

Compléter le code suivant pour remplir la table least_coins qui donne le nombre minimal de pièces pour chaque sous-montant :

Objectif : remplir la table en minimisant le nombre de pièces utilisées pour chaque montant.

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
coins = [1,3,5,7,10,20]
def least_coins(amount):
    ''' Renvoie le nombre de pièces minimal pour un montant amount'''
    n = len(coins) # nombre de pièces
    # initialisation du tableau avec des valeurs infinies
    least_coins = [[float('inf')] * (amount + 1) for _ in range(n)]

    # remplissage de la première lige
    for sub_amount in range(amount + 1):
        if sub_amount % coins[0] == 0:
                least_coins[0][sub_amount] = _____

    # Calcul des lignes suivantes en se basant sous les sous problèmes.
    for i in range(1, n):
        for j in range(amount + 1):
            least_coins[i][j] = _____
            if coins[i] <= j:
                if least_coins[i][j - coins[i]] + 1 < least_coins[i][j]:
                    least_coins[i][j] = _____
    return least_coins[n - 1][amount]

2. Reconstruction de la solution optimale⚓︎

Une fois la table remplie, on peut reconstruire la combinaison de pièces choisies. Compléter le code ci-dessous pour cela :

Objectif : en partant de least_coins[n-1][amount], déterminer quelles pièces permettent d'obtenir ce résultat optimal.

Le code suivant sera ajouté à la fin de la fonction least_coins, à la place du return least_coins[n - 1][amount], et en ajoutant return chosen

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
chosen = [0] * n
j = amount
i = n - 1
while j:
    if j >= coins[i]:
        if _____:
            chosen[i] += 1
            j -= coins[i]
            continue
    i -= 1

3. Variante top-down (récursive avec mémoïzation)⚓︎

Compléter le code suivant qui propose une version récursive mémoïisée (top-down) de l'algorithme :

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def moneyback_topdown(amount, coins):
    memo = {}
    def helper(i, remaining):
        if remaining == 0:
            return 0
        if i < 0 or remaining < 0:
            return float('inf')
        if (i, remaining) in memo:
            return memo[(i, remaining)]

        not_take = helper(i - 1, remaining)
        take = float('inf')
        if coins[i] <= remaining:
            take = _____

        memo[(i, remaining)] = _____
        return memo[(i, remaining)]

    result = helper(len(coins) - 1, amount)
    return result if result != float('inf') else -1

Cette version met en œuvre l'approche descendante qui consiste à partir du problème global et résoudre récursivement les sous-problèmes nécessaires.

Ici la focntion récursive (top_down) ne donne que le nombre de pièces minimal. Pas la répartition.

Conclusion⚓︎

L'approche en programmation dynamique permet d'éviter la répétition de calculs inutiles et garantit une solution optimale.

Les deux versions (bottom-up et top-down) permettent d'appréhender deux façons complémentaires de raisonner sur des problèmes d'optimisation discrète.

Crédits : Rendu de monnaie, bases de programmation dynamique -Dec 11, 2016 • Jill-Jênn Vie & Clémence Réda