VERSIONE ORIGINALE

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

void calcolaResto(int n, int *val, int *disp, int r);
int calcolaRestoR(int pos, int n, int *val, int *dispR, int *sol, int r, int k);
int check(int *sol, int n, int *val, int r);
int numeroMonete(int *sol, int n);
int main()
{

    int n = 3, r;
    int val[3] = {1,10,25};
    int disp[3] = {10,3,2};

    r = 30;

    calcolaResto(n, val, disp, r);
    return 0;
}
void calcolaResto(int n, int *val, int *disp, int r){
    int i, j , k;
    int *sol, *dispR;
    sol = calloc(n,sizeof(int));
    dispR = malloc(n*sizeof(int));
    for(j=0; j<n; j++)
        dispR[j] = disp[j];
    for(k=1; k<n; k++){
        if(calcolaRestoR(0,n,val,dispR,sol,r,k))
            break;
    }
    i = 0;
    i = numeroMonete(sol ,n);

    printf("Numero monete: %d", i);
    return;
}

int calcolaRestoR(int pos, int n, int *val, int *dispR, int *sol, int r, int k)
{
    int i, ris;
    if(pos >= k){
        if(check(sol, n, val, r))
            return 1;
    }
    for(i = 0; i < n; i++){
        if(dispR[i]>0){
            dispR[i]--;
            sol[i]++;
            ris = calcolaRestoR(pos+1,n,val,dispR,sol,r,k);
            if(ris == 1) return 1;
            dispR[i]++;
            sol[i]--;
        }
    }
    return ris;
}
int check(int *sol, int n, int *val, int r){
    int i, conta, ris;
    ris = 0;
    for(i = 0; i < n; i++){
        conta = sol[i];
        while(conta > 0){
            ris += val[i];
            conta--;
        }
    }
    if(ris == r)
        return 1;
    return 0;
}
int numeroMonete(int *sol, int n){
    int ris, i;
    ris = 0;
    for(i = 0; i < n; i++){
        ris += sol[i];
    }
    return ris;
}