Problema das Moedas

...

int troco(int S[],int n,int V,int D[]) {

int C[V+1];

int i,j;

int min,coin;

C[0] = 0;

for(i = 1; i <= V; i++) {

min = INT_MAX;

for(j = 0; j < n; j++) {

if(S[j] <= i) {

if((C[i-S[j]]) < min) {

min = C[i-S[j]];

coin = j;

}

}

}

D[i] = coin;

if( min < INT_MAX )

C[i] = min + 1;

else

C[i] = INT_MAX;

}

return C[V];

}

int main() {

int S[] = {5,8,6,10,2};

int n = sizeof(S)/sizeof(int);

int V = 17;

int D[V+1];

printf("Quantidades de Moedas: %d\n",troco(S,n,V,D));

mostraTroco(D,S,V);

return 0;

}

Saída do algoritmo

Para entrada: S = {5,8,6,10,2} e V = 17

Quantidades de Moedas: 3

Moedas: 5 6 6

Para entrada: S = {5,2,7,10,20} e V = 18

Quantidades de Moedas: 4

Moedas: 2 2 7 7