Diviser et Conquérir - Minimum de Changement - Renvoyez des Pièces en Array

Question

Ci-dessous est une solution de force brute au problème de changement de pièce minimum. Il faut un int A, qui est le changement qui doit être fait, et un tableau de dénominations de pièces de monnaie. Il retourne un objet, les résultats, qui a les pièces de monnaie minimales qui peuvent être retournées sur la base du tableau des dénominations de pièces de monnaie ainsi que la matrice de pièces de monnaie.

Par exemple, si on lui demandait de donner changement pour 10 cents avec les valeurs [1, 2, 5], il doit retourner 2 pièces min et un tableau [0, 0, 2] pour deux pièces de dix cents.

Il renvoie la valeur minimale correcte, mais pas le bon tableau de pièces.

# values the algorithms should return, the min num of coins, the actual  
# coins in an array, and the original 

# array of coin denominations 
class Results: 

    a = 0 
    change = [] 
    coinsDenom = [] 

# A is an array of coin denominations 
# C is the change to be made 
# returns results object 
def changeslow(A, C): 
    res = Results() 
    res.coinsDenom = C 
    res.change = [] 
    # initialize your change array to be the length of the coindenom array 
    for i in range(0, len(res.coinsDenom)): 
     res.change.append(0) 

    minCoins = A 

    for i in [j for j in C if j <= A]: 
     if j == A: 
      res.a = 1 
      res.change[i] = res.change[i] + 1 
      return res 

     nextcall = changeslow(A-i, C) 
     numCoins = 1 + nextcall.a 

     if numCoins < minCoins: 
      minCoins = numCoins 
      res.change = nextcall.change 
      res.change[0] = res.change[0] + 1 



    res.a = minCoins 

    return res 

Answer 1

Ce problème est mieux résolu en utilisant dynamic programming. Par exemple, reportez-vous à cette http://www.columbia.edu/~cs2035/courses/csor4231.F07/dynamic.pdf pour la formulation de programmation dynamique intuitive suivante:

# DP-CHANGE 
# find number of coins needed to represent a value and memoize the last coin 
def DP_CHANGE(denoms, value): 
    num_coins = [0]*(value+1) # store number of coins needed to represent coin values from [0..value] 
    last_coin = [float('Inf')]*(value+1) # memoize last coin used to represent coin values from [0..value] 
    for d in denoms: 
     num_coins[d] = 1 
    for i in range(1, value + 1): 
     num_denom = min([(num_coins[i-d] + 1, d) for d in denoms if i - d >= 0]) 
     num_coins[i], last_coin[i] = num_denom[0], num_denom[1] 
    return num_coins, last_coin 

# TRACE-CHANGE 
# back-trace the denominations used 
def TRACE_CHANGE(value, last_coin): 
    denoms_used = [] 
    while value > 0: 
     denoms_used.append(last_coin[value]); 
     value-=last_coin[value] 
    return denoms_used 

def FIND_CHANGE(value, denoms): 
    num_coins, last_coin = DP_CHANGE(denoms, value) 
    print 'number of coins needed to represent values ' + str(range(value+1)) + ': ' + str(num_coins) 
    print 'minimum number of coins need to represent the value ' + str(value) + ': ' + str(num_coins[value]) 
    print 'coins of denominations needed:' + str(TRACE_CHANGE(value, last_coin)) 

FIND_CHANGE(10, [1,2,5]) 
# number of coins needed to represent values [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]: 
#           [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2] 
# minimum number of coins need to represent the value 10: 2 
# coins of denominations needed:[5, 5]