Lab2_Algoritmia_P2_Coin_Change

#include <stdio.h>
#include <stdlib.h>

/*
 *
 */
#define MIN(x,y) (((x)<(y)) ? (x) : (y))
#define MAXSIZE 100

int main(int argc, char** argv) {
    int F[MAXSIZE+1],D[MAXSIZE+1];
    int j,m,k,n,temp;
    printf("Ingrese cantidad de monedas (maximo 100):");
    scanf("%d",&m);
    printf("ingrese las %d monedas: ",m);
    for(k=1;k<=m;k++){
        scanf("%d",&temp);
        D[k]=temp;
    }
    printf("ingrese el monto que deben sumar las monedas:");
    scanf("%d",&n);
    F[0]=0;
    for(k=1;k<=n;k++) {
        j=1;
        while(j<=m && k >= D[j]) {
            if(j==1) temp=F[k-D[j]];
            temp= MIN(F[k-D[j]],temp);
            j++;
        }
        F[k]=temp+1;
    }
    int cant[m]; // almaceno la cantidad de cada denominacion
    for(j=1;j<=m;j++) cant[j]=0; // inicializo
    k=n;
    printf("la minima cantidad de monedas es %d \n",F[n]);
    while(k>=1){ // hallo
        j=1;
        int jmin=1;
        while(j<=m && k >= D[j]) {
            if(j==1) temp=F[k-D[j]];
            temp= MIN(F[k-D[j]],temp);
            if((F[k-D[j]])<=temp) jmin=j;
            j++;
        }
        cant[jmin]++;
        k-=D[jmin];
    }
    printf("denominaciones usadas:\n");
    for(k=1;k<=m;k++){
        if(cant[k]>0)
            printf("%d moneda(s) de %d \n",cant[k],D[k]);
    }
    return (EXIT_SUCCESS);
}