Récursive de transformation de l'algorithme

Donné une quantité de cible et une liste de pièces, mon code est censé trouver le moins de pièces de monnaie nécessaire pour atteindre le montant cible.

Exemples:

C(78, [1, 5, 10, 25, 50]) = 6
- nous pouvons faire de 78 à partir de 3x25 + 3x1, pour 6 pièces de monnaie sont nécessaires
C(48, [1, 7, 24, 42]) = 2
- 48 = 2x24, donc 2 pièces sont suffisamment
C(35, [1, 3, 16, 30, 50]) = 3
- nous pouvons faire 35 de 2x16 + 1x3, donc 3 pièces suffisent

J'ai fait le code avec des boucles, mais comment puis-je faire en récursif?

def C(i, coins, cdict = None):
    if cdict == None:
        cdict = {}
    if i <= 0:
        cdict[i] = 0
        return cdict[i]
    elif i in cdict:
        return cdict[i]
    elif i in coins:
        cdict[i] = 1
        return cdict[i]
    else:
        min = 0
        for cj in coins:
            result = C(i - cj, coins)
            if result != 0:
                if min == 0 or (result + 1) < min:
                    min = 1 + result
        cdict[i] = min
        return cdict[i]

quand vous dites "paire de pièces de monnaie", entendez-vous à la "liste des pièces"?
Déjà, elle est récursive. Vous appelez C de l'intérieur de lui-même. Suis-je manqué quelque chose?
"La moins quantité de pièces de monnaie qui sont nécessaires"? Pour ce que? C'est vraiment mal expliqué.
Je pense que le plus petit nombre de pièces de la liste qui s'ajoutent à l'égal de ce nombre.
C'est sans doute la moins quantité de pièces de monnaie nécessaire d'ajouter jusqu'à i. C'est un assez bon exemple de problème de programmation dynamique.

InformationsquelleAutor user1681664 | 2012-09-20

19

C'est le changer de prise problème. Voici le standard de la solution récursive, V s'agit de la liste de pièces de monnaie et C le montant cible de l'argent:
```
def min_change(V, C):
    def min_coins(i, aC):
        if aC == 0:
            return 0
        elif i == -1 or aC < 0:
            return float('inf')
        else:
            return min(min_coins(i-1, aC), 1 + min_coins(i, aC-V[i]))
    return min_coins(len(V)-1, C)
```
Et c'est une version optimisée, à l'aide de la programmation dynamique:
```
def min_change(V, C):
    m, n = len(V)+1, C+1
    table = [[0] * n for x in xrange(m)]
    for j in xrange(1, n):
        table[0][j] = float('inf')
    for i in xrange(1, m):
        for j in xrange(1, n):
            aC = table[i][j - V[i-1]] if j - V[i-1] >= 0 else float('inf')
            table[i][j] = min(table[i-1][j], 1 + aC)
    return table[m-1][n-1]
```
Les deux implémentations retournera toujours la solution optimale, mais le second sera beaucoup plus rapide pour les grandes entrées. Notez que l'algorithme glouton suggéré dans d'autres réponses donne une solution optimale que pour certaines combinaisons de la monnaie par exemple, il travaille pour les Américains de pièces de monnaie.
- Je vous remercie. c'est exactement ce dont j'avais besoin. Juste quelques questions, où êtes-vous d'obtenir les variables i, aC et ce que signifient-ils?
- Regardez la dernière ligne de la fonction, de la partie où min_coins() est appelé. D'abord, i = len(V)-1 et aC = C. min_coins() est une fonction d'assistance interne
InformationsquelleAutor Óscar López
2

Essayez d'utiliser un algorithme glouton (la plus grande des pièces de monnaie en premier). Retirez la pièce de monnaie à partir de la liste après s'applique à l'ensemble et appeler la fonction à nouveau de l'intérieur.
- L'algorithme glouton ne donne pas toujours la meilleure réponse. Par exemple, avec 1, 6, 7, et 10 pièces de un cent, ce qui est le moins nombre de pièces nécessaires pour obtenir de 13 cents? La méthode greedy dit {10,1,1,1}, Mais la vraie réponse est {7,6}.
- Il le fait pour de vrai les dénominations de pièces de monnaie ... mais à partir d'un point de vue académique que c'est correct
- L'algorithme glouton donne une solution optimale que pour certaines combinaisons de monnaie. Par exemple, il travaille pour les Américains de pièces de monnaie.
- Approche gourmande ne donnera pas une solution optimale. C'est certainement une question concernant Programmation Dynamique.
- Vérifier mon gourmand de mise en œuvre ci-dessus: print(greedy((1, 6, 7, 10), 13)) donne: {6: 1, 7: 1}. Si cela ne vous donne pas la bonne réponse, cela signifie seulement que vous n'étiez pas en mesure de mettre en œuvre correctement. Gourmand signifie qu'il va chercher tous les moyens possibles pour résoudre le problème, puis le choix optimal.
InformationsquelleAutor BeReal82

De sorte que le meilleur endroit pour chercher de la programmation dynamique de la mise en œuvre est: interactive python

Cependant, après quelques essais j'ai constaté que ce n'est pas la solution la plus rapide. La bonne chose à ce sujet est que un seul passage suffit de trouver des valeurs pour toutes les valeurs de changement jusqu'montant nécessaire.

Mon préféré est encore d'utiliser la récursivité avec la mise en cache:

from collections import defaultdict
from functools import lru_cache


@lru_cache(maxsize=1024)
def greedy(coin_list, change):
    if change in coin_list:
        return defaultdict(int, [(change, 1)])
    else:
        min_coins = change
        for c in [coin for coin in coin_list if coin < change]:
            result_min1 = greedy(coin_list, change - c)
            num_coins = 1 + sum(result_min1.values())
            if num_coins <= min_coins:
                min_coins = num_coins
                result = defaultdict(int, [(c, 1)])
                for c1, n in result_min1.items():
                    result[c1] += n
        return result

InformationsquelleAutor dgrigonis

Vous devez vous connecter pour publier un commentaire.