Olá meus amigos nerds, essa semana meus parcos conhecimentos sobre programação dinâmica me permitiram chegar um pouco mais perto de um antigo objetivo meu. E para comemorar, nada melhor que apresentar um problema sobre esse tema!
Hoje vamos discutir o problema 2836. Moedas. Nesse problema, vamos ajudar o rei da Pinelândia a descobrir qual é o número mínimo de moedas que ele precisa juntar para ter um determinado valor. Mais especificamente, dados os valores das moedas disponíveis e um valor que se deseja somar, determinar o número mínimo de moedas que deve ser usado para somar o valor desejado, ou dizer que tal soma é impossível.
Modelagem
Este é um problema clássico de Programação Dinâmica, chamado de Change-making problem, ou Coin Change. Sendo assim não vou falar muito sobre ele.
Vamos começar pelos casos triviais:
Se queremos somar 0 tostões, precisamos de 0 moedas...
Se precisamos somar x tostões e temos uma moeda de x tostões precisamos de uma moeda...
Se precisamos somar x tostões e a moeda de menor valor é maior que x, então o problema é impossível...
Agora vem o truque.
Se precisamos somar y tostões usando uma única moeda de x tostões precisamos ser capazes de juntar moedas no valor de y-x tostões. Assim se formos capazes de determinar o número mínimo de moedas necessárias para juntar y-x tostões nosso problema fica resolvido.
Mais formalmente, sejam m o valor que queremos ajuntar e m1, m2,..,mm os valores das moedas disponíveis, temos:
minimoMoedas(0) = 0minimoMoedas(m) = 1 se temos uma moeda de m tostões
minimoMoedas(m) = 1 + minimo [minimoMoedas(m-m1), minimoMoedas(m-m2), ...,minimoMoedas(m-mm)]
Basta agora fazermos uma programação dinâmica para calcular minimoMoedas e Voilá, problema resolvido.
Há muitos artigos na internet sobre o problema MOEDAS do SPOJ, mas em todos eles os autores escondem o jogo de como resolvê-lo com explicações supérfluas e incompletas que só confundem e o código apresentado é de difícil entendimento para quem não sabe a estratégia adotada. Depois de muito procurar só achei um que dava uma tênue ideia de como implementar a solução.
ResponderExcluirPara acabar com isso, vou aqui entregar o ouro. Crie um vetor ("qm") onde o índice representará os valores inteiros de zero até o preço (o SPOJ chama de "m" e sugere que seja um vetor de 50000 posições, p.ex., qm[50000]). A posição zero será preenchida com zero significando que são necessárias zero moedas para pagar um preço de zero tostões. Use um flag para preencher as posições impossíveis de terem um número de moedas sem troco. Para simplificar a programação, escolha um valor alto como o inteiro máximo da linguagem escolhida ou 50001 ou preço+1. As restantes posições do vetor devem ser preenchidas com
1+qm[i-v[j]],
onde "v" é o vetor com os valores das moedas, se qm[i-v[j]] não for impossível. Segue este trecho do código na linguagem C:
for(i=1; i<=preco; i++) {
qm[i]=MAX_VALOR;
for(j=n-1; j>=0; j--) {
if(i>=v[j]) {
if(qm[i - v[j]]<MAX_VALOR) {
t = 1 + qm[x];
if(t<qm[i]) {
qm[i]=t;
}
}
}
}