Algorithme de changement de pièces

Question

Supposons que j'ai un ensemble de pièces de monnaie ayant les dénominations a1, a2, ... ak.

L'un d'eux est connu pour être égal à 1.

Je veux faire des changements pour tous les entiers 1 à n en utilisant le nombre minimum de pièces.

Toutes les idées pour l'algorithme.

eg. 1, 3, 4 coin denominations 
n = 11 
optimal selection is 3, 0, 2 in the order of coin denominations. 

n = 12 
optimal selection is 2, 2, 1. 

Note: pas de devoirs juste une modification de this problème

Answer 1

Ceci est un problème de programmation dynamique classique (noter tout d'abord que l'algorithme glouton ne fonctionne pas toujours ici!).

Supposons que les pièces sont commandées de sorte que a_1 > a_2 > ... > a_k = 1. Nous définissons un nouveau problème. Nous disons que le problème (i, j) est de trouver le nombre minimum de pièces faisant changement pour j en utilisant des pièces de monnaie a_i > a_(i + 1) > ... > a_k. Le problème que nous souhaitons résoudre est (1, j) pour tout j avec 1 <= j <= n. Dites que C(i, j) est la réponse au problème (i, j).

Maintenant, considérons une instance (i, j). Nous devons décider si nous utilisons ou non l'une des pièces a_i. Si ce n'est pas le cas, nous sommes en train de résoudre un problème (i + 1, j) et la réponse est C(i + 1, j). Si nous sommes, nous complétons la solution en faisant le changement pour j - a_i. Pour ce faire en utilisant le moins de pièces possible, nous voulons résoudre le problème (i, j - a_i). Nous organisons des choses pour que ces deux problèmes sont déjà résolus pour nous et puis:

C(i, j) = C(i + 1, j)       if a_i > j 
     = min(C(i + 1, j), 1 + C(i, j - a_i)) if a_i <= j 

maintenant savoir ce que les premiers cas sont et comment traduire cela dans la langue de votre choix et vous devriez être bon d'aller.

Si vous souhaitez vous essayer à un autre problème intéressant nécessitant une programmation dynamique, consultez Projet Euler Problem 67.

Answer 2

Voici un exemple d'implémentation d'un algorithme de programmation dynamique en Python. C'est plus simple que l'algorithme que décrit Jason, car il ne calcule qu'une seule ligne de la table 2D qu'il décrit.

Veuillez noter que l'utilisation de ce code pour tromper les devoirs fera pleurer Zombie Dijkstra.

import sys 
def get_best_coins(coins, target): 
    costs = [0] 
    coins_used = [None] 
    for i in range(1,target + 1): 
     if i % 1000 == 0: 
      print '...', 
     bestCost = sys.maxint 
     bestCoin = -1 
     for coin in coins: 
      if coin <= i: 
       cost = 1 + costs[i - coin] 
       if cost < bestCost: 
        bestCost = cost 
        bestCoin = coin 
     costs.append(bestCost) 
     coins_used.append(bestCoin) 
    ret = []  
    while target > 0: 
     ret.append(coins_used[target]) 
     target -= coins_used[target] 
    return ret 

coins = [1,10,25] 
target = 100033 
print get_best_coins(coins, target)