Programação dinâmica simplesEditar
Uma estratégia clássica de programação dinâmica funciona para cima, encontrando as combinações de todos os valores menores que se somariam ao limite atual. Assim, em cada limiar, todos os limiares anteriores são potencialmente considerados para trabalhar para cima até ao valor da meta W. Por este motivo, esta abordagem de programação dinâmica requer uma série de passos que é O(nW), onde n é o número de tipos de moedas.
ImplementationEdit
O que se segue é uma implementação de programação dinâmica (com Python 3) que usa uma matriz para acompanhar as soluções ótimas para os sub-problemas, e retorna o número mínimo de moedas, ou “Infinity” se não houver maneira de fazer troco com as moedas dadas. Uma segunda matriz pode ser usada para obter o conjunto de moedas para a solução ótima.
def _get_change_making_matrix(set_of_coins, r: int): m = for _ in range(len(set_of_coins) + 1)] for i in range(1, r + 1): m = float('inf') # By default there is no way of making change return mdef change_making(coins, n: int): """This function assumes that all coins are available infinitely. n is the number to obtain with the fewest coins. coins is a list or tuple with the available denominations. """ m = _get_change_making_matrix(coins, n) for c in range(1, len(coins) + 1): for r in range(1, n + 1): # Just use the coin coins. if coins == r: m = 1 # coins cannot be included. # Use the previous solution for making r, # excluding coins. elif coins > r: m = m # coins can be used. # Decide which one of the following solutions is the best: # 1. Using the previous solution for making r (without using coins). # 2. Using the previous solution for making r - coins (without # using coins) plus this 1 extra coin. else: m = min(m, 1 + m]) return m
Programação dinâmica com a árvore de convolução probabilísticaEdit
A árvore de convolução probabilística também pode ser usada como uma abordagem mais eficiente de programação dinâmica. A árvore de convolução probabilística funde pares de moedas para produzir todas as quantidades que podem ser criadas por aquele par de moedas (sem nenhuma moeda presente, apenas a primeira moeda presente, apenas a segunda moeda presente, e ambas as moedas presentes), e posteriormente fundindo pares destes resultados fundidos da mesma maneira. Este processo é repetido até que as duas colecções finais de resultados sejam fundidas numa só, levando a uma árvore binária equilibrada com W log(W) tais operações de fusão. Além disso, através da discretização dos valores das moedas, cada uma destas operações de fusão pode ser realizada através da convolução, que muitas vezes pode ser realizada de forma mais eficiente com a transformação rápida de Fourier (FFT). Desta forma, a árvore de convolução probabilística pode ser utilizada para alcançar uma solução em número subquadrático de passos: cada convolução pode ser realizada em n log(n), e as operações iniciais (mais numerosas) de fusão utilizam um n menor, enquanto as operações posteriores (menos numerosas) requerem n na ordem de W.
O método de programação dinâmica baseada em árvores de convolução probabilística também resolve eficientemente a generalização probabilística do problema de mudança, onde a incerteza ou imprecisão na quantidade de objetivo W a torna uma distribuição discreta ao invés de uma quantidade fixa, onde o valor de cada moeda é igualmente permitido ser difuso (por exemplo, quando uma taxa de câmbio é considerada), e onde diferentes moedas podem ser usadas com frequências particulares.
Método gananciosoEditar
Para os chamados sistemas canônicos de moedas, como os utilizados nos EUA e em muitos outros países, um algoritmo ganancioso de escolher a maior denominação de moeda que não seja maior do que a quantidade restante a ser feita produzirá o resultado ótimo. Este não é, porém, o caso dos sistemas de moedas arbitrárias. Por exemplo, se as denominações das moedas fossem 1, 3 e 4, então para fazer 6, o algoritmo ganancioso escolheria três moedas (4,1,1) enquanto que a solução ótima é duas moedas (3,3). É possível testar se um sistema de moedas é canônico (ou seja, se o algoritmo ganancioso sempre resolve seu problema de fazer troco de maneira ótima) em tempo polinomial.