Problema das Moedas

O problema das moedas consiste em: para um valor de troco V, e com um estoque infinito de cada uma das n moedas de diferentes valores x1,x2,…, xn, quais e quantas moedas se deve entregar de modo que o total de moedas seja o mínimo possível? Para uma solução ótima será usado programação dinâmica, que é a análise de subproblemas mais simples a fim de resolver o problema original, o qual é mais complexo.

A solução para o problema das moedas é composto de soluções para subproblemas. Dado:

S=X0,X1,..Xn : conjunto de moedas;

V: valor que se quer pagar com as moedas;

C[V]: quantidade de moedas para chegar ao valor V;

D[V]: índice onde estão as moedas para chegar ao valor V;

n: quantidade de tipos de moedas;

C[0] = 0

C[V] = min(C[V-X0], C[V-X1]...C[V-Xn]) + 1

é apresentado o algoritmo e a análise:

Análise de complexidade e algoritmo

troco(S,n,V) Custo Complexidade

C[0] <- 0 c1 O(1)

para i <- 1 até V c2 O(nV)

min <- INFINITO c3 O(1)

para j <- 0 até n c4 O(n)

se ( S[j] <= i ) faça c5 O(1)

se ( C[i - S[j]] < min ) faça c6 O(1)

min <- C[i - S[j]] c7 O(1)

coin <- j c8 O(1)

D[i] <- coin c9 O(1)

se ( min < INFINITO ) faça c10 O(1)

C[i] <- min + 1 c11 O(1)

senão

C[i] <- INFINITO c13 O(1)

return C[V] e D C14 O(1)

Complexidade Total

c1*O(1) + c2*O(n*V) + c10*O(1) + c11*O(1) + c13*O(1) + c14*O(1)

Logo, complexidade do algoritmo é: O(nV)

Como calculado acima, o custo do algoritmo é O(nV), logo o algoritmo não é polinomial e sim linear.

Implementação

#include<stdlib.h>

#include<stdio.h>

#include<limits.h>

void mostraTroco(int D[],int S[],int V) {

printf("Moedas: ");

while(V > 0) {

printf("%d ",S[D[V]]);

V = V - S[D[V]];

}

printf("\n");

}

...