o problema de mudança aborda a questão de encontrar o número mínimo de moedas (de certas denominações) que somam até um determinado montante de dinheiro. É um caso especial do problema do knapsack inteiro, e tem aplicações mais amplas do que apenas a moeda.
também é a variação mais comum da mudança da moeda problema, um caso geral de partição na qual, dada a disponível denominações de um conjunto infinito de moedas, o objetivo é descobrir o número de maneiras possíveis de fazer uma mudança para uma quantidade específica de dinheiro, sem considerar a ordem das moedas.fazer a mudança é um problema de minimização, escolhemos a solução onde temos de dar o número mínimo de moedas para uma determinada quantidade.
- método ganancioso
2. Método dinâmico
programação dinâmica
uma estratégia de programação dinâmica clássica funciona para cima, encontrando as combinações de todos os valores menores que somariam ao limiar actual.Assim, em cada limiar, todos os anteriores limites são potencialmente considerada para o trabalho para cima, para a quantidade de golos W. Por esta razão, este dinâmico abordagem de programação podem exigir um número de passos que é, no mínimo, quadrática, com o objetivo quantidade W.
ideal da mudança da moeda temos visto isso, você quer fazer a mudança através de um sistema de denominações, utilizando o menor número de moedas possível. Às vezes, o algoritmo ganancioso dá a solução ideal. Mas às vezes não-um exemplo foi o sistema (12, 5, 1), onde o algoritmo dinâmico dá 15 = 12 + 1 + 1 + 1 mas uma resposta melhor é 15 = 5 + 5 + 5. mas a dinâmica dá sempre a solução ideal ou possíveis moedas mínimas dentro desses denominadores.
Steps:-
we will find the minimum no. de moedas necessárias para o montante .
A quantidade é a quantidade para a qual estamos fazendo a mudança.
vamos primeiro definir min. Não. = = notas = = = = ligações externas = = , min = INFINITY isto significa que inicialmente não sabemos quantas moedas serão necessárias.
então nós verificamos cada moeda de denominação e vemos se ela pode ser usada para obter a solução.se possível, atualizamos as variáveis min e coin.
where, min = minimum no. of coins required for making change for amount
coin = first index of the coin in the solution
exemplo:
Amount = 5
coins = {1,2,3}
Ways to make change = 5
